Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
arXiv:1112.0708
Abstract
We study the compressed sensing reconstruction problem for a broad class of random, band-diagonal sensing matrices. This construction is inspired by the idea of spatial coupling in coding theory. As demonstrated heuristically and numerically by Krzakala et al. \cite{KrzakalaEtAl}, message passing algorithms can effectively solve the reconstruction problem for spatially coupled measurements with undersampling rates close to the fraction of non-zero coordinates. We use an approximate message passing (AMP) algorithm and analyze it through the state evolution method. We give a rigorous proof that this approach is successful as soon as the undersampling rate exceeds the (upper) Rényi information dimension of the signal, $\uRenyi(p_X)$. More precisely, for a sequence of signals of diverging dimension whose empirical distribution converges to , reconstruction is with high probability successful from $\uRenyi(p_X)\, n+o(n)$ measurements taken according to a band diagonal matrix. For sparse signals, i.e., sequences of dimension and non-zero entries, this implies reconstruction from measurements. For `discrete' signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from measurements. The result is robust with respect to noise, does not apply uniquely to random signals, but requires the knowledge of the empirical distribution of the signal .
arXiv comment60 pages, 7 figures, Sections 3,5 and Appendices A,B are added. The stability constant is quantified (cf Theorem 1.7)
References in corpus (8)
- Message Passing Algorithms for Compressed Sensing
- Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
- Universality in polytope phase transitions and message passing algorithms
- Message-Passing Estimation from Quantized Samples
- A Message-Passing Receiver for BICM-OFDM over Unknown Clustered-Sparse Channels
- Threshold Saturation on BMS Channels via Spatial Coupling
- Optimal Phase Transitions in Compressed Sensing
- The LASSO risk for gaussian matrices