Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices

Abstract

Compressed sensing is a signal processing method that acquires data directly in a compressed form. This allows one to make less measurements than what was considered necessary to record a signal, enabling faster or more precise measurement protocols in a wide range of applications. Using an interdisciplinary approach, we have recently proposed in [arXiv:1109.4424] a strategy that allows compressed sensing to be performed at acquisition rates approaching to the theoretical optimal limits. In this paper, we give a more thorough presentation of our approach, and introduce many new results. We present the probabilistic approach to reconstruction and discuss its optimality and robustness. We detail the derivation of the message passing algorithm for reconstruction and expectation max- imization learning of signal-model parameters. We further develop the asymptotic analysis of the corresponding phase diagrams with and without measurement noise, for different distribution of signals, and discuss the best possible reconstruction performances regardless of the algorithm. We also present new efficient seeding matrices, test them on synthetic data and analyze their performance asymptotically.

42 pages, 37 figures, 3 appendixes

References in corpus (9)

• Message Passing Algorithms for Compressed Sensing
• The dynamics of message passing on dense graphs, with applications to compressed sensing
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Phase transition in the detection of modules in sparse networks
• Statistical physics-based reconstruction in compressed sensing
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization
• The Nishimori line and Bayesian Statistics
• Glassy dynamics as a melting process (On melting dynamics and the glass transition, Part II)

Cited by in corpus (90)

• A high-bias, low-variance introduction to Machine Learning for physicists
• Statistical physics of inference: Thresholds and algorithms
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• SPARCs for Unsourced Random Access
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Mixed-ADC Massive MIMO Detectors: Performance Analysis and Design Optimization
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Compressive Hyperspectral Imaging via Approximate Message Passing
• Bayesian Optimal Data Detector for Hybrid mmWave MIMO-OFDM Systems with Low-Resolution ADCs
• On Convergence of Approximate Message Passing
• A Unified Bayesian Inference Framework for Generalized Linear Models
• The Mutual Information in Random Linear Estimation
• Near optimal compressed sensing without priors: Parametric SURE Approximate Message Passing
• A Theory of Solving TAP Equations for Ising Models with General Invariant Random Matrices
• Parametric Bilinear Generalized Approximate Message Passing
• On the Performance of Turbo Signal Recovery with Partial DFT Sensing Matrices
• A Simple Proof of Maxwell Saturation for Coupled Scalar Recursions
• Cross validation in LASSO and its acceleration
• Approximate Message Passing with Unitary Transformation for Robust Bilinear Recovery
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Provable Convergence of Plug-and-Play Priors with MMSE denoisers
• Mutual Information and Optimality of Approximate Message-Passing in Random Linear Estimation
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• Joint Activity Detection and Channel Estimation in Cell-Free Massive MIMO Networks with Massive Connectivity
• Bayesian Optimal Data Detector for mmWave OFDM System with Low-Resolution ADC
• Location Identification of Power Line Outages Using PMU Measurements with Bad Data
• Finite Sample Analysis of Approximate Message Passing Algorithms
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• High-temperature Expansions and Message Passing Algorithms
• Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
• The condensation phase transition in random graph coloring
• Variational Free Energies for Compressed Sensing
• Mean-field inference methods for neural networks
• Disordered Systems Insights on Computational Hardness
• Multi-Layer Generalized Linear Estimation
• Generalized Turbo Signal Recovery for Nonlinear Measurements and Orthogonal Sensing Matrices
• Statistical mechanics of unsupervised feature learning in a restricted Boltzmann machine with binary synapses
• Approximate Message Passing with Restricted Boltzmann Machine Priors
• Intensity-only optical compressive imaging using a multiply scattering material and a double phase retrieval approach
• Performance Analysis of Approximate Message Passing for Distributed Compressed Sensing
• An Approximate Message Passing Framework for Side Information
• Belief Propagation Reconstruction for Discrete Tomography
• Statistical Mechanics of High-Dimensional Inference
• Inferring Sparsity: Compressed Sensing using Generalized Restricted Boltzmann Machines
• The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding
• Performance Limits for Noisy Multi-Measurement Vector Problems
• A Deterministic and Generalized Framework for Unsupervised Learning with Restricted Boltzmann Machines
• Performance Analysis of Joint Active User Detection and Channel Estimation for Massive Connectivity
• Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing
• A positive temperature phase transition in random hypergraph 2-coloring
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• Unsourced Multiuser Sparse Regression Codes achieve the Symmetric MAC Capacity
• Generalized Approximate Message-Passing Decoder for Universal Sparse Superposition Codes
• Compressed Sensing of Approximately-Sparse Signals: Phase Transitions and Optimal Reconstruction
• Performance Limits with Additive Error Metrics in Noisy Multi-Measurement Vector Problem
• On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix
• Compressed sensing reconstruction using Expectation Propagation
• Non-adaptive pooling strategies for detection of rare faulty items
• Typical $l_1$-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
• Two-Part Reconstruction with Noisy-Sudocodes
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Prediction Errors for Penalized Regressions based on Generalized Approximate Message Passing
• Streaming Bayesian inference: theoretical limits and mini-batch approximate message-passing
• Blind Sensor Calibration using Approximate Message Passing
• Sample Distortion for Compressed Imaging
• Sparse approximation problem: how rapid simulated annealing succeeds and fails
• Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing
• Robust error correction for real-valued signals via message-passing decoding and spatial coupling
• Bayesian inference of infected patients in group testing with prevalence estimation
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Performance Trade-Offs in Multi-Processor Approximate Message Passing
• A Probabilistic Bayesian Approach to Recover $R_2^{\ast }$ map and Phase Images for Quantitative Susceptibility Mapping
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Scampi: a robust approximate message-passing framework for compressive imaging
• Neural-prior stochastic block model
• Phase transition in compressed sensing with horseshoe prior
• Estimator of Prediction Error Based on Approximate Message Passing for Penalized Linear Regression
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Large Deviations of Semi-supervised Learning in the Stochastic Block Model
• Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation
• Blind calibration for compressed sensing: State evolution and an online algorithm
• The phase diagram of compressed sensing with ${\ell }_0$-norm regularization
• Optimal Number of Measurements in a Linear System with Quadratically Decreasing SNR
• Reconstructing Sparse Signals via Greedy Monte-Carlo Search
• Many-User Multiple Access with Random User Activity: Achievability Bounds and Efficient Schemes
• Expectation propagation on the diluted Bayesian classifier
• Effect of global shrinkage parameter of horseshoe prior in compressed sensing