The dynamics of message passing on dense graphs, with applications to compressed sensing

Abstract

Approximate message passing algorithms proved to be extremely effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper we provide the first rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with large number of short loops in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory.

41 pages

References in corpus (4)

• Message Passing Algorithms for Compressed Sensing
• Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• A typical reconstruction limit of compressed sensing based on Lp-norm minimization

Cited by in corpus (159)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Massive Connectivity with Massive MIMO-Part I: Device Activity Detection and Channel Estimation
• Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air
• Sparse Signal Processing for Grant-Free Massive Connectivity: A Future Paradigm for Random Access Protocols in the Internet of Things
• Expectation-Maximization Gaussian-Mixture Approximate Message Passing
• AMP-Inspired Deep Networks for Sparse Linear Inverse Problems
• Statistical physics of inference: Thresholds and algorithms
• Sparse Activity Detection for Massive Connectivity
• Bayes-Optimal Joint Channel-and-Data Estimation for Massive MIMO with Low-Precision ADCs
• Bilinear Generalized Approximate Message Passing
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Trainable ISTA for Sparse Signal Recovery
• Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior
• Non-Bayesian Activity Detection, Large-Scale Fading Coefficient Estimation, and Unsourced Random Access with a Massive MIMO Receiver
• An Online Plug-and-Play Algorithm for Regularized Image Reconstruction
• Dynamic Compressive Sensing of Time-Varying Signals via Approximate Message Passing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Robust subspace clustering
• Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
• Statistical physics-based reconstruction in compressed sensing
• Turbo Compressed Sensing with Partial DFT Sensing Matrix
• A GAMP Based Low Complexity Sparse Bayesian Learning Algorithm
• Efficient High-Dimensional Inference in the Multiple Measurement Vector Problem
• SPARCs for Unsourced Random Access
• Massive Connectivity with Massive MIMO-Part II: Achievable Rate Characterization
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Message-Passing Estimation from Quantized Samples
• Capacity-achieving Sparse Superposition Codes via Approximate Message Passing Decoding
• Approximate message-passing decoder and capacity-achieving sparse superposition codes
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• A Message-Passing Receiver for BICM-OFDM over Unknown Clustered-Sparse Channels
• Mean-field message-passing equations in the Hopfield model and its generalizations
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Compressive Hyperspectral Imaging via Approximate Message Passing
• Compressive Imaging via Approximate Message Passing with Image Denoising
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Decentralized Equalization with Feedforward Architectures for Massive MU-MIMO
• On Convergence of Approximate Message Passing
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Linear Precoding for the MIMO Multiple Access Channel with Finite Alphabet Inputs and Statistical CSI
• A Factor Graph Approach to Joint OFDM Channel Estimation and Decoding in Impulsive Noise Environments
• The Mutual Information in Random Linear Estimation
• Near optimal compressed sensing without priors: Parametric SURE Approximate Message Passing
• Message-passing algorithms for synchronization problems over compact groups
• Fundamental limits of many-user MAC with finite payloads and fading
• Hybrid Approximate Message Passing
• A Theory of Solving TAP Equations for Ising Models with General Invariant Random Matrices
• On the Performance of Turbo Signal Recovery with Partial DFT Sensing Matrices
• 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
• Statistical and computational phase transitions in spiked tensor estimation
• 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
• Reconstruction of Signals Drawn from a Gaussian Mixture from Noisy Compressive Measurements
• Computational Barriers to Estimation from Low-Degree Polynomials
• Lossy Compression via Sparse Linear Regression: Computationally Efficient Encoding and Decoding
• Finite Sample Analysis of Approximate Message Passing Algorithms
• Typology of phase transitions in Bayesian inference problems
• Plug-in Estimation in High-Dimensional Linear Inverse Problems: A Rigorous Analysis
• Replica Analysis and Approximate Message Passing Decoder for Superposition Codes
• Sensitivity of ${\ell }_1$ minimization to parameter choice
• Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
• Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
• Variational Free Energies for Compressed Sensing
• Disordered Systems Insights on Computational Hardness
• Entropy landscape of solutions in the binary perceptron problem
• Bilinear Recovery using Adaptive Vector-AMP
• Multi-Layer Generalized Linear Estimation
• Convolutional Approximate Message-Passing
• Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)
• Approximate Message Passing Algorithm with Universal Denoising and Gaussian Mixture Learning
• Intensity-only optical compressive imaging using a multiply scattering material and a double phase retrieval approach
• The committee machine: Computational to statistical gaps in learning a two-layers neural network
• Multi-Layer Bilinear Generalized Approximate Message Passing
• MIMO-OFDM-Based Massive Connectivity With Frequency Selectivity Compensation
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• On the Performance of Mismatched Data Detection in Large MIMO Systems
• Glassy nature of the hard phase in inference problems
• Modulated Sparse Superposition Codes for the Complex AWGN Channel
• An Approximate Message Passing Framework for Side Information
• Performance Analysis of Approximate Message Passing for Distributed Compressed Sensing
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Memory-free dynamics for the TAP equations of Ising models with arbitrary rotation invariant ensembles of random coupling matrices
• Statistical Mechanics of High-Dimensional Inference
• Coded Demixing for Unsourced Random Access
• Performance Limits for Noisy Multi-Measurement Vector Problems
• Joint Device Activity Detection, Channel Estimation and Signal Detection for Massive Grant-free Access via BiGAMP
• Belief Propagation with Quantum Messages for Quantum-Enhanced Classical Communications
• Approximate Survey Propagation for Statistical Inference
• The Error Probability of Sparse Superposition Codes with Approximate Message Passing Decoding
• Phase transitions and optimal algorithms in high-dimensional Gaussian mixture clustering
• Optimal Quantization for Compressive Sensing under Message Passing Reconstruction
• Learning curves for the multi-class teacher-student perceptron
• Precise Performance Analysis of the Box-Elastic Net under Matrix Uncertainties
• Gaussian Universality of Perceptrons with Random Labels
• Performance Analysis of Joint Active User Detection and Channel Estimation for Massive Connectivity
• Optimizing Mean Field Spin Glasses with External Field
• Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing
• Decoding from Pooled Data: Phase Transitions of Message Passing
• Statistical mechanics of low-rank tensor decomposition
• Unsourced Multiuser Sparse Regression Codes achieve the Symmetric MAC Capacity
• Phase transition in random tensors with multiple independent spikes
• Rigorous dynamical mean field theory for stochastic gradient descent methods
• Generalized Approximate Message-Passing Decoder for Universal Sparse Superposition Codes
• Compressed Sensing of Approximately-Sparse Signals: Phase Transitions and Optimal Reconstruction
• A Dynamical Mean-Field Theory for Learning in Restricted Boltzmann Machines
• On the Universality of Noiseless Linear Estimation with Respect to the Measurement Matrix
• Performance Limits with Additive Error Metrics in Noisy Multi-Measurement Vector Problem
• Near-Optimal Coding for Many-user Multiple Access Channels
• Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting
• TARM: A Turbo-type Algorithm for Affine Rank Minimization
• Compressed sensing radar detectors under the row-orthogonal design model: a statistical mechanics perspective
• Gaussian Approximation of Quantization Error for Estimation from Compressed Data
• Approximate Message Passing with Parameter Estimation for Heavily Quantized Measurements
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Bayes-Optimal Estimation in Generalized Linear Models via Spatial Coupling
• Statistical mechanics approach to 1-bit compressed sensing
• Two-Part Reconstruction with Noisy-Sudocodes
• On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
• Device Activity Detection and Channel Estimation for Millimeter-Wave Massive MIMO
• Simultaneous Active and Passive Information Transfer for RIS-Aided MIMO Systems: Iterative Decoding and Evolution Analysis
• Mismatched Data Detection in Massive MU-MIMO
• Blind Sensor Calibration using Approximate Message Passing
• Streaming Bayesian inference: theoretical limits and mini-batch approximate message-passing
• Exact solution to the random sequential dynamics of a message passing algorithm
• Compressive Computed Tomography Reconstruction through Denoising Approximate Message Passing
• Robust error correction for real-valued signals via message-passing decoding and spatial coupling
• Sample Distortion for Compressed Imaging
• Approximate Message Passing with Rigorous Guarantees for Pooled Data and Quantitative Group Testing
• Analysis of Bayesian Inference Algorithms by the Dynamical Functional Approach
• On the TAP equations via the cavity approach in the generic mixed $p$-spin models
• Performance Trade-Offs in Multi-Processor Approximate Message Passing
• Optimal Data Detection and Signal Estimation in Systems with Input Noise
• Efficient Massive Machine Type Communication (mMTC) via AMP
• A Probabilistic Bayesian Approach to Recover $R_2^{\ast }$ map and Phase Images for Quantitative Susceptibility Mapping
• On the best choice of Lasso program given data parameters
• Scampi: a robust approximate message-passing framework for compressive imaging
• Optimum GSSK Transmission in Massive MIMO Systems Using the Box-LASSO Decoder
• Detangling robustness in high dimensions: composite versus model-averaged estimation
• Semi-analytic approximate stability selection for correlated data in generalized linear models
• Compressed sensing with l0-norm: statistical physics analysis and algorithms for signal recovery
• Sampling from Mean-Field Gibbs Measures via Diffusion Processes
• Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation
• The planted XY model: thermodynamics and inference
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• Performance Analysis of Cell-Free Massive MIMO Systems with Massive Connectivity
• Critical Behavior and Universality Classes for an Algorithmic Phase Transition in Sparse Reconstruction
• Sparse Message Passing Based Preamble Estimation for Crowded M2M Communications
• The phase diagram of compressed sensing with ${\ell }_0$-norm regularization
• Statistical mechanics analysis of general multi-dimensional knapsack problems
• Optimal Number of Measurements in a Linear System with Quadratically Decreasing SNR
• Asymptotic Performance Prediction for ADMM-Based Compressed Sensing
• Precise Error Rates for Computationally Efficient Testing
• Linear Operator Approximate Message Passing (OpAMP)
• Many-User Multiple Access with Random User Activity: Achievability Bounds and Efficient Schemes
• Planted matching problems on random hypergraphs
• Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions
• Algebra of L-banded Matrices