首次实现高维相位恢复的高效鲁棒算法，支持重尾噪声和对抗性污染。
Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity
- 利用鲁棒PCA新进展解决相位恢复的谱初始化难题。
- 在仅需近线性样本量（$O(n ext{ polylog } n)$）下完成恢复。
- 适用于光学、晶体学等受噪声与恶意干扰影响的场景。
相位恢复是经典问题，目标是从带噪的相位缺失测量值 $y_i = \langle a_i, x^* \rangle^2 + ζ_i$ 中恢复信号 $x^* \in \mathbb{R}^n$。该问题在光学、晶体学、异方差回归等领域有广泛应用。现有算法对测量误差的鲁棒性仍是关键挑战。近期，在鲁棒统计算法方面取得突破，可高效处理重尾噪声与对抗性污染下的均值、协方差估计及鲁棒主成分分析（PCA）。本文研究在恒定比例测量值和传感向量 $a_i$ 受任意对抗性污染时的鲁棒相位恢复算法。此前，Buna 和 Rebeschini（AISTATS 2025）提出需指数时间的 $O(n \log n)$ 样本复杂度算法，其依赖于鲁棒谱初始化（即协方差矩阵最大特征向量的鲁棒估计），被认为超出现有高效算法能力。本文通过建立鲁棒谱初始化与最新鲁棒PCA进展的联系，首次实现多项式时间算法，并达到近线性样本复杂度 $O(n \text{ polylog } n)$，突破了此前瓶颈。
原文摘要 · Abstract (English)
Phase retrieval is the classical problem of recovering a signal $x^* \in \mathbb{R}^n$ from its noisy phaseless measurements $y_i = \langle a_i, x^* \rangle^2 + ζ_i$ (where $ζ_i$ denotes noise, and $a_i$ is the sensing vector) for $i \in [m]$. The problem of phase retrieval has a rich history, with a variety of applications such as optics, crystallography, heteroscedastic regression, astrophysics, etc. A major consideration in algorithms for phase retrieval is robustness against measurement errors. In recent breakthroughs in algorithmic robust statistics, efficient algorithms have been developed for several parameter estimation tasks such as mean estimation, covariance estimation, robust principal component analysis (PCA), etc. in the presence of heavy-tailed noise and adversarial corruptions. In this paper, we study efficient algorithms for robust phase retrieval with heavy-tailed noise when a constant fraction of both the measurements $y_i$ and the sensing vectors $a_i$ may be arbitrarily adversarially corrupted. For this problem, Buna and Rebeschini (AISTATS 2025) very recently gave an exponential time algorithm with sample complexity $O(n \log n)$. Their algorithm needs a robust spectral initialization, specifically, a robust estimate of the top eigenvector of a covariance matrix, which they deemed to be beyond known efficient algorithmic techniques (similar spectral initializations are a key ingredient of a large family of phase retrieval algorithms). In this work, we make a connection between robust spectral initialization and recent algorithmic advances in robust PCA, yielding the first polynomial-time algorithms for robust phase retrieval with both heavy-tailed noise and adversarial corruptions, in fact with near-linear (in $n$) sample complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。