# Phase transitions and sample complexity in Bayes-optimal matrix factorization

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2014.

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

- [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)
- [Deep learning via message passing algorithms based on belief propagation](https://mlsanity.com/paper/2110.14583/) (2021)
- [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)
- [Statistical mechanics of extensive-width Bayesian neural networks near interpolation](https://mlsanity.com/paper/2505.24849/) (2025)
- [Kernel Methods and Multi-layer Perceptrons Learn Linear Models in High Dimensions](https://mlsanity.com/paper/2201.08082/) (2022)
- [Approximate Message Passing for the Matrix Tensor Product Model](https://mlsanity.com/paper/2306.15580/) (2023)
- [On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariance](https://mlsanity.com/paper/2411.01974/) (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)
- [Sufficient-Statistic Memory AMP](https://mlsanity.com/paper/2112.15327/) (2021)
- [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)
- [Automatic Hyperparameter Tuning in Sparse Matrix Factorization](https://mlsanity.com/paper/2305.10114/) (2023)
- [Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation](https://mlsanity.com/paper/2501.18530/) (2025)
- [Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing](https://mlsanity.com/paper/2505.15195/) (2025)
- [Fundamental limits and algorithms for sparse linear regression with sublinear sparsity](https://mlsanity.com/paper/2101.11156/) (2021)
- [Estimation of embedding vectors in high dimensions](https://mlsanity.com/paper/2312.07802/) (2023)
- [Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation](https://mlsanity.com/paper/2510.24616/) (2025)

## Abstract (arXiv)

We analyse the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications such as dictionary learning, blind matrix calibration, sparse principal component analysis, blind source separation, low rank matrix completion, robust principal component analysis or factor analysis. It is also important in machine learning: unsupervised representation learning can often be studied through matrix factorization. We use the tools of statistical mechanics - the cavity and replica methods - to analyze the achievability and computational tractability of the inference problems in the setting of Bayes-optimal inference, which amounts to assuming that the two matrices have random independent elements generated from some known distribution, and this information is available to the inference algorithm. In this setting, we compute the minimal mean-squared-error achievable in principle in any computational time, and the error that can be achieved by an efficient approximate message passing algorithm. The computation is based on the asymptotic state-evolution analysis of the algorithm. The performance that our analysis predicts, both in terms of the achieved mean-squared-error, and in terms of sample complexity, is extremely promising and motivating for a further development of the algorithm.