NeurIPS 2023poster12 citations
Optimal Algorithms for the Inhomogeneous Spiked Wigner Model
Alexander Pak, Justin Ko, Florent Krzakala
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.
Spectral MethodCommunity detectionWigner Spike modelRandom MatrixBBP transitionApproximate Message PassingSpin glassesStatistical Physics
BibTeX
@inproceedings{
pak2023optimal,
title={Optimal Algorithms for the Inhomogeneous Spiked Wigner Model},
author={Alexander Pak and Justin Ko and Florent Krzakala},
booktitle={Thirty-seventh Conference on Neural Information Processing Systems},
year={2023},
url={https://openreview.net/forum?id=xNUmTRYtV1}
}