提出高效算法，从有坏数据的测量中恢复信号
A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval
- 用交替最小化结合非凸优化求解器，避开复杂初始化
- 在少量样本下仍能收敛，样本复杂度近似线性
- 适合处理含任意坏数据的信号恢复问题
本文研究鲁棒相位恢复问题，目标是从可能被任意破坏的仅含幅值的线性测量中恢复未知信号 θ* ∈ ℝ^d。提出一种交替最小化算法，将非凸优化问题的预言机求解器作为子程序。该算法保证收敛至 θ*，且收敛速率对坏数据比例具有显式的多项式依赖关系。进一步，在稀疏任意异常值模型下，给出了该预言机的高效构造，并揭示了带坏数据时相位恢复损失函数的几何特性。所提预言机无需计算代价高昂的谱初始化，仅使用固定步长梯度下降与随机初始化即可实现。整体算法达到近似线性样本复杂度，为 𝒪(d polylog(d))。
原文摘要 · Abstract (English)
In this work, we study the robust phase retrieval problem where the task is to recover an unknown signal $θ^* \in \mathbb{R}^d$ in the presence of potentially arbitrarily corrupted magnitude-only linear measurements. We propose an alternating minimization approach that incorporates an oracle solver for a non-convex optimization problem as a subroutine. Our algorithm guarantees convergence to $θ^*$ and provides an explicit polynomial dependence of the convergence rate on the fraction of corrupted measurements. We then provide an efficient construction of the aforementioned oracle under a sparse arbitrary outliers model and offer valuable insights into the geometric properties of the loss landscape in phase retrieval with corrupted measurements. Our proposed oracle avoids the need for computationally intensive spectral initialization, using a simple gradient descent algorithm with a constant step size and random initialization instead. Additionally, our overall algorithm achieves nearly linear sample complexity, $\mathcal{O}(d \, \mathrm{polylog}(d))$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。