Sunday Morning Insight: Stripe Physics, Wavelets and Compressive Sensing Solvers

[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.

He first described that stripe physics, the physics by which matter organized itself into stripe like figures, seemed to be pretty universal as it spread over 15 orders of magnitude. The second item that got me interested was his statement about how the phenomena seemed to occur computationally: 

• 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.  

 with an image processing view of the world, I then made the following remark. Given that, 

• 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.

I found it odd that the potentials (which happened to be Zygmund-Calderon operators) responsible for transforming fields into stripes ( therefore making the field sparse or compressible in a wavelet basis), were also 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....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)
It seems that some more insight has been gotten since the late 1990's, from [2]  

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 determined by 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. 

So there is some connection with the potential operator used in the hamiltonian of these systems. However, there seems to be little mention of the analyzing basis of the potential operator or the issue of sparsity.  Now let us turn to compressive sensing where any talks on the subject starts with "everything is sparse, including natural images". One could certainly agree that natural images are the embodiement of stripe physics. Here is the peculiar connection: Some of the solvers needed to reconstruct a sparse signal from its multiplexed projection are belief propagation solvers [3] of a certain kind (Approximate Message Passing or AMP). From [4] 

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). In the context of physics of spin glasses this transformation of the belief propagation equations corresponds to the Thouless-Anderson-Palmer equations [13]. 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 find 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.

[emphasis mine]
In short, the numerical solvers needed to find optimal configurations in spin glasses systems with 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.
We also know that images that are weakly sparse or compressible (i.e. images can be decomposed as a non truncated wavelet series) tend to not be very well reconstructed with these solvers mentioned above (see some examples in [5]).
Here are my stupid questions of the day:

• 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 ?

[1] Fast Wavelet Transforms and Numerical Algorithms I, G. Beylkin, R. Coifman, V. Rokhlin [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) Published September 21, 2010

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

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.