Skip to yearly menu bar Skip to main content


Optimal Algorithms for the Inhomogeneous Spiked Wigner Model

Aleksandr Pak · Justin Ko · Justin Ko · Florent Krzakala

Great Hall & Hall B1+B2 (level 1) #2005
[ ]
[ Paper [ Poster [ OpenReview
Thu 14 Dec 3 p.m. PST — 5 p.m. PST


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.

Chat is not available.