{"ID":2921952,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-02T02:42:49.606572591Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.00500","arxiv_id":"2606.00500","title":"Easy, robust approximate message passing for planted spike models","abstract":"We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let $\\varepsilon$ be a sufficiently small constant, and suppose that $X \\in \\mathbb R^{n \\times n}$ is a Gaussian matrix with a planted rank-$1$ spike, and $E \\in \\mathbb R^{n \\times n}$ is an adversarially chosen matrix supported on an $\\varepsilon n \\times \\varepsilon n$ principal minor. Let $v_{\\mathrm{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_{\\mathrm{ALG}}(Y)$ which is $\\tilde{O}(\\sqrt{\\varepsilon})$-close to $v_{\\mathrm{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.","short_abstract":"We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let $\\varepsilon$ be a sufficiently small constant, and suppose that $X \\in \\mathbb R^{n \\times n}$ is a Gaussian matrix with a planted rank-$1$ spike, and $E \\in \\mathbb R^{n \\times n}$...","url_abs":"https://arxiv.org/abs/2606.00500","url_pdf":"https://arxiv.org/pdf/2606.00500v1","authors":"[\"Misha Ivkov\",\"Tselil Schramm\"]","published":"2026-05-30T03:18:52Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\",\"math.ST\",\"stat.ML\"]","methods":"[]","has_code":false}