A unifying tutorial on Approximate Message Passing

2021/05/05 by Feng, Oliver Y., Venkataramanan, Ramji, Rush, Cynthia +1 · 9 citations
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2105.02180

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

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