{"id":"arxiv/2606.00500","url":"https://arxiv.org/abs/2606.00500","tags":["cs.DS","cs.LG","math.ST","stat.ML"],"score":0,"title":"Easy, robust approximate message passing for planted spike models","domain":"cs.DS","source":"arxiv","authors":["Misha Ivkov","Tselil Schramm"],"reviews":0,"subject":"cs.DS","summary":"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$,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-30","reactions":{}}