Easy, robust approximate message passing for planted spike models

arXiv:2606.00500v1 Announce Type: cross Abstract: We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let arepsilon be a sufficiently small constant, and suppose that X in mathbb R^{n imes n} is a Gaussian matrix with a planted rank-1 spike, and E in mathbb R^{n imes n} is an adversarially chosen matrix supported on an arepsilon n imes arepsilon n principal minor. Let v_{AMP}(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 v_{ALG}(Y) which is ilde{O}(sqrt{arepsilon})-close to v_{AMP}(X), for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and mathbb Z_2 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.

Source: arXiv cs.LG | 2026-06-02