# Statistical limits of dictionary learning: random matrix theory and the spectral replica method

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 137 references that are in the map.
- First posted on arXiv 14 Sep 2021.

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

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [Passed & Spurious: Descent Algorithms and Local Minima in Spiked Matrix-Tensor Models](https://mlsanity.com/paper/1902.00139/) (2019)
- [Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula](https://mlsanity.com/paper/1606.04142/) (2016)
- [Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model](https://mlsanity.com/paper/1907.08226/) (2019)
- [Phase transitions and sample complexity in Bayes-optimal matrix factorization](https://mlsanity.com/paper/1402.1298/) (2014)
- [Information Limits for Recovering a Hidden Community](https://mlsanity.com/paper/1509.07859/) (2015)
- [All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation](https://mlsanity.com/paper/2006.07971/) (2020)
- [Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2102.12430/) (2021)
- [Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method](https://mlsanity.com/paper/1812.02537/) (2018)
- [Information-Theoretic Limits for the Matrix Tensor Product](https://mlsanity.com/paper/2005.11273/) (2020)
- [Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning](https://mlsanity.com/paper/1301.5898/) (2013)
- [Rank-one matrix estimation: analytic time evolution of gradient descent dynamics](https://mlsanity.com/paper/2105.12257/) (2021)
- [Sample Complexity of Bayesian Optimal Dictionary Learning](https://mlsanity.com/paper/1301.6199/) (2013)
- [Mismatched Estimation of rank-one symmetric matrices under Gaussian noise](https://mlsanity.com/paper/2107.08927/) (2021)

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

- [Archetypal SAE: Adaptive and Stable Dictionary Learning for Concept Extraction in Large Vision Models](https://mlsanity.com/paper/2502.12892/) (2025)
- [Statistical mechanics of extensive-width Bayesian neural networks near interpolation](https://mlsanity.com/paper/2505.24849/) (2025)
- [Depth induces scale-averaging in overparameterized linear Bayesian neural networks](https://mlsanity.com/paper/2111.11954/) (2021)
- [On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariance](https://mlsanity.com/paper/2411.01974/) (2024)
- [Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens](https://mlsanity.com/paper/2410.18858/) (2024)
- [The Decimation Scheme for Symmetric Matrix Factorization](https://mlsanity.com/paper/2307.16564/) (2023)
- [Gradient flow on extensive-rank positive semi-definite matrix denoising](https://mlsanity.com/paper/2303.09474/) (2023)
- [Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation](https://mlsanity.com/paper/2501.18530/) (2025)
- [Bayesian Inference with Nonlinear Generative Models: Comments on Secure Learning](https://mlsanity.com/paper/2201.09986/) (2022)
- [Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation](https://mlsanity.com/paper/2510.24616/) (2025)

## Abstract (arXiv)

We consider increasingly complex models of matrix denoising and dictionary learning in the Bayes-optimal setting, in the challenging regime where the matrices to infer have a rank growing linearly with the system size. This is in contrast with most existing literature concerned with the low-rank (i.e., constant-rank) regime. We first consider a class of rotationally invariant matrix denoising problems whose mutual information and minimum mean-square error are computable using techniques from random matrix theory. Next, we analyze the more challenging models of dictionary learning. To do so we introduce a novel combination of the replica method from statistical mechanics together with random matrix theory, coined spectral replica method. This allows us to derive variational formulas for the mutual information between hidden representations and the noisy data of the dictionary learning problem, as well as for the overlaps quantifying the optimal reconstruction error. The proposed method reduces the number of degrees of freedom from Theta(N2) matrix entries to Theta(N) eigenvalues (or singular values), and yields Coulomb gas representations of the mutual information which are reminiscent of matrix models in physics. The main ingredients are a combination of large deviation results for random matrices together with a new replica symmetric decoupling ansatz at the level of the probability distributions of eigenvalues (or singular values) of certain overlap matrices and the use of HarishChandra-Itzykson-Zuber spherical integrals.