mlsanityData to 7 Oct 2026

Optimal Algorithms for the Inhomogeneous Spiked Wigner Model

arXiv 2302.06665 ↗First posted 13 Feb 2023stat.ML cond-mat.dis-nn cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

In this paper, we study a spiked Wigner problem with an inhomogeneous noise profile. Our aim in this problem is to recover the signal passed through an inhomogeneous low-rank matrix channel. While the information-theoretic performances are well-known, we focus on the algorithmic problem. We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem and show that its rigorous state evolution coincides with the information-theoretic optimal Bayes fixed-point equations. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random. Finally, from the adapted AMP iteration we deduce a simple and efficient spectral method that can be used to recover the transition for matrices with general variance profiles. This spectral method matches the conjectured optimal computational phase transition.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 15 of its 40 references that are in the map. First posted on arXiv 13 Feb 2023.

Builds on

15 of 40 references.

References · 15

  1. 2015Statistical physics of inference: Thresholds and algorithmscited by 128
  2. 2021A unifying tutorial on Approximate Message Passingcited by 49
  3. 2017Fundamental Limits of Weak Recovery with Applications to Phase Retrievalcited by 39
  4. 2021Graph-based Approximate Message Passing Iterationscited by 35
  5. 2020The estimation error of general first order methodscited by 33
  6. 2014Spectral Clustering of Graphs with the Bethe Hessiancited by 22
  7. 2018Notes on computational-to-statistical gaps: predictions using statistical physicscited by 22
  8. 2020Approximate Message Passing with Spectral Initialization for Generalized Linear Modelscited by 22
  9. 2019The spiked matrix model with generative priorscited by 20
  10. 2018Fundamental limits of detection in the spiked Wigner modelcited by 18
  11. 2021Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passingcited by 18
  12. 2020Optimal Combination of Linear and Spectral Estimators for Generalized Linear Modelscited by 15
3 more
  1. 2018Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling methodcited by 11
  2. 2020Information-theoretic limits of a multiview low-rank symmetric spiked matrix modelcited by 8
  3. 2021Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticitycited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 3; 2025: 2; 2026: 1.

8 papers.

  1. 2023Approximate Message Passing for the Matrix Tensor Product Modelcited by 6
  2. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 6
  3. 2023Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passingcited by 5
  4. 2024Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methodscited by 5
  5. 2024Spectral Phase Transition and Optimal PCA in Block-Structured Spiked modelscited by 4
  6. 2024Signal-Plus-Noise Decomposition of Nonlinear Spiked Random Matrix Modelscited by 2
  7. 2025Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noisecited by 0
  8. 2026Precise sample covariance spectral norm error -- an RDT viewcited by 0