The Replica-Symmetric Prediction for Compressed Sensing with Gaussian Matrices is Exact

Galen just sent me the following:

Hi Igor,

This week I presented some work at ISIT that might be of interest. In joint work with Henry Pfister, we have shown that the replica-symmetric prediction for compressed sensing with Gaussian matrices is exact. ( https://arxiv.org/abs/1607.02524 ) In fact, I gave a talk about the proof of this result in March (https://www.youtube.com/watch?v=vmd8-CMv04I ), which you were kind enough to feature on your website (Its my fault that the abstract did not reflect the content of the talk).

Moreover, some people might be interested relationship between this paper and the recent work by Jean Barbier, Mohamad Dia, Nicolas Macris, Florent Krzakala titled, "The Mutual Information in Random Linear Estimation”. [Note: mentioned earlier on Nuit Blanche]  I would like to point that there proof techniques are very different and that there are some important difference in the assumptions that are required. Perhaps the most significant difference is that their approach requires discrete and bounded distributions that satisfy a certain “three-solution” property. By contrast, our result applies to any distribution that has bounded fourth moment and also satisfies a certain ``single-crossing’’ property, which is more general then the three-solution property. (See, e.g., Figure~1 in our paper for an example).

cheers,
Galen

Let me make a small comment here with regards to pre- and post- publication peer review. In this case of two groups arriving to a very similar results on an open conjecture, the question has become "who needs pre-publication peer review ?" Indeed, the Arxiv date stamps for the preprints and the date the video was posted on YouTube somehow prove that both groups have proven an interesting conjecture independently albeit with different assumptions. In previous times, I am absolutely sure that one of the two groups could have thought that an anonymous pre-publication reviewer was slowing down the review for other reasons than a scientific one.  In the end, the result is even stronger: since both proofs and assumptions are different, there is even a sense, to a non-specialist like myself, that the result will hold the test of time. Congratulations to both groups !
And thanks Galen for the heads-up. Here is the paper:

The Replica-Symmetric Prediction for Compressed Sensing with Gaussian Matrices is Exact by Galen Reeves, Henry D. Pfister

This paper considers the fundamental limit of compressed sensing for i.i.d. signal distributions and i.i.d. Gaussian measurement matrices. Its main contribution is a rigorous characterization of the asymptotic mutual information (MI) and minimum mean-square error (MMSE) in this setting. Under mild technical conditions, our results show that the limiting MI and MMSE are equal to the values predicted by the replica method from statistical physics. This resolves a well-known problem that has remained open for over a decade.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page 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.