2021

A unifying tutorial on Approximate Message Passing

Feng, Oliver Y., Venkataramanan, Ramji, Rush, Cynthia et al.

Understand

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.

Built on

Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation
Original
Yang, G. (2019) · 1902
Earlier work this paper cites.
Fundamental barriers to high-dimensional regression with convex penalties
Original
Celentano, M. and Montanari, A. (2019) · 1903
Earlier work this paper cites.
High-dimensional principal component analysis with heterogeneous missingness
Original
Zhu, Z., Wang, T. and Samworth, R. J. (2019) · 1906
Earlier work this paper cites.
Statistical and computational trade-offs in estimation of sparse principal components
Wang, T., Berthet, Q. and Samworth, R. J. (2016) · 1930
Earlier work this paper cites.
Proc. Natl. Acad. Sci. U.S.A. , 33
Hsu, P. L. and Robbins, H. (1947). Complete convergence and the law of large numbers · 1947
Earlier work this paper cites.
Proc. Third Berkeley Symp. Math. Statist. Prob. , 1
Robbins, H. (1956). An empirical Bayes approach to statistics · 1956
Earlier work this paper cites.
Ann. Math. Statist. , 35
Huber, P. J. (1964). Robust estimation of a location parameter · 1964
Earlier work this paper cites.
Ann. Statist. , 1
Brown, L. D. and Purves, R. (1973). Measurable selections of extrema · 1973
Earlier work this paper cites.
Ann. Statist. , 1
Huber, P. J. (1973). Robust regression: asymptotics, conjectures and Monte Carlo · 1973
Earlier work this paper cites.
Academic Press, London
Prékopa, A. (1980). Logarithmic concave measures and related topics. In Stochastic Programming (Proc. Internat. Conf., Univ. Oxford, Oxford, 1974, M. A. H. Dempster ed.) , pp. 63–82 · 1974
Earlier work this paper cites.
Wiley, New York
Serfling, R. J. (1980). Approximation Theorems of Mathematical Statistics · 1980
Earlier work this paper cites.
On the existence of maximum likelihood estimates in logistic regression models
Albert, A. and Anderson J. A. (1984) · 1984
Earlier work this paper cites.
Ann. Statist. , 12
Portnoy, S. (1984). Asymptotic behavior of M M -estimators of p p regression parameters when p 2 / n p^{2}/n is large. I. Consistency · 1984
Earlier work this paper cites.
Ann. Statist. , 13
Portnoy, S. (1985). Asymptotic behavior of M M -estimators of p p regression parameters when p 2 / n p^{2}/n is large; II. Normal approximation · 1985
Earlier work this paper cites.
World Scientific Lecture Notes in Physics, 9
Mézard, M., Parisi, G., Virasoro, M. A. (1987). Spin Glass Theory and Beyond · 1987
Earlier work this paper cites.
Ann. Statist. , 16
Portnoy, S. (1988). Asymptotic behavior of likelihood methods for exponential families when the number of parameters tends to infinity · 1988
Earlier work this paper cites.
Generalized Linear Models , 2nd edition
McCullagh, P. and Nelder, J. A. (1989) · 1989
Earlier work this paper cites.
Minimax risk over l p l_{p} balls for l q l_{q} error
Donoho, D. L. and Johnstone, I. M. (1994) · 1994
Earlier work this paper cites.
Am. Math. Mon. , 101
Gordon, L. (1994). A stochastic approach to the gamma function · 1994
Earlier work this paper cites.
Geometric Measure Theory
Federer, H. (1996) · 1996
Earlier work this paper cites.
Regression shrinkage and selection via the Lasso
Tibshirani, R. (1996) · 1996
Earlier work this paper cites.
Springer–Verlag, New York
Kallenberg, O. (1997). Foundations of Modern Probability · 1997
Earlier work this paper cites.
World Scientific, Singapore
Pace, L. and Salvan, A. (1997). Principles of Statistical Inference: From a Neo-Fisherian Perspective · 1997
Earlier work this paper cites.
Princeton University Press, Princeton
Rockafellar, R. T. (1997). Convex Analysis · 1997
Earlier work this paper cites.
Principles of Real Analysis , 3rd edition
Aliprantis, C. D. and Burkinshaw, O. (1998) · 1998
Earlier work this paper cites.
Finding a large hidden clique in a random graph
Alon, N., Krivelevich, M. and Sudakov, B. (1998) · 1998
Earlier work this paper cites.
Minimax estimation via wavelet shrinkage
Donoho, D. L. and Johnstone, I. M. (1998) · 1998
Earlier work this paper cites.
Cambridge University Press, Cambridge
van der Vaart, A. W. (1998). Asymptotic Statistics · 1998
Earlier work this paper cites.
Cambridge University Press, Cambridge
Dudley, R. M. (2002). Real Analysis and Probability , 2nd edition · 2002
Earlier work this paper cites.
A precise high-dimensional asymptotic theory for boosting and minimum- ℓ 1 \ell_{1} -norm interpolated classifiers
Original
Liang, T. and Sur, P. (2020) · 2002
Earlier work this paper cites.
A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors
Tanaka, T. (2002) · 2002
Earlier work this paper cites.
Bakhshizadeh, M., Maleki, A. and de la Pena, V. H. (2020). Sharp concentration results for heavy-tailed distributions. Available at https://arxiv.org/pdf/2003.13819.pdf
Original
2003
Earlier work this paper cites.
J. Mach. Learn. Res. , 3
Blei, D. M., Ng, A. Y. and Jordan, M. I. (2003). Latent Dirichlet allocation · 2003
Earlier work this paper cites.
J. Comput. Graph. Statist. , 12
Jolliffe, I. T., Trendafilov, N. T. and Uddin, M. (2003). A modified principal component technique based on the LASSO · 2003
Earlier work this paper cites.
Topics in Optimal Transportation. Graduate Studies in Mathematics
Villani, C. (2003) · 2003
Earlier work this paper cites.
Random Matrices , 3rd edition
Mehta, M. L. (2004) · 2004
Earlier work this paper cites.
Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
Baik, J., Ben Arous, G. and Péché, S. (2005) · 2005
Earlier work this paper cites.
Expectation consistent approximate inference
Opper, M. and Winther, O. (2005) · 2005
Earlier work this paper cites.
Eigenvalues of large sample covariance matrices of spiked population models
Baik, J. and Silverstein, J. W. (2006) · 2006
Earlier work this paper cites.
All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation
Original
Barbier, J., Macris, N. and Rush, C. (2020) · 2006
Earlier work this paper cites.
High Dimensional Statistical Inference and Random Matrices
Johnstone, I. M. (2006) · 2006
Earlier work this paper cites.
J. Comput. Graph. Statist. , 15
Zou, H., Hastie, T. and Tibshirani, R. (2006). Sparse principal component analysis · 2006
Earlier work this paper cites.
The largest eigenvalue of rank one deformation of large Wigner matrices
Féral, D. and Péché, S. (2007) · 2007
Earlier work this paper cites.
Asymptotics of sample eigenstructure for a large dimensional spiked covariance model
Paul, D. (2007) · 2007
Earlier work this paper cites.
A tutorial on spectral clustering
von Luxburg, U. (2007) · 2007
Earlier work this paper cites.
Approximate message passing algorithms for rotationally invariant matrices
Original
Fan, Z. (2020) · 2008
Earlier work this paper cites.
Available at https://arxiv.org/pdf/2008.03326.pdf
Original
Mondelli, M., Thrampoulidis, C. and Venkataramanan, R. (2020). Optimal combination of linear and spectral estimators for generalized linear models · 2008
Earlier work this paper cites.
A fast iterative shrinkage-thresholding algorithm for linear inverse problems
Beck, A. and Teboulle, M. (2009) · 2009
Earlier work this paper cites.
Candès, E. J. and Recht, B. (2009). Exact matrix completion via convex optimization. Found. Comput. Math. , 9
2009
Earlier work this paper cites.

Similar

The largest eigenvalues of finite rank deformation of large Wigner matrices: convergence and nonuniversality of the fluctuations
Capitaine, M., Donati-Martin, C. and Féral, D. (2009) · 2009
Cited alongside, same era.
Message-passing algorithms for compressed sensing
Donoho, D. L., Maleki, A. and Montanari, A. (2009) · 2009
Cited alongside, same era.
Robust Statistics , 2nd edition
Huber, P. J. and Ronchetti, E. (2009) · 2009
Cited alongside, same era.
On consistency and sparsity for principal components analysis in high dimensions
Johnstone, I. M. and Lu, A. Y. (2009) · 2009
Cited alongside, same era.
Probabilistic Graphical Models: Principles and Techniques
Koller, D. and Friedman, N. (2009) · 2009
Cited alongside, same era.
Information, Physics, and Computation
Mézard, M. and Montanari, M. (2009) · 2009
Cited alongside, same era.
Asymptotic analysis of MAP estimation via the replica method and applications to compressed sensing
Rangan, S., Fletcher, A. K. and Goyal, V. K. (2009) · 2009
Cited alongside, same era.
A survey of collaborative filtering techniques
Su, X. and Khoshgoftaar, T. M. (2009) · 2009
Cited alongside, same era.
Introduction to Nonparametric Estimation
Tsybakov, A. B. (2009) · 2009
Cited alongside, same era.
Optimal Transport, Old and New
Villani, C. (2009) · 2009
Cited alongside, same era.
An Introduction to Random Matrices
Anderson, G., Guionnet, A. and Zeitouni, O. (2010) · 2010
Cited alongside, same era.
Spectral Analysis of Large Dimensional Random Matrices
Bai, Z. and Silverstein, J. (2010) · 2010
Cited alongside, same era.

Then

Mutual information for symmetric rank-one matrix estimation: a proof of the replica formula
Barbier, J., Dia, M., Macris, N., Krzakala, F., Lesieur, T. and Zdeborová, L. (2016) · 2016
Later among the works it cites.
Asymptotic mutual information for the balanced binary stochastic block model
Deshpande, Y., Abbe, E. and Montanari, A. (2016) · 2016
Later among the works it cites.
High dimensional robust M-estimation: asymptotic variance via approximate message passing
Donoho, D. and Montanari, A. (2016) · 2016
Later among the works it cites.
Phase transitions and sample complexity in Bayes optimal matrix factorization
Kabashima, Y., Krzakala, F., Mézard, M., Sakata, A. and Zdeborová, L. (2016) · 2016
Later among the works it cites.
Non-negative principal component analysis: Message passing algorithms and sharp asymptotics
Montanari, A. and Richard, E. (2016) · 2016
Later among the works it cites.
A theory of solving TAP equations for Ising models with general invariant random matrices
Opper, M., Çakmak, B. and Winther, O. (2016) · 2016
Later among the works it cites.
Fixed points of generalized approximate message passing with arbitrary matrices
Rangan, S., Schniter, P., Riegler, E., Fletcher, A. K. and Cevher, V. (2016) · 2016
Later among the works it cites.
Vector approximate message passing for the generalized linear model
Schniter, P., Rangan, S. and Fletcher, A. K. (2016) · 2016
Later among the works it cites.
SLOPE is adaptive to unknown sparsity and asymptotically minimax
Su, W. and Candès, E. (2016) · 2016
Later among the works it cites.
Statistical physics of inference: thresholds and algorithms
Zdeborová, L. and Krzakala, F. (2016) · 2016
Later among the works it cites.
Approximate message-passing decoder and capacity achieving sparse superposition codes
Barbier, J. and Krzakala, F. (2017) · 2017
Later among the works it cites.
The LASSO risk for Gaussian matrices
Bayati, M. and Montanari, A. (2012) · 2017
Later among the works it cites.
Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
Lesieur, T., Krzakala, F. and Zdeborová, L. (2017) · 2017
Later among the works it cites.
Learned D-AMP: Principled neural network based compressive image recovery
Metzler, C., Mousavi, A. and Baraniuk, R. (2017) · 2017
Later among the works it cites.
Capacity-achieving sparse superposition codes via approximate message passing decoding
Rush, C., Greig, A. and Venkataramanan, R. (2017) · 2017
Later among the works it cites.
False discoveries occur early on the LASSO path
Su, W., Bogdan, M. and Candès, E. (2017) · 2017
Later among the works it cites.
The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled chi-square
Sur, P., Chen, Y. and Candès, E. J. (2017) · 2017
Later among the works it cites.
SLOPE meets LASSO: improved oracle bounds and optimality
Bellec, P. C., Lecué, G. and Tsybakov, A. B. (2018) · 2018
Later among the works it cites.
Shrinkage Estimation
Fourdrinier, D., Strawderman, W. E. and Wells, M. T. (2018) · 2018
Later among the works it cites.
PCA in high dimensions: an orientation
Johnstone, I. M. and Paul, D. (2018) · 2018
Later among the works it cites.
Kuchibhotla, A. and Chakrabortty A. (2018). Moving beyond sub-Gaussianity in high-dimensional statistics: applications in covariance estimation and linear regression. Available at https://arxiv.org/pdf/1804.02605.pdf
Original
2018
Later among the works it cites.
The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
Original
Miolane, L. and Montanari, A. (2018) · 2018
Later among the works it cites.
Consistent parameter estimation for LASSO and approximate message passing
Mousavi, A., Maleki, A., Baraniuk, R. G. (2018) · 2018
Later among the works it cites.
Optimality and sub-optimality of PCA I: Spiked random matrix models
Perry, A., Wein, A. S., Bandeira, A. S. and Moitra, A. (2018) · 2018
Later among the works it cites.
Iterative reconstruction of rank-one matrices in noise
Rangan, S. and Fletcher, A. K. (2018) · 2018
Later among the works it cites.
IEEE Trans. Inf. Theory , 64
Rush, C. and Venkataramanan, R. (2018). Finite sample analysis of approximate message passing algorithms · 2018
Later among the works it cites.
IEEE Trans. Inf. Theory , 64
Thrampoulidis, C., Abbasi, E. and Hassibi, B. (2018). Precise error analysis of regularized M M -estimators in high dimensions · 2018
Later among the works it cites.
Optimal errors and phase transitions in high-dimensional generalized linear models
Barbier, J., Krzakala, F., Macris, N., Miolane, L., and Zdeborová, L. (2019) · 2019
Later among the works it cites.
Memory-free dynamics for the Thouless–Anderson–Palmer equations of Ising models with arbitrary rotation-invariant ensembles of random coupling matrices
Çakmak, B. and Opper, M. (2019) · 2019
Later among the works it cites.
Fundamental limits of symmetric low-rank matrix estimation
Lelarge, M. and Miolane, L. (2019) · 2019
Later among the works it cites.
Optimization-based AMP for phase retrieval: the impact of initialization and ℓ 2 \ell_{2} regularization
Ma, J., Xu, J. and Maleki, A. (2019) · 2019
Later among the works it cites.
Analysis of approximate message passing with non-separable denoisers and Markov random field priors
Ma, Y., Rush, C. and Baron, D. (2019) · 2019
Later among the works it cites.
Asymptotics of MAP inference in deep networks
Pandit, P., Sahraee, M., Rangan, S. and Fletcher, A. K. (2019) · 2019
Later among the works it cites.
The replica-symmetric prediction for random linear estimation with Gaussian matrices is exact
Reeves, G. and Pfister, H. D. (2019) · 2019
Later among the works it cites.
State evolution for approximate message passing with non-separable functions
Berthier, R., Montanari, A. and Nguyen, P.-M. (2020) · 2020
Later among the works it cites.
Ann. Statist. , 48
Candès, E. J. and Sur, P. (2020). The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression · 2020
Later among the works it cites.
The estimation error of general first order methods
Celentano, M., Montanari, A. and Wu, Y. (2020) · 2020
Later among the works it cites.
Generalization error of generalized linear models in high dimensions
Emami, M., Sahraee-Ardakan, M., Pandit, P., Rangan, S. and Fletcher, A. K. (2020) · 2020
Later among the works it cites.
Sparse principal component analysis via axis-aligned random projections
Gataric, M., Wang, T. and Samworth, R. J. (2020) · 2020
Later among the works it cites.
Proc. Mach. Learn. Res. , 130
Mondelli, M. and Venkataramanan, R. (2020). Approximate message passing with spectral initialization for generalized linear models · 2020
Later among the works it cites.
Springer–Verlag, New York
Panaretos, V. M. and Zemel, Y. (2020). An Invitation to Statistics in Wasserstein Space · 2020
Later among the works it cites.
Inference with deep generative priors in high dimensions
Pandit, P., Sahraee-Ardakan, M., Rangan, S., Schniter, P. and Fletcher, A. K. (2020) · 2020
Later among the works it cites.
A simple derivation of AMP and its state evolution via first-order cancellation
Schniter, P. (2020) · 2020
Later among the works it cites.
Rigorous dynamics of expectation-propagation-based signal recovery from unitarily invariant measurements
Takeuchi, K. (2020) · 2020
Later among the works it cites.
Algorithmic analysis and statistical estimation of SLOPE via approximate message passing
Bu, Z., Klusowski, J., Rush, C. and Su, W. (2021) · 2021
Closest in time.
Universality of approximate message passing algorithms
Chen, W-K. and Lam, W-K. (2021) · 2021
Closest in time.
Bounding distributional errors via density ratios
Dümbgen, L., Samworth, R. J. and Wellner, J. A. (2021) · 2021
Closest in time.
Estimation of low-rank matrices via approximate message passing
Montanari, A. and Venkataramanan, R. (2021) · 2021
Closest in time.
Orthogonal AMP
Ma, J. and Ping, L. (2017) · 2033
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…