*Stanford University. · †Stanford University.
We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let
ε be a sufficiently small constant, and suppose that
X∈Rn×n is a Gaussian matrix with a planted rank-
1 spike, and
E∈Rn×n is an adversarially chosen matrix supported on an
εn×εn principal minor. Let
vAMP(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
vALG(Y) which is
O~(ε)-close to
vAMP(X), for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and
Z2 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.