# All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation

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

## Key facts

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

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

- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (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)
- [Homophily modulates double descent generalization in graph convolution networks](https://mlsanity.com/paper/2212.13069/) (2022)
- [Statistical limits of dictionary learning: random matrix theory and the spectral replica method](https://mlsanity.com/paper/2109.06610/) (2021)
- [Statistical and Computational Phase Transitions in Group Testing](https://mlsanity.com/paper/2206.07640/) (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)
- [Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity](https://mlsanity.com/paper/2106.11950/) (2021)
- [Performance of Bayesian linear regression in a model with mismatch](https://mlsanity.com/paper/2107.06936/) (2021)
- [Bayes-optimal limits in structured PCA, and how to reach them](https://mlsanity.com/paper/2210.01237/) (2022)
- [Computational bottlenecks for denoising diffusions](https://mlsanity.com/paper/2503.08028/) (2025)
- [On maximum-likelihood estimation in the all-or-nothing regime](https://mlsanity.com/paper/2101.09994/) (2021)
- [Fundamental limits and algorithms for sparse linear regression with sublinear sparsity](https://mlsanity.com/paper/2101.11156/) (2021)
- [Bayesian Inference with Nonlinear Generative Models: Comments on Secure Learning](https://mlsanity.com/paper/2201.09986/) (2022)
- [Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise](https://mlsanity.com/paper/2302.03306/) (2023)
- [Inferring Change Points in High-Dimensional Regression via Approximate Message Passing](https://mlsanity.com/paper/2404.07864/) (2024)

## Abstract (arXiv)

We determine statistical and computational limits for estimation of a rank-one matrix (the spike) corrupted by an additive gaussian noise matrix, in a sparse limit, where the underlying hidden vector (that constructs the rank-one matrix) has a number of non-zero components that scales sub-linearly with the total dimension of the vector, and the signal-to-noise ratio tends to infinity at an appropriate speed. We prove explicit low-dimensional variational formulas for the asymptotic mutual information between the spike and the observed noisy matrix and analyze the approximate message passing algorithm in the sparse regime. For Bernoulli and Bernoulli-Rademacher distributed vectors, and when the sparsity and signal strength satisfy an appropriate scaling relation, we find all-or-nothing phase transitions for the asymptotic minimum and algorithmic mean-square errors. These jump from their maximum possible value to zero, at well defined signal-to-noise thresholds whose asymptotic values we determine exactly. In the asymptotic regime the statistical-to-algorithmic gap diverges indicating that sparse recovery is hard for approximate message passing.