# Optimal Algorithms for the Inhomogeneous Spiked Wigner Model

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

## Key facts

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

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

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Fundamental Limits of Weak Recovery with Applications to Phase Retrieval](https://mlsanity.com/paper/1708.05932/) (2017)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [The estimation error of general first order methods](https://mlsanity.com/paper/2002.12903/) (2020)
- [Spectral Clustering of Graphs with the Bethe Hessian](https://mlsanity.com/paper/1406.1880/) (2014)
- [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)
- [The spiked matrix model with generative priors](https://mlsanity.com/paper/1905.12385/) (2019)
- [Fundamental limits of detection in the spiked Wigner model](https://mlsanity.com/paper/1806.09588/) (2018)
- [Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2112.04330/) (2021)
- [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)
- [Information-theoretic limits of a multiview low-rank symmetric spiked matrix model](https://mlsanity.com/paper/2005.08017/) (2020)
- [Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity](https://mlsanity.com/paper/2106.11950/) (2021)

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

- [Optimal Spectral Transitions in High-Dimensional Multi-Index Models](https://mlsanity.com/paper/2502.02545/) (2025)
- [Approximate Message Passing for the Matrix Tensor Product Model](https://mlsanity.com/paper/2306.15580/) (2023)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods](https://mlsanity.com/paper/2405.13912/) (2024)
- [Spectral Phase Transition and Optimal PCA in Block-Structured Spiked models](https://mlsanity.com/paper/2403.03695/) (2024)
- [Signal-Plus-Noise Decomposition of Nonlinear Spiked Random Matrix Models](https://mlsanity.com/paper/2405.18274/) (2024)
- [Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise](https://mlsanity.com/paper/2510.08541/) (2025)
- [Precise sample covariance spectral norm error -- an RDT view](https://mlsanity.com/paper/2607.14460/) (2026)

## 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.