提出一种简单高效的鲁棒消息传递算法，可恢复被局部干扰的主成分。
Easy, robust approximate message passing for planted spike models
- 先做谱预处理，再用鲁棒初始化，直接套用标准AMP
- 在ε≤0.01时，恢复误差仅约√ε量级
- 适合做稀疏PCA、非负PCA等鲁棒性分析
我们提出一种简单高效的鲁棒近似消息传递（AMP）算法，用于带植入秩-1信号的高斯矩阵模型。设 $X \in \mathbb{R}^{n \times n}$ 为高斯矩阵，其包含一个秩-1植入信号，$E \in \mathbb{R}^{n \times n}$ 为对抗性噪声，支持在大小为 $\varepsilon n \times \varepsilon n$ 的主子块上。令 $v_{\mathrm{AMP}}(X)$ 为对未污染矩阵 $X$ 执行标准AMP迭代的输出。本文给出一种仅需访问污染矩阵 $Y = X + E$ 的算法，可计算出向量 $v_{\mathrm{ALG}}(Y)$，使其与 $v_{\mathrm{AMP}}(X)$ 的距离为 $\tilde{O}(\sqrt{\varepsilon})$。该算法包括一个谱预处理步骤和一个鲁棒谱初始化过程；我们证明，令人惊讶的是，一旦完成这些步骤，标准AMP即具备天然鲁棒性。此结果适用于包括稀疏主成分分析（PCA）、非负PCA以及 $\mathbb{Z}_2$ 同步在内的多种典型AMP迭代。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。