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

DOI10.1109/TIT.2013.2274513zbMATH Open1364.94120arXiv1112.0708OpenAlexW2571527823MaRDI QIDQ5346265FDOQ5346265

Authors: David Donoho, A. Javanmard, Andrea Montanari 

Publication date: 8 June 2017

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

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$.

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)

Cited In (22)

• Approximate message passing with spectral initialization for generalized linear models*
• Universality in polytope phase transitions and message passing algorithms
• Weak-Type Estimates for the Metaplectic Representation Restricted to the Shearing and Dilation Subgroup of $$SL(2,\mathbb {R})$$
• On Reconstructing Functions from Binary Measurements
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• A Unifying Tutorial on Approximate Message Passing
• Approximate message passing algorithms for rotationally invariant matrices
• Optimal group testing
• Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation
• Typical reconstruction limits for distributed compressed sensing based on ℓ_2,1-norm minimization and Bayesian optimal reconstruction
• Fundamental limits of weak recovery with applications to phase retrieval
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Multi-layer state evolution under random convolutional design
• Universality of approximate message passing algorithms and tensor networks
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• Precise statistical analysis of classification accuracies for adversarial training
• Message-Passing De-Quantization With Applications to Compressed Sensing
• Universality of approximate message passing algorithms
• Decoding from Pooled Data: Sharp Information-Theoretic Bounds
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• On convergence of the cavity and Bolthausen's TAP iterations to the local magnetization
• Marginals of a spherical spin Glass model with correlated disorder

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)