mlsanityData to 14 Oct 2026

MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel

arXiv 1507.03857 ↗First posted 14 Jul 2015cs.IT cond-mat.stat-mech math.ITcited by 22

Not on the map. Why?

Abstract (arXiv)

This paper considers probabilistic estimation of a low-rank matrix from non-linear element-wise measurements of its elements. We derive the corresponding approximate message passing (AMP) algorithm and its state evolution. Relying on non-rigorous but standard assumptions motivated by statistical physics, we characterize the minimum mean squared error (MMSE) achievable information theoretically and with the AMP algorithm. Unlike in related problems of linear estimation, in the present setting the MMSE depends on the output channel only trough a single parameter - its Fisher information. We illustrate this striking finding by analysis of submatrix localization, and of detection of communities hidden in a dense stochastic block model. For this example we locate the computational and statistical boundaries that are not equal for rank larger than four.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). First posted on arXiv 14 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 4; 2022: 3; 2023: 6; 2024: 6; 2025: 2; 2026: 1.

22 papers.

Sort:

  1. 2022The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statisticscited by 31
  2. 2023Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspectivecited by 26
  3. 2021The planted matching problem: Sharp threshold and infinite-order phase transitioncited by 9
  4. 2026A solvable high-dimensional model where nonlinear autoencoders learn structure invisible to PCA while test loss misaligns with generalizationcited by 8
  5. 2022Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomialscited by 6
  6. 2024Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noisecited by 6
  7. 2024Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methodscited by 5
  8. 2021Detection of Signal in the Spiked Rectangular Modelscited by 4
  9. 2024Optimal thresholds and algorithms for a model of multi-modal learning in high dimensionscited by 4
  10. 2024On the phase diagram of extensive-rank symmetric matrix denoising beyond rotational invariancecited by 4
  11. 2022Bayes-optimal limits in structured PCA, and how to reach themcited by 3
  12. 2023Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networkscited by 3
10 more
  1. 2021Bayesian reconstruction of memories stored in neural networks from their connectivitycited by 2
  2. 2021Inferring Hidden Structures in Random Graphscited by 2
  3. 2023Planted Bipartite Graph Detectioncited by 2
  4. 2023The Decimation Scheme for Symmetric Matrix Factorizationcited by 2
  5. 2024Fundamental limits of Non-Linear Low-Rank Matrix Estimationcited by 2
  6. 2024Signal-Plus-Noise Decomposition of Nonlinear Spiked Random Matrix Modelscited by 2
  7. 2025Sparse corruption in low-rank matrix inference: the PCA benchmarkcited by 2
  8. 2023Detection problems in the spiked matrix modelscited by 1
  9. 2023Estimation of embedding vectors in high dimensionscited by 0
  10. 2025Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noisecited by 0