Optimal Algorithms for the Inhomogeneous Spiked Wigner Model

Abstract

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. First, 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. Second, we deduce a simple and efficient spectral method that outperforms PCA and is shown to match the information-theoretic transition.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Pak et al. "Optimal Algorithms for the Inhomogeneous Spiked Wigner Model." Neural Information Processing Systems, 2023.

Markdown

[Pak et al. "Optimal Algorithms for the Inhomogeneous Spiked Wigner Model." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/pak2023neurips-optimal/)

BibTeX

@inproceedings{pak2023neurips-optimal,
  title     = {{Optimal Algorithms for the Inhomogeneous Spiked Wigner Model}},
  author    = {Pak, Aleksandr and Ko, Justin and Krzakala, Florent},
  booktitle = {Neural Information Processing Systems},
  year      = {2023},
  url       = {https://mlanthology.org/neurips/2023/pak2023neurips-optimal/}
}