A unifying tutorial on Approximate Message Passing

2021/05/05 by Oliver Y. Feng, Feng, Oliver Y., Ramji Venkataramanan +5 · 14 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Bayesian Modeling and Causal Inference #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Statistics Theory (math.ST) #cs.IT #math.IT #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.2105.02180

99 pages, 2 figures

arxiv created 2021/05/05 · openalex publication_date 2021/05/05 · arxiv updated 2021/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Over the last decade or so, Approximate Message Passing (AMP) algorithms have become extremely popular in various structured high-dimensional statistical problems. The fact that the origins of these techniques can be traced back to notions of belief propagation in the statistical physics literature lends a certain mystique to the area for many statisticians. Our goal in this work is to present the main ideas of AMP from a statistical perspective, to illustrate the power and flexibility of the AMP framework. Along the way, we strengthen and unify many of the results in the existing literature.

Cited by

• Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms
• Universality of AMP via Tree Pairings
• Approximate Message Passing for Quantum State Tomography
• Precise Dynamics of Diagonal Linear Networks: A Unifying Analysis by Dynamical Mean-Field Theory
• Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime
• Joint modeling of whole-genome sequencing data for human height via approximate message passing
• Asymptotic Analysis of Nonlinear One-Bit Precoding in Massive MIMO Systems via Approximate Message Passing
• Towards understanding Accelerated Stein Variational Gradient Flow -- Analysis of Generalized Bilinear Kernels for Gaussian target distributions
• Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling
• Sharp Trade-Offs in High-Dimensional Inference via 2-Level SLOPE
• Computational Thresholds in Multi-Modal Learning via the Spiked Matrix-Tensor Model
• The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks
• Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing
• Capacity-achieving sparse superposition codes with spatially coupled VAMP decoder

Related

• Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction
• Universality of Approximate Message Passing Algorithms
• Approximate Message Passing for general non-Symmetric random matrices
• Unifying Message Passing Algorithms Under the Framework of Constrained Bethe Free Energy Minimization
• A non-asymptotic distributional theory of approximate message passing for sparse and robust regression