# Easy, robust approximate message passing for planted spike models

arXiv: https://arxiv.org/abs/2606.00500 · HTML: https://mlsanity.com/paper/2606.00500/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 19 references that are in the map.
- First posted on arXiv 30 May 2026.

## Builds on (most cited first, 8 of 8)

- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [Message-passing algorithms for synchronization problems over compact groups](https://mlsanity.com/paper/1610.04583/) (2016)
- [Local Statistics, Semidefinite Programming, and Community Detection](https://mlsanity.com/paper/1911.01960/) (2019)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [Semidefinite programs simulate approximate message passing robustly](https://mlsanity.com/paper/2311.09017/) (2023)
- [Robust recovery for stochastic block models, simplified and generalized](https://mlsanity.com/paper/2402.13921/) (2024)
- [Fast, robust approximate message passing](https://mlsanity.com/paper/2411.02764/) (2024)

## Abstract (arXiv)

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 ∈ mathbb Rn × n is a Gaussian matrix with a planted rank-1 spike, and E ∈ mathbb Rn × n is an adversarially chosen matrix supported on an varepsilon n × varepsilon 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 tildeO(√varepsilon)-close to vAMP(X), for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and mathbb 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.