# Estimation of Low-Rank Matrices via Approximate Message Passing

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2017.

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

- [Learning Mixtures of Gaussians Using the DDPM Objective](https://mlsanity.com/paper/2307.01178/) (2023)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2112.04330/) (2021)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [PCA Initialization for Approximate Message Passing in Rotationally Invariant Models](https://mlsanity.com/paper/2106.02356/) (2021)
- [Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods](https://mlsanity.com/paper/2202.08907/) (2022)
- [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)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity](https://mlsanity.com/paper/2106.11950/) (2021)
- [Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery](https://mlsanity.com/paper/2502.01583/) (2025)
- [Minimum ℓ1-norm interpolators: Precise asymptotics and multiple descent](https://mlsanity.com/paper/2110.09502/) (2021)
- [Deflated HeteroPCA: Overcoming the curse of ill-conditioning in heteroskedastic PCA](https://mlsanity.com/paper/2303.06198/) (2023)
- [Approximate Message Passing for the Matrix Tensor Product Model](https://mlsanity.com/paper/2306.15580/) (2023)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)
- [Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise](https://mlsanity.com/paper/2405.20993/) (2024)
- [Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods](https://mlsanity.com/paper/2405.13912/) (2024)
- [Precise Error Rates for Computationally Efficient Testing](https://mlsanity.com/paper/2311.00289/) (2023)
- [Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions](https://mlsanity.com/paper/2407.03522/) (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)
- [Mixed Regression via Approximate Message Passing](https://mlsanity.com/paper/2304.02229/) (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)
- [Fundamental limits of Non-Linear Low-Rank Matrix Estimation](https://mlsanity.com/paper/2403.04234/) (2024)
- [Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling](https://mlsanity.com/paper/2508.10782/) (2025)
- [Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap](https://mlsanity.com/paper/2205.13527/) (2022)
- [Gradient flow on extensive-rank positive semi-definite matrix denoising](https://mlsanity.com/paper/2303.09474/) (2023)
- [A Convergence Analysis of Approximate Message Passing with Non-Separable Functions and Applications to Multi-Class Classification](https://mlsanity.com/paper/2402.08676/) (2024)

## Abstract (arXiv)

Consider the problem of estimating a low-rank matrix when its entries are perturbed by Gaussian noise. If the empirical distribution of the entries of the spikes is known, optimal estimators that exploit this knowledge can substantially outperform simple spectral approaches. Recent work characterizes the asymptotic accuracy of Bayes-optimal estimators in the high-dimensional limit. In this paper we present a practical algorithm that can achieve Bayes-optimal accuracy above the spectral threshold. A bold conjecture from statistical physics posits that no polynomial-time algorithm achieves optimal error below the same threshold (unless the best estimator is trivial). Our approach uses Approximate Message Passing (AMP) in conjunction with a spectral initialization. AMP algorithms have proved successful in a variety of statistical estimation tasks, and are amenable to exact asymptotic analysis via state evolution. Unfortunately, state evolution is uninformative when the algorithm is initialized near an unstable fixed point, as often happens in low-rank matrix estimation. We develop a new analysis of AMP that allows for spectral initializations. Our main theorem is general and applies beyond matrix estimation. However, we use it to derive detailed predictions for the problem of estimating a rank-one matrix in noise. Special cases of this problem are closely related---via universality arguments---to the network community detection problem for two asymmetric communities. For general rank-one models, we show that AMP can be used to construct confidence intervals and control false discovery rate. We provide illustrations of the general methodology by considering the cases of sparse low-rank matrices and of block-constant low-rank matrices with symmetric blocks (we refer to the latter as to the `Gaussian Block Model').