Easy, robust approximate message passing for planted spike models

Abstract

We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let $\epsilon$ be a sufficiently small constant, and suppose that $X\in {\mathbb{R}}^{n\times n}$ is a Gaussian matrix with a planted rank-$1$ spike, and $E\in {\mathbb{R}}^{n\times n}$ is an adversarially chosen matrix supported on an $\epsilon n\times \epsilon n$ principal minor. Let $v_{\mathrm{AMP}}(X)$ be the output of an AMP iteration on the uncorrupted matrix $X$. We give a procedure that, given access only to the corrupted matrix $Y=X+E$, computes a vector $v_{\mathrm{ALG}}(Y)$ which is $\tilde{O}(\sqrt{\epsilon })$-close to $v_{\mathrm{AMP}}(X)$, for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and ${\mathbb{Z}}_2$ synchronization. Our algorithm consists of a spectral pre-processing step combined with a robust spectral initialization procedure; given these inputs, we prove that (perhaps surprisingly) AMP is robust out-of-the-box.

32 pages