Journal
IEEE TRANSACTIONS ON INFORMATION THEORY
Volume 57, Issue 2, Pages 764-785Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2010.2094817
Keywords
Compressed sensing; density evolution; message passing algorithms; random matrix theory; state evolution
Funding
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [743978] Funding Source: National Science Foundation
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [0806211] Funding Source: National Science Foundation
Ask authors/readers for more resources
Approximate message passing (AMP) algorithms have proved to be 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 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. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with a large number of short cycles in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available