# Bayes-optimal limits in structured PCA, and how to reach them

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 106 references that are in the map.
- First posted on arXiv 3 Oct 2022.

## Builds on (most cited first, 25 of 25)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [A modern maximum-likelihood theory for high-dimensional logistic regression](https://mlsanity.com/paper/1803.06964/) (2018)
- [Entropy and mutual information in models of deep neural networks](https://mlsanity.com/paper/1805.09785/) (2018)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [Phase retrieval in high dimensions: Statistical and computational phase transitions](https://mlsanity.com/paper/2006.05228/) (2020)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [Approximate Message Passing algorithms for rotationally invariant matrices](https://mlsanity.com/paper/2008.11892/) (2020)
- [Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula](https://mlsanity.com/paper/1606.04142/) (2016)
- [Asymptotic Errors for Teacher-Student Convex Generalized Linear Models (or : How to Prove Kabashima's Replica Formula)](https://mlsanity.com/paper/2006.06581/) (2020)
- [Phase transitions and sample complexity in Bayes-optimal matrix factorization](https://mlsanity.com/paper/1402.1298/) (2014)
- [MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel](https://mlsanity.com/paper/1507.03857/) (2015)
- [Approximate Message Passing with Spectral Initialization for Generalized Linear Models](https://mlsanity.com/paper/2010.03460/) (2020)
- [Message-passing algorithms for synchronization problems over compact groups](https://mlsanity.com/paper/1610.04583/) (2016)
- [Fundamental limits of detection in the spiked Wigner model](https://mlsanity.com/paper/1806.09588/) (2018)
- [Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization](https://mlsanity.com/paper/2110.02318/) (2021)
- [Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2112.04330/) (2021)
- [Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares](https://mlsanity.com/paper/1705.02973/) (2017)
- [All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation](https://mlsanity.com/paper/2006.07971/) (2020)
- [PCA Initialization for Approximate Message Passing in Rotationally Invariant Models](https://mlsanity.com/paper/2106.02356/) (2021)
- [Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method](https://mlsanity.com/paper/1812.02537/) (2018)
- [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)
- [Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization](https://mlsanity.com/paper/1609.05573/) (2016)
- [Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures](https://mlsanity.com/paper/2009.12939/) (2020)

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

- [Regularization, early-stopping and dreaming: a Hopfield-like setup to address generalization and overfitting](https://mlsanity.com/paper/2308.01421/) (2023)
- [The effect of priors on Learning with Restricted Boltzmann Machines](https://mlsanity.com/paper/2412.02623/) (2024)
- [Mismatched estimation of non-symmetric rank-one matrices corrupted by structured noise](https://mlsanity.com/paper/2302.03306/) (2023)

## Abstract (arXiv)

How do statistical dependencies in measurement noise influence high-dimensional inference? To answer this, we study the paradigmatic spiked matrix model of principal components analysis (PCA), where a rank-one matrix is corrupted by additive noise. We go beyond the usual independence assumption on the noise entries, by drawing the noise from a low-order polynomial orthogonal matrix ensemble. The resulting noise correlations make the setting relevant for applications but analytically challenging. We provide the first characterization of the Bayes-optimal limits of inference in this model. If the spike is rotation-invariant, we show that standard spectral PCA is optimal. However, for more general priors, both PCA and the existing approximate message passing algorithm (AMP) fall short of achieving the information-theoretic limits, which we compute using the replica method from statistical mechanics. We thus propose a novel AMP, inspired by the theory of Adaptive Thouless-Anderson-Palmer equations, which saturates the theoretical limit. This AMP comes with a rigorous state evolution analysis tracking its performance. Although we focus on specific noise distributions, our methodology can be generalized to a wide class of trace matrix ensembles at the cost of more involved expressions. Finally, despite the seemingly strong assumption of rotation-invariant noise, our theory empirically predicts algorithmic performance on real data, pointing at remarkable universality properties.