Compressed Sensing of Approximately-Sparse Signals: Phase Transitions and Optimal Reconstruction

Abstract

Compressed sensing is designed to measure sparse signals directly in a compressed form. However, most signals of interest are only "approximately sparse", i.e. even though the signal contains only a small fraction of relevant (large) components the other components are not strictly equal to zero, but are only close to zero. In this paper we model the approximately sparse signal with a Gaussian distribution of small components, and we study its compressed sensing with dense random matrices. We use replica calculations to determine the mean-squared error of the Bayes-optimal reconstruction for such signals, as a function of the variance of the small components, the density of large components and the measurement rate. We then use the G-AMP algorithm and we quantify the region of parameters for which this algorithm achieves optimality (for large systems). Finally, we show that in the region where the GAMP for the homogeneous measurement matrices is not optimal, a special "seeding" design of a spatially-coupled measurement matrix allows to restore optimality.

8 pages, 10 figures

References in corpus (4)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Statistical physics-based reconstruction in compressed sensing

Cited by in corpus (6)

• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Fundamental limits of many-user MAC with finite payloads and fading
• Intensity-only optical compressive imaging using a multiply scattering material and a double phase retrieval approach
• Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing
• Non-adaptive pooling strategies for detection of rare faulty items
• Robust error correction for real-valued signals via message-passing decoding and spatial coupling