mlsanityData to 14 Oct 2026

Fundamental limits of Non-Linear Low-Rank Matrix Estimation

arXiv 2403.04234 ↗First posted 7 Mar 2024stat.ML cs.LGcited by 2

Not on the map. Why?

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.

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

23 of 68 references.

References · 23

  1. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  2. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 150
  3. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  4. 2022High-dimensional limit theorems for SGD: Effective dynamics and critical scalingcited by 70
  5. 2021A unifying tutorial on Approximate Message Passingcited by 50
  6. 2017Estimation of Low-Rank Matrices via Approximate Message Passingcited by 41
  7. 2015Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectorscited by 38
  8. 2015Tensor principal component analysis via sum-of-squares proofscited by 35
  9. 2021Graph-based Approximate Message Passing Iterationscited by 35
  10. 2017The landscape of the spiked tensor modelcited by 34
  11. 2018Optimality and Sub-optimality of PCA I: Spiked Random Matrix Modelscited by 33
  12. 2020The estimation error of general first order methodscited by 33
11 more
  1. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  2. 2016Mutual information for symmetric rank-one matrix estimation: A proof of the replica formulacited by 26
  3. 2015MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channelcited by 22
  4. 2018Notes on computational-to-statistical gaps: predictions using statistical physicscited by 22
  5. 2020Approximate Message Passing with Spectral Initialization for Generalized Linear Modelscited by 22
  6. 2015Information Limits for Recovering a Hidden Communitycited by 18
  7. 2016Message-passing algorithms for synchronization problems over compact groupscited by 18
  8. 2018Fundamental limits of detection in the spiked Wigner modelcited by 18
  9. 2020Universality of Approximate Message Passing Algorithmscited by 16
  10. 2020Optimal Combination of Linear and Spectral Estimators for Generalized Linear Modelscited by 15
  11. 2018Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling methodcited by 11

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025Sparse corruption in low-rank matrix inference: the PCA benchmarkcited by 2
  2. 2025Learning with Restricted Boltzmann Machines: Asymptotics of AMP and GD in High Dimensionscited by 1