Poster
Optimal Algorithms for the Inhomogeneous Spiked Wigner Model
Aleksandr Pak · Justin Ko · Justin Ko · Florent Krzakala
Great Hall & Hall B1+B2 (level 1) #2005
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.
Chat is not available.