# Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula

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

## Key facts

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

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

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective](https://mlsanity.com/paper/2308.14085/) (2023)
- [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)
- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Statistical limits of dictionary learning: random matrix theory and the spectral replica method](https://mlsanity.com/paper/2109.06610/) (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)
- [Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity](https://mlsanity.com/paper/2106.11950/) (2021)
- [Statistical Advantage of Softmax Attention: Insights from Single-Location Regression](https://mlsanity.com/paper/2509.21936/) (2025)
- [Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise](https://mlsanity.com/paper/2405.20993/) (2024)
- [Rank-one matrix estimation: analytic time evolution of gradient descent dynamics](https://mlsanity.com/paper/2105.12257/) (2021)
- [Predicting Different Types of Subtle Toxicity in Unhealthy Online Conversations](https://mlsanity.com/paper/2106.03952/) (2021)
- [On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariance](https://mlsanity.com/paper/2411.01974/) (2024)
- [Bayes-optimal limits in structured PCA, and how to reach them](https://mlsanity.com/paper/2210.01237/) (2022)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)
- [Asymptotic Dynamics of Alternating Minimization for Bilinear Regression](https://mlsanity.com/paper/2402.04751/) (2024)
- [Fundamental limits of Non-Linear Low-Rank Matrix Estimation](https://mlsanity.com/paper/2403.04234/) (2024)
- [Sparse corruption in low-rank matrix inference: the PCA benchmark](https://mlsanity.com/paper/2511.11927/) (2025)
- [Asymptotic Normality of Log Likelihood Ratio and Fundamental Limit of the Weak Detection for Spiked Wigner Matrices](https://mlsanity.com/paper/2203.00821/) (2022)
- [Subspace clustering in high-dimensions: Phase transitions & Statistical-to-Computational gap](https://mlsanity.com/paper/2205.13527/) (2022)
- [Detection problems in the spiked matrix models](https://mlsanity.com/paper/2301.05331/) (2023)
- [Orthogonal Approximate Message Passing with Optimal Spectral Initializations for Rectangular Spiked Matrix Models](https://mlsanity.com/paper/2512.19334/) (2025)
- [On maximum-likelihood estimation in the all-or-nothing regime](https://mlsanity.com/paper/2101.09994/) (2021)
- [Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise](https://mlsanity.com/paper/2302.03306/) (2023)
- [Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise](https://mlsanity.com/paper/2510.08541/) (2025)
- [Orthogonal Approximate Message Passing Algorithms for Rectangular Spiked Matrix Models with Rotationally Invariant Noise](https://mlsanity.com/paper/2602.03283/) (2026)

## Abstract (arXiv)

Factorizing low-rank matrices has many applications in machine learning and statistics. For probabilistic models in the Bayes optimal setting, a general expression for the mutual information has been proposed using heuristic statistical physics computations, and proven in few specific cases. Here, we show how to rigorously prove the conjectured formula for the symmetric rank-one case. This allows to express the minimal mean-square-error and to characterize the detectability phase transitions in a large set of estimation problems ranging from community detection to sparse PCA. We also show that for a large set of parameters, an iterative algorithm called approximate message-passing is Bayes optimal. There exists, however, a gap between what currently known polynomial algorithms can do and what is expected information theoretically. Additionally, the proof technique has an interest of its own and exploits three essential ingredients: the interpolation method introduced in statistical physics by Guerra, the analysis of the approximate message-passing algorithm and the theory of spatial coupling and threshold saturation in coding. Our approach is generic and applicable to other open problems in statistical estimation where heuristic statistical physics predictions are available.