Fast, robust approximate message passing

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 $\widehat{v}$ which is guaranteed to be close to the output of $\mathcal{A}$ on the uncorrupted $X$, with $\mathrm{\parallel }\mathcal{A}(X)-\widehat{v}{\mathrm{\parallel }}_2\le f(\epsilon )\mathrm{\parallel }\mathcal{A}(X){\mathrm{\parallel }}_2$ where $f(\epsilon )\to 0$ as $\epsilon \to 0$ depending only on $\epsilon$.