Extraordinary claims require extraordinary proofs which really is the reason why this sorts of discussion is important. Similarly, sometimes, you are so blinded to some sorts of a truth and are faced with something so different that you can misread entirely what is being said. If you read this morning's entry, you might get a feel that I am little ambivalent about the true interesting nature of a paper entitled Statistical physics-based reconstruction in compressed sensing by Florent Krzakala, Marc Mézard, François Sausset, Yifan Sun, Lenka Zdeborová. Let's put this in perspective, our current understanding so far is that the universal phase transition observed by Donoho and Tanner seems to be seen with all the solvers featured here, that there are many ensembles for which it fits (not just Gaussian, I remember my jaw dropping when Jared Tanner showed it worked for the ensembles of Piotr Indyk, Radu Berinde et al) and that the only way to break it is to now consider structured sparsity as shown by Phil Schniter at the beginning of the week. In most people's mind, the L_1 solvers are really a good proxy to the L_0 solvers since even greedy solvers (the closest we can find to L_0 solvers) seem to provide similar results. Then there are results like the ones of Shrinivas Kudekar and Henry Pfister. ( Figure 5 of The Effect of Spatial Coupling on Compressive Sensing) that look like some sort of improvement (but not a large one). In all, a slight improvement over that phase transition could, maybe, be attributed to a slightly different solver, or ensemble (measurement matrices). So this morning I made the point that given what I understood about the graphs displayed in the article, it may be at best a small improvement over the Donoho-Tanner phase transition known to hold for not only Gaussian but other types of matrices and for different kinds of solvers, including greedy algorithms and SL0 (that simulate some sorts of L_0 approach). At best is really an overstatement but I was intrigued mostly because of the use of an AMP solver, so I fired off an inquisitive e-mail on the subject to the corresponding author:
Dear Dr. Krzakala,
... I briefly read your recent paper on arxiv with regards to your statistical physics based reconstruction capability and I am wondering if your current results are within the known boundary of what we know of the phase transition found by Donoho and Tanner or if it is an improvement on it. I provided an explanation of what I meant in today's entry (http://nuit-blanche.blogspot.com/2011/09/this-week-in-compressive-sensing.html). If this is an improvement, I'd love to hear about it. If it is is not an improvement, one wonders if some of the deeper geometrical findings featured by the Donoho-Tanner phase transition have a bearing on phase transition on real physical systems.Best regards,Igor.
The authors responded quickly with:
Thanks for writing about our work in your blog.Please notice, however, that our axes in the figure you show are not the same as those of Donoho and Tanner. For a signal with N components, we define \rho N as the number of non-zeros in the signal, and \alpha N as the number of measurements. In our notation Donoho and Tanner's parameters are rho_DT = rho/alpha and delta_DT = alpha. We are attaching our figure plotted in Donoho and Tanner's way. Our green line is then exactly the DT's red line (since we do not put any restriction of the signal elements), the rest is how much we can improve on it with our method. Asymptotically (N\to \infty) our method can reconstruct exactly till the red line alpha=rho, which is the absolute limit for exact reconstruction (with exhaustive search algorithms).So we indeed improve a lot over the standard L1 reconstruction!We will be of course very happy to discuss/explain/clarify details if you are interested.With best regardsFlorent, Marc, Francois, Yifan, and Lenka
The reason I messed up reading the variables is because I was probably not expecting something that stunning.
Thank you for Florent Krzakala, Marc Mézard, François Sausset, Yifan Sun, Lenka Zdeborová for their rapid feedback.
Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from