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 A, our algorithm performs a spectral pre-processing step and then mildly modifies the iterates of A. If given the perturbed input X + E ∈ ℝn × n for any E supported on a ε n × ε n principal minor, our algorithm outputs a solution v which is guaranteed to be close to the output of A on the uncorrupted X, with ||A(X) − v||2 ≤ f(ε) ||A(X)||2 where f(ε) → 0 as ε → 0 depending only on ε.