# A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2022.

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

- [Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models](https://mlsanity.com/paper/2306.09251/) (2023)
- [A Sharp Convergence Theory for The Probability Flow ODEs of Diffusion Models](https://mlsanity.com/paper/2408.02320/) (2024)
- [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)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)
- [Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings](https://mlsanity.com/paper/2402.08543/) (2024)
- [A non-asymptotic distributional theory of approximate message passing for sparse and robust regression](https://mlsanity.com/paper/2401.03923/) (2024)
- [Unifying AMP Algorithms for Rotationally-Invariant Models](https://mlsanity.com/paper/2412.01574/) (2024)
- [Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models](https://mlsanity.com/paper/2211.03827/) (2022)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Heteroskedastic Tensor Clustering](https://mlsanity.com/paper/2311.02306/) (2023)
- [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)
- [Universality of first-order methods on random and deterministic matrices](https://mlsanity.com/paper/2604.11729/) (2026)
- [Decoupled Descent: Exact Test Error Tracking Via Approximate Message Passing](https://mlsanity.com/paper/2604.27883/) (2026)
- [Approximate Message Passing with Random Initialization for Phase Retrieval](https://mlsanity.com/paper/2608.01654/) (2026)

## Abstract (arXiv)

Approximate message passing (AMP) emerges as an effective iterative paradigm for solving high-dimensional statistical problems. However, prior AMP theory -- which focused mostly on high-dimensional asymptotics -- fell short of predicting the AMP dynamics when the number of iterations surpasses obig(fraclog nloglog nbig) (with n the problem dimension). To address this inadequacy, this paper develops a non-asymptotic framework for understanding AMP in spiked matrix estimation. Built upon new decomposition of AMP updates and controllable residual terms, we lay out an analysis recipe to characterize the finite-sample behavior of AMP in the presence of an independent initialization, which is further generalized to allow for spectral initialization. As two concrete consequences of the proposed analysis recipe: (i) when solving mathbbZ2 synchronization, we predict the behavior of spectrally initialized AMP for up to Obig(fracnpolylog nbig) iterations, showing that the algorithm succeeds without the need of a subsequent refinement stage (as conjectured recently by citetcelentano2021local); (ii) we characterize the non-asymptotic behavior of AMP in sparse PCA (in the spiked Wigner model) for a broad range of signal-to-noise ratio.