# Approximate Message Passing algorithms for rotationally invariant matrices

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Aug 2020.

## Built on by (most cited first, 30 of 32)

- [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)
- [Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2112.04330/) (2021)
- [PCA Initialization for Approximate Message Passing in Rotationally Invariant Models](https://mlsanity.com/paper/2106.02356/) (2021)
- [The price of ignorance: how much does it cost to forget noise structure in low-rank matrix estimation?](https://mlsanity.com/paper/2205.10009/) (2022)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Preventing Model Collapse Under Overparametrization: Optimal Mixing Ratios for Interpolation Learning and Ridge Regression](https://mlsanity.com/paper/2509.22341/) (2025)
- [Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise](https://mlsanity.com/paper/2405.20993/) (2024)
- [Certified Data Removal Under High-dimensional Settings](https://mlsanity.com/paper/2505.07640/) (2025)
- [Householder Dice: A Matrix-Free Algorithm for Simulating Dynamics on Gaussian and Random Orthogonal Ensembles](https://mlsanity.com/paper/2101.07464/) (2021)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Theoretical Analysis of Leave-one-out Cross Validation for Non-differentiable Penalties under High-dimensional Settings](https://mlsanity.com/paper/2402.08543/) (2024)
- [Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods](https://mlsanity.com/paper/2405.13912/) (2024)
- [Memory Approximate Message Passing](https://mlsanity.com/paper/2106.02237/) (2021)
- [QCM-SGM+: Improved Quantized Compressed Sensing With Score-Based Generative Models](https://mlsanity.com/paper/2302.00919/) (2023)
- [ROTI-GCV: Generalized Cross-Validation for right-ROTationally Invariant Data](https://mlsanity.com/paper/2406.11666/) (2024)
- [Unifying AMP Algorithms for Rotationally-Invariant Models](https://mlsanity.com/paper/2412.01574/) (2024)
- [Bayes-optimal limits in structured PCA, and how to reach them](https://mlsanity.com/paper/2210.01237/) (2022)
- [Approximate Message Passing for Multi-Layer Estimation in Rotationally Invariant Models](https://mlsanity.com/paper/2212.01572/) (2022)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (2023)
- [Sufficient-Statistic Memory AMP](https://mlsanity.com/paper/2112.15327/) (2021)
- [Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling](https://mlsanity.com/paper/2508.10782/) (2025)
- [Sufficient Statistic Memory Approximate Message Passing](https://mlsanity.com/paper/2206.11674/) (2022)
- [Stability of a Generalized Debiased Lasso with Applications to Resampling-Based Variable Selection](https://mlsanity.com/paper/2405.03063/) (2024)
- [Learning with Restricted Boltzmann Machines: Asymptotics of AMP and GD in High Dimensions](https://mlsanity.com/paper/2505.18046/) (2025)
- [Orthogonal Approximate Message Passing with Optimal Spectral Initializations for Rectangular Spiked Matrix Models](https://mlsanity.com/paper/2512.19334/) (2025)
- [Random Multiplexing](https://mlsanity.com/paper/2512.24087/) (2025)
- [Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems](https://mlsanity.com/paper/2111.03237/) (2021)
- [Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise](https://mlsanity.com/paper/2302.03306/) (2023)
- [Asymptotic Analysis of Nonlinear One-Bit Precoding in Massive MIMO Systems via Approximate Message Passing](https://mlsanity.com/paper/2509.13955/) (2025)

## Abstract (arXiv)

Approximate Message Passing (AMP) algorithms have seen widespread use across a variety of applications. However, the precise forms for their Onsager corrections and state evolutions depend on properties of the underlying random matrix ensemble, limiting the extent to which AMP algorithms derived for white noise may be applicable to data matrices that arise in practice. In this work, we study more general AMP algorithms for random matrices W that satisfy orthogonal rotational invariance in law, where W may have a spectral distribution that is different from the semicircle and Marcenko-Pastur laws characteristic of white noise. The Onsager corrections and state evolutions in these algorithms are defined by the free cumulants or rectangular free cumulants of the spectral distribution of W. Their forms were derived previously by Opper, cCakmak, and Winther using non-rigorous dynamic functional theory techniques, and we provide rigorous proofs. Our motivating application is a Bayes-AMP algorithm for Principal Components Analysis, when there is prior structure for the principal components (PCs) and possibly non-white noise. For sufficiently large signal strengths and any non-Gaussian prior distributions for the PCs, we show that this algorithm provably achieves higher estimation accuracy than the sample PCs.