Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing

DOI10.1109/TIT.2013.2274513MaRDI QIDQ5346265zbMATH OpenOpenAlexFDO

Authors David Donoho, A. Javanmard, Andrea Montanari

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.0708

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Measures of information, entropy (94A17)

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 $delta$ exceeds the (upper) R'enyi information dimension of the signal, $uRenyi(p_X)$. More precisely, for a sequence of signals of diverging dimension $n$ whose empirical distribution converges to $p_X$, 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 $n$ and $k(n)$ non-zero entries, this implies reconstruction from $k(n)+o(n)$ measurements. For `discrete' signals, i.e., signals whose coordinates take a fixed finite set of values, this implies reconstruction from $o(n)$ 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 $p_X$.

Cited in

(25)

• Universality of approximate message passing algorithms
• On convergence of the cavity and Bolthausen's TAP iterations to the local magnetization
• Marginals of a spherical spin Glass model with correlated disorder
• Precise statistical analysis of classification accuracies for adversarial training
• Approximate message passing algorithms for rotationally invariant matrices
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• Universality in polytope phase transitions and message passing algorithms
• Fundamental limits of weak recovery with applications to phase retrieval
• On reconstructing functions from binary measurements
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Typical reconstruction limits for distributed compressed sensing based on \(\ell_{2,1} \)-norm minimization and Bayesian optimal reconstruction
• Message-Passing De-Quantization With Applications to Compressed Sensing
• Decoding from pooled data: sharp information-theoretic bounds
• Approximate message passing with spectral initialization for generalized linear models*
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Weak-type estimates for the metaplectic representation restricted to the shearing and dilation subgroup of \(\mathrm{SL}(2,\mathbb{R})\)
• Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation
• A Unifying Tutorial on Approximate Message Passing
• Optimal group testing
• Multi-layer state evolution under random convolutional design
• Universality of approximate message passing algorithms and tensor networks
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• Noisy group testing via spatial coupling
• Inference and mutual information on random factor graphs
• A nonasymptotic distributional theory of approximate message passing for sparse and robust regression

This page was built for publication: Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346265)