[Updated version ]

Back in the late 1990's I attended an interesting presentation in the physics department on stripe physics. From what I can gather it used to be a hot field in the condensed matter physics community for a little while [2]. The presenter,~~I can't recall his name except that he was Italian and worked in the physics department at ETHZ ~~Danilo Pescia (h/t to Nuit Blanche reader Philippe Doucet Beaupré for identifying him), made a point that, to this day, still makes an impression on me.

Back in the late 1990's I attended an interesting presentation in the physics department on stripe physics. From what I can gather it used to be a hot field in the condensed matter physics community for a little while [2]. The presenter,

**orders of magnitude. The second item that got me interested was his statement about how the phenomena seemed to occur computationally:**

*15*- If you are just looking at elements with short range +1/-1 spin interaction potential, then you have the typical spin systems yielding configurations that are, errrr, shall we say, chaotic, i.e. not really that interesting.
- However as soon as you add a long range potential such as 1/r^2, then the phenomenon of stripe physics starts to appear.

- In image processing, if you try to sample an image of a short range potential configuration, (a bunch of +1 scattered all over the image) then one will need many wavelets to reproduce that figure, since for each dot of the image, one will be required to have a few wavelets to represent each of the dots. To put it some other way, an image of that field would not be compressible or weakly sparse (the second term I did not use since as you recall it was the 1990s)
- adding a long range potential in the physics of the same system, the physical change and seems to produce a resulting field which if it were imaged, could be well (i.e. sparsely) decomposed in a series of (long range aka non-Haar) wavelets.

__shown to be compressible with wavelets series (see the connection between Zygmund-Calderon operators and wavelets in [1]). The speaker kind of liked the remark and then went on....__

**also**

__In other words, the family of wavelets used in the series expansion of the potential (so it has a compressible representation) also seemed to be relevant to the series expansion of the equilibrium field (so that the field could also have a compressible representation)__The Swedish researchers find that for any system where interactions can be modeled as isotropic, the emergence and the characteristic length scale of the pattern are determinedby the nontrivial minimum in the energy excitation spectrum, where the latter is simply the Fourier transform of the interaction potential. Even qualitatively different potentials end up having a dominant minimum in their energy spectrum, so the stripe morphology is merely the physical guise of this mathematical feature. Thus examining the problem in reciprocal space pays off nicely, the way it has so many times before in physics. In addition to finding a unifying feature of stripe morphologies, the proposed analysis opens up new possibilities for molecular assembly of patterned structures. The study goes as far as to provide a rather convincing proof of principle of how the scheme works in practice.

B. Related works The l_1-minimization based algorithms [1], [2] are widely used for compressed sensing of approximately sparse signals. They are very general and provide good performances in many situations. They, however, do not achieve optimal reconstruction when the statistical properties of the signal are known. The two-Gaussian model for approximately sparse signal eq. (1) was used in compressed sensing e.g. in [8], [9]. Belief propagation based reconstruction algorithms were introduced in compressed sensing by [8]. Authors of [8] used sparse measurement matrices and treated the BP messages as probabilities over real numbers, that were represented by a histogram. The messages, however, can be represented only by their mean and variance as done by [10], [11]. Moreover, one does not need to send messages between every signal components and every measurements [12], this leads to the approximate message passing (AMP). . The AMP was generalized for general signal models in [5], [6] and called G-AMP. The algorithm used in [3], [7] is equivalent to G-AMP. We also want to note that we ﬁnd the name “approximate” message passing a little misleading since, as argued e.g. in [7], for dense random measurement matrices the G-AMP is asymptotically equivalent to BP, i.e. all the leading terms in N are included in G-AMP.In the context of physics of spin glasses this transformation of the belief propagation equations corresponds to the Thouless-Anderson-Palmer equations [13]

__short range__potentials, are also the same solvers that are needed to find near optimal solutions to underdetermined linear systems with exactly sparse solutions (compressive sensing) that can be well decomposed with the

__short range Haar wavelets__.

**truncated wavelet series) tend to not be very well reconstructed with these solvers mentioned above (see some examples in [5]).**

*non*- Are there methods like belief propagation, cavity methods, etc in solid states physics that empirically find low entropy solutions with fields that include long range potentials ?
- If long range potentials can be decomposed well in series of (long range or non-Haar) wavelets, can some sort of hierarchical AMP solver see the light the day and really address the issue of weakly sparse signals ?

**[2]**Synopsis: Where stripes come from, summarizing elements from Universality of Striped Morphologies, E. Edlund and M. Nilsson Jacobi Phys. Rev. Lett. 105, 137203 (2010)

[3] D. Baron, S. Sarvotham, and R. Baraniuk, “Bayesian compressive sensing via belief propagation,” IEEE Transactions on Signal Processing,

Credit: E. Edlund et al., Phys. Rev. Lett. (2010)

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

vol. 58, no. 1, pp. 269 – 280, 2010.

[4] Compressed Sensing of Approximately-Sparse Signals: Phase Transitions and Optimal Reconstruction by Jean Barbier, Florent Krzakala, Marc Mezard , and Lenka Zdeborova

[5] Breaking the coherence barrier: asymptotic incoherence and asymptotic sparsity in compressed sensing

Credit: E. Edlund et al., Phys. Rev. Lett. (2010)

**Join the CompressiveSensing subreddit or the Google+ Community and post there !**

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

## No comments:

Post a Comment