Statistical physics-based reconstruction in compressed sensing

Abstract

Compressed sensing is triggering a major evolution in signal acquisition. It consists in sampling a sparse signal at low rate and later using computational power for its exact reconstruction, so that only the necessary information is measured. Currently used reconstruction techniques are, however, limited to acquisition rates larger than the true density of the signal. We design a new procedure which is able to reconstruct exactly the signal with a number of measurements that approaches the theoretical limit in the limit of large systems. It is based on the joint use of three essential ingredients: a probabilistic approach to signal reconstruction, a message-passing algorithm adapted from belief propagation, and a careful design of the measurement matrix inspired from the theory of crystal nucleation. The performance of this new algorithm is analyzed by statistical physics methods. The obtained improvement is confirmed by numerical studies of several cases.

20 pages, 8 figures, 3 tables. Related codes and data are available at http://aspics.krzakala.org

References in corpus (1)

• Phase transition in the detection of modules in sparse networks

Cited by in corpus (80)

• Compressive Fluorescence Microscopy for Biological and Hyperspectral Imaging
• Universality in polytope phase transitions and message passing algorithms
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Threshold Saturation for Spatially-Coupled LDPC and LDGM Codes on BMS Channels
• On Convergence of Approximate Message Passing
• Generalisation error in learning with random features and the hidden manifold model
• The Mutual Information in Random Linear Estimation
• Near optimal compressed sensing without priors: Parametric SURE Approximate Message Passing
• A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• Networking - A Statistical Physics Perspective
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• The Mutual Information in Random Linear Estimation Beyond i.i.d. Matrices
• Performance Improvement of Iterative Multiuser Detection for Large Sparsely-Spread CDMA Systems by Spatial Coupling
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Unbiased Monte Carlo Cluster Updates with Autoregressive Neural Networks
• Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
• Variational Free Energies for Compressed Sensing
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
• Phase recovery from a Bayesian point of view: the variational approach
• State of the Art and Prospects of Structured Sensing Matrices in Compressed Sensing
• Approximate Message Passing with Restricted Boltzmann Machine Priors
• Dreaming neural networks: rigorous results
• Glassy nature of the hard phase in inference problems
• Performance Analysis of Approximate Message Passing for Distributed Compressed Sensing
• Modulated Sparse Superposition Codes for the Complex AWGN Channel
• Belief Propagation Reconstruction for Discrete Tomography
• Statistical Mechanics of Dictionary Learning
• Performance Limits for Noisy Multi-Measurement Vector Problems
• Inferring Sparsity: Compressed Sensing using Generalized Restricted Boltzmann Machines
• Bayesian signal reconstruction for 1-bit compressed sensing
• Inference of the sparse kinetic Ising model using the decimation method
• Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing
• Statistical-mechanical analysis of compressed sensing for Hamiltonian estimation of Ising spin glass
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• Tuning and jamming reduced to their minima
• Parallel Tempering for the planted clique problem
• Compressed Sensing of Approximately-Sparse Signals: Phase Transitions and Optimal Reconstruction
• On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix
• Compressed sensing reconstruction using Expectation Propagation
• Near-Optimal Coding for Many-user Multiple Access Channels
• Non-adaptive pooling strategies for detection of rare faulty items
• Online compressed sensing
• A weighted belief-propagation algorithm to estimate volume-related properties of random polytopes
• Fast inference of ill-posed problems within a convex space
• Phase diagram of matrix compressed sensing
• Dynamics and termination cost of spatially coupled mean-field models
• Approximate Message Passing with Parameter Estimation for Heavily Quantized Measurements
• Gaussian-Spherical Restricted Boltzmann Machines
• Typical $l_1$-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Statistical mechanics approach to 1-bit compressed sensing
• Large scale analysis of generalization error in learning using margin based classification methods
• Active pooling design in group testing based on Bayesian posterior prediction
• Interpolating between boolean and extremely high noisy patterns through Minimal Dense Associative Memories
• Compressed sensing with sparse, structured matrices
• Exact solution to the random sequential dynamics of a message passing algorithm
• Robust error correction for real-valued signals via message-passing decoding and spatial coupling
• Sample Distortion for Compressed Imaging
• Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
• Evaluation of Generalized Degrees of Freedom for Sparse Estimation by Replica Method
• Analysis of Bayesian Inference Algorithms by the Dynamical Functional Approach
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Phase transition in compressed sensing with horseshoe prior
• A Probabilistic Bayesian Approach to Recover $R_2^{\ast }$ map and Phase Images for Quantitative Susceptibility Mapping
• Scampi: a robust approximate message-passing framework for compressive imaging
• Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation
• Phase transition in binary compressed sensing based on $L_1$-norm minimization
• Accelerating Iterative Detection for Spatially Coupled Systems by Collaborative Training
• The phase diagram of compressed sensing with ${\ell }_0$-norm regularization
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens
• Statistical mechanics analysis of thresholding 1-bit compressed sensing
• Stability of the replica symmetric solution in diluted perceptron learning
• Typical reconstruction limit and phase transition of maximum entropy method
• Effect of global shrinkage parameter of horseshoe prior in compressed sensing