Galen just sent me the following:
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).
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.
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.