# Fundamental limits of Non-Linear Low-Rank Matrix Estimation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 68 references that are in the map.
- First posted on arXiv 7 Mar 2024.

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

- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [High-dimensional limit theorems for SGD: Effective dynamics and critical scaling](https://mlsanity.com/paper/2206.04030/) (2022)
- [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)
- [Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors](https://mlsanity.com/paper/1512.02337/) (2015)
- [Tensor principal component analysis via sum-of-squares proofs](https://mlsanity.com/paper/1507.03269/) (2015)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [The landscape of the spiked tensor model](https://mlsanity.com/paper/1711.05424/) (2017)
- [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018)
- [The estimation error of general first order methods](https://mlsanity.com/paper/2002.12903/) (2020)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula](https://mlsanity.com/paper/1606.04142/) (2016)
- [MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel](https://mlsanity.com/paper/1507.03857/) (2015)
- [Notes on computational-to-statistical gaps: predictions using statistical physics](https://mlsanity.com/paper/1803.11132/) (2018)
- [Approximate Message Passing with Spectral Initialization for Generalized Linear Models](https://mlsanity.com/paper/2010.03460/) (2020)
- [Information Limits for Recovering a Hidden Community](https://mlsanity.com/paper/1509.07859/) (2015)
- [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)
- [Universality of Approximate Message Passing Algorithms](https://mlsanity.com/paper/2003.10431/) (2020)
- [Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models](https://mlsanity.com/paper/2008.03326/) (2020)
- [Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method](https://mlsanity.com/paper/1812.02537/) (2018)

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

- [Sparse corruption in low-rank matrix inference: the PCA benchmark](https://mlsanity.com/paper/2511.11927/) (2025)
- [Learning with Restricted Boltzmann Machines: Asymptotics of AMP and GD in High Dimensions](https://mlsanity.com/paper/2505.18046/) (2025)

## Abstract (arXiv)

We consider the task of estimating a low-rank matrix from non-linear and noisy observations. We prove a strong universality result showing that Bayes-optimal performances are characterized by an equivalent Gaussian model with an effective prior, whose parameters are entirely determined by an expansion of the non-linear function. In particular, we show that to reconstruct the signal accurately, one requires a signal-to-noise ratio growing as Nfrac 12 (1-1/kF), where kF is the first non-zero Fisher information coefficient of the function. We provide asymptotic characterization for the minimal achievable mean squared error (MMSE) and an approximate message-passing algorithm that reaches the MMSE under conditions analogous to the linear version of the problem. We also provide asymptotic errors achieved by methods such as principal component analysis combined with Bayesian denoising, and compare them with Bayes-optimal MMSE.