Fast, robust approximate message passing

Abstract

We give a fast, spectral procedure for implementing approximate-message passing (AMP) algorithms robustly. For any quadratic optimization problem over symmetric matrices $X$ with independent subgaussian entries, and any separable AMP algorithm $\mathcal{A}$, our algorithm performs a spectral pre-processing step and then mildly modifies the iterates of $\mathcal{A}$. If given the perturbed input $X+E\in {\mathbb{R}}^{n\times n}$ for any $E$ supported on a $\epsilon n\times \epsilon n$ principal minor, our algorithm outputs a solution $\hat{v}$ which is guaranteed to be close to the output of $\mathcal{A}$ on the uncorrupted $X$, with $\Vert \mathcal{A}(X)-\hat{v}{\Vert }_2\le f(\epsilon )\Vert \mathcal{A}(X){\Vert }_2$ where $f(\epsilon )\to 0$ as $\epsilon \to 0$ depending only on $\epsilon$.

22 pages, 2 figures