提出快速鲁棒的AMP算法，抗局部噪声干扰。
Fast, robust approximate message passing
- 先谱预处理，再微调迭代过程
- 噪声仅限εn×εn子矩阵时误差随ε趋近0
- 适合高维对称矩阵优化问题
针对任意具有独立次高斯元素的对称矩阵 $X$ 上的二次优化问题，以及任意可分离的AMP算法 $Ω$，本文提出一种快速谱方法实现鲁棒的近似消息传递。该算法在输入 $X + E$（其中 $E$ 支持于 $ε n \times ε n$ 主子矩阵）时，输出解 $\hat v$ 与 $Ω(X)$ 的欧氏距离满足 $\|\u2126(X) - \hat v\|_2 \le f(\u03b5) \|\u2126(X)\|_2$，其中 $f(\u03b5) \to 0$ 当 $\u03b5 \to 0$，且仅依赖于 $\u03b5$。该方法在保持原有算法性能的同时显著提升了对局部扰动的鲁棒性。
原文摘要 · Abstract (English)
We give a fast, spectral procedure for implementing approximate-message passing (AMP) algorithms robustly. For any quadratic optimization problem over symmetric matrices $X$ with independent subgaussian entries, and any separable AMP algorithm $\mathcal A$, our algorithm performs a spectral pre-processing step and then mildly modifies the iterates of $\mathcal A$. If given the perturbed input $X + E \in \mathbb R^{n \times n}$ for any $E$ supported on a $\varepsilon n \times \varepsilon n$ principal minor, our algorithm outputs a solution $\hat v$ which is guaranteed to be close to the output of $\mathcal A$ on the uncorrupted $X$, with $\|\mathcal A(X) - \hat v\|_2 \le f(\varepsilon) \|\mathcal A(X)\|_2$ where $f(\varepsilon) \to 0$ as $\varepsilon \to 0$ depending only on $\varepsilon$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。