# Finite Sample Analysis of Approximate Message Passing Algorithms

arXiv: https://arxiv.org/abs/1606.01800 · HTML: https://mlsanity.com/paper/1606.01800/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2016.

## Built on by (most cited first, 20 of 20)

- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensions](https://mlsanity.com/paper/2106.03791/) (2021)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime](https://mlsanity.com/paper/2509.24882/) (2025)
- [Fundamental computational limits of weak learnability in high-dimensional multi-index models](https://mlsanity.com/paper/2405.15480/) (2024)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Minimum ℓ1-norm interpolators: Precise asymptotics and multiple descent](https://mlsanity.com/paper/2110.09502/) (2021)
- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [Average case analysis of Lasso under ultra-sparse conditions](https://mlsanity.com/paper/2302.13093/) (2023)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Bayes optimal learning in high-dimensional linear regression with network side information](https://mlsanity.com/paper/2306.05679/) (2023)
- [Sharp Analysis of Power Iteration for Tensor PCA](https://mlsanity.com/paper/2401.01047/) (2024)
- [Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling](https://mlsanity.com/paper/2508.10782/) (2025)
- [A Convergence Analysis of Approximate Message Passing with Non-Separable Functions and Applications to Multi-Class Classification](https://mlsanity.com/paper/2402.08676/) (2024)
- [Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems](https://mlsanity.com/paper/2111.03237/) (2021)
- [Estimating Generalization Performance Along the Trajectory of Proximal SGD in Robust Regression](https://mlsanity.com/paper/2410.02629/) (2024)
- [Decoupled Descent: Exact Test Error Tracking Via Approximate Message Passing](https://mlsanity.com/paper/2604.27883/) (2026)
- [DAIF: A Data-Driven Intermediate Fusion Framework for Multimodal Supervised Learning via Approximate Message Passing](https://mlsanity.com/paper/2608.02769/) (2026)

## Abstract (arXiv)

Approximate message passing (AMP) refers to a class of efficient algorithms for statistical estimation in high-dimensional problems such as compressed sensing and low-rank matrix estimation. This paper analyzes the performance of AMP in the regime where the problem dimension is large but finite. For concreteness, we consider the setting of high-dimensional regression, where the goal is to estimate a high-dimensional vector β0 from a noisy measurement y=A β0 + w. AMP is a low-complexity, scalable algorithm for this problem. Under suitable assumptions on the measurement matrix A, AMP has the attractive feature that its performance can be accurately characterized in the large system limit by a simple scalar iteration called state evolution. Previous proofs of the validity of state evolution have all been asymptotic convergence results. In this paper, we derive a concentration inequality for AMP with i.i.d. Gaussian measurement matrices with finite size n × N. The result shows that the probability of deviation from the state evolution prediction falls exponentially in n. This provides theoretical support for empirical findings that have demonstrated excellent agreement of AMP performance with state evolution predictions for moderately large dimensions. The concentration inequality also indicates that the number of AMP iterations t can grow no faster than order fraclog nlog log n for the performance to be close to the state evolution predictions with high probability. The analysis can be extended to obtain similar non-asymptotic results for AMP in other settings such as low-rank matrix estimation.