Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes

Abstract

We study the behavior of Approximate Message-Passing, a solver for linear sparse estimation problems such as compressed sensing, when the i.i.d matrices -for which it has been specifically designed- are replaced by structured operators, such as Fourier and Hadamard ones. We show empirically that after proper randomization, the structure of the operators does not significantly affect the performances of the solver. Furthermore, for some specially designed spatially coupled operators, this allows a computationally fast and memory efficient reconstruction in compressed sensing up to the information-theoretical limit. We also show how this approach can be applied to sparse superposition codes, allowing the Approximate Message-Passing decoder to perform at large rates for moderate block length.

20 pages, 10 figures

References in corpus (5)

• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• The Effect of Spatial Coupling on Compressive Sensing
• Analysis of Compressed Sensing with Spatially-Coupled Orthogonal Matrices

Cited by in corpus (21)

• Statistical physics of inference: Thresholds and algorithms
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Sparse Regression Codes
• Techniques for improving the finite length performance of sparse superposition codes
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Generalized Turbo Signal Recovery for Nonlinear Measurements and Orthogonal Sensing Matrices
• An Approximate Message Passing Framework for Side Information
• Modulated Sparse Superposition Codes for the Complex AWGN Channel
• Concise Derivation of Complex Bayesian Approximate Message Passing via Expectation Propagation
• Generalized Approximate Message-Passing Decoder for Universal Sparse Superposition Codes
• Phase diagram of matrix compressed sensing
• EXIT Chart Analysis of Turbo Compressed Sensing Using Message Passing De-Quantization
• Two-Part Reconstruction with Noisy-Sudocodes
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Scampi: a robust approximate message-passing framework for compressive imaging
• Using List Decoding to Improve the Finite-Length Performance of Sparse Regression Codes
• State Estimation in Smart Distribution System With Low-Precision Measurements
• Compressed Coding, AMP Based Decoding and Analog Spatial Coupling