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 ∈ mathbb Rn × n for any E supported on a varepsilon n × varepsilon 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 |mathcal A(X) - hat v|2 ≤ f(varepsilon) |mathcal A(X)|2 where f(varepsilon) → 0 as varepsilon → 0 depending only on varepsilon.