2010

The dynamics of message passing on dense graphs, with applications to compressed sensing

Bayati, Mohsen, Montanari, Andrea

Understand

Approximate message passing algorithms proved to be extremely effective in reconstructing sparse signals from a small number of incoherent linear measurements.

Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution.
In this paper we provide the first rigorous foundation to state evolution.
We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed gaussian entries.

Built on

V. A. Marcenko and L. A. Pastur, Distribution of Eignevalues for Some Sets of Random Matrices , Mathematics of the USSR-Sbornik 1
1967
Earlier work this paper cites.
C. Stein, A bound for the error in the normal approximation to the distribution of a sum of dependent random variables , Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, 1972
1972
Earlier work this paper cites.
D. L. Donoho and I. M. Johnstone, Ideal spatial adaptation via wavelet shrinkage , Biometrika 81
1994
Earlier work this paper cites.
I. Benjamini and O. Schramm, Percolation beyond Z d Z^{d} , many questions and a few answers , Electron. Comm. Probab. 1
1996
Earlier work this paper cites.
T. C. Hu and R. L. Taylor, Strong law for arrays and for the bootstrap mean and variance , Internat. J. Math. and Math. Sci. 20
1997
Earlier work this paper cites.
D. N.C. Tse and S. V. Hanly, Linear multiuser receivers: effective interference, effective bandwidth and user capacity , IEEE Trans. on Inform. Theory 45
1999
Earlier work this paper cites.
S. Verdú and S. Shamai, Spectral efficiency of CDMA with random spreading , IEEE Trans. on Inform. Theory 45
1999
Earlier work this paper cites.
D. Aldous, The ζ ⁡ ( 2 ) \zeta(2) Limit in the Random Assignment Problem , Random Structures and Algorithms 18
2001
Earlier work this paper cites.
T. Tanaka, A statistical-mechanics approach to large-system analysis of cdma multiuser detectors , IEEE Trans. on Inform. Theory 48
2002
Earlier work this paper cites.
D. Aldous and J. M. Steele, The Objective Method: Probabilistic Combinatorial Optimization and Local Weak Convergence , Probability on discrete structures (H. Kesten, ed.), Springer Verlag, 2003, pp. 1–72
2003
Earlier work this paper cites.

Similar

Y. Kabashima, A CDMA multiuser detection algorithm on the basis of belief propagation , J. Phys. A 36
2003
Cited alongside, same era.
I. Daubechies, M. Defrise, and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint , Communications on Pure and Applied Mathematics 75
2004
Cited alongside, same era.
D. L. Donoho and J. Tanner, Neighborliness of randomly-projected simplices in high dimensions , Proceedings of the National Academy of Sciences 102
2005
Cited alongside, same era.
J.P. Neirotti and D. Saad, Improved message passing for inference in densely connected systems , Europhys. Lett. 71
2005
Cited alongside, same era.
T. Tanaka, Statistical physics of information processing in mobile communications , Progr. of Theor. Phys. Suppl. 157
2005
Cited alongside, same era.
D. Donoho, For most large underdetermined systems of equations, the minimal ℓ 1 \ell_{1} -norm near-solution approximates the sparsest near-solution , Communications on Pure and Applied Mathematics 59
2006
Cited alongside, same era.
A. Montanari and D. Tse, Analysis of belief propagation for non-linear problems: the example of CDMA (or: how to prove Tanaka’s formula) , Proceedings of IEEE Inform. Theory Workshop (Punta de l’Este, Uruguay), 2006
2006
Cited alongside, same era.
T.J. Richardson and R. Urbanke, Modern Coding Theory , Cambridge University Press, Cambridge, 2008
2008
Cited alongside, same era.
E. Bolthausen, On the high-temperature phase of the Sherrington-Kirkpatrick model , Seminar at EURANDOM, Eindhoven, September 2009
2009
Cited alongside, same era.
D. L. Donoho and A. Maleki, Optimally tuned iterative thresholding algorithm for compressed sensing , To appear, 2009
2009
Cited alongside, same era.

Then

D. L. Donoho, A. Maleki, and A. Montanari, Message Passing Algorithms for Compressed Sensing , Proceedings of the National Academy of Sciences 106
2009
Later among the works it cites.
D. Guo, D. Baron, and S. Shamai, A single-letter characterization of optimal noisy compressed sensing , 47th Annual Allerton Conference (Monticello, IL), September 2009
2009
Later among the works it cites.
Y. Kabashima, T. Wadayama, and T. Tanaka, A typical reconstruction limit for compressed sensing based on lp-norm minimization , J.Stat. Mech. (2009), L09003
2009
Later among the works it cites.
M. Mézard and A. Montanari, Information, Physics and Computation , Oxford University Press, Oxford, 2009
2009
Later among the works it cites.
S. Rangan, A. K. Fletcher, and V. K. Goyal, Asymptotic analysis of map estimation via the replica method and applications to compressed sensing , NIPS, 2009
2009
Later among the works it cites.
J. Salez and D. Shah, Belief propagation: optimal algorithm for random assignment problem , Mathematics of Operations Research 32
2009
Later among the works it cites.
M. Bayati and A. Montanari, The LASSO risk for gaussian matrices , submitted, 2010
2010
Closest in time.
D.L. Donoho, A. Maleki, and A. Montanari, The Noise Sensitivity Phase Transition in Compressed Sensing , Preprint, 2010
2010
Closest in time.
D. Guo and S. Verdu, Randomly Spread CDMA: Asymptotics via Statistical Physics , IEEE Trans. on Inform. Theory 51
2010
Closest in time.
M. Talagrand, Mean field models for spin glasses , vol. Volume I: Basic Examples, Springer, Berlin, 2010, available online
2010
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…