Phase Retrieval via Wirtinger Flow: Theory and Algorithms
Emmanuel J. Candès Xiaodong Li Mahdi Soltanolkotabi Departments of Mathematics and of Statistics, Stanford University, Stanford CADepartment of Statistics, The Wharton School, University of Pennsylvania, Philadelphia, PAMing Hsieh Department of Electrical Engineering, University of Southern California, Los Angeles, CA
Abstract
We study the problem of recovering the phase from magnitude measurements; specifically, we wish to reconstruct a complex-valued signal $\bm{x}\in\mathbb{C}^{n}$ about which we have phaseless samples of the form $y_{r}=\left|\langle\bm{a}_{r},\bm{x}\rangle\right|^{2}$ , $r=1,\ldots,m$ (knowledge of the phase of these samples would yield a linear system). This paper develops a non-convex formulation of the phase retrieval problem as well as a concrete solution algorithm. In a nutshell, this algorithm starts with a careful initialization obtained by means of a spectral method, and then refines this initial estimate by iteratively applying novel update rules, which have low computational complexity, much like in a gradient descent scheme. The main contribution is that this algorithm is shown to rigorously allow the exact retrieval of phase information from a nearly minimal number of random measurements. Indeed, the sequence of successive iterates provably converges to the solution at a geometric rate so that the proposed scheme is efficient both in terms of computational and data resources. In theory, a variation on this scheme leads to a near-linear time algorithm for a physically rea
中文速览
相位恢复（phase retrieval）要从信号的强度测量值（即模的平方）中还原出原始复数信号，难点在于测量过程丢失了相位信息，直接求解是一个非凸问题。这篇论文提出了"Wirtinger流"（Wirtinger Flow）算法：先用谱方法对数据矩阵做特征值分解，得到一个足够好的初始估计，再以Wirtinger导数为基础做类梯度下降迭代更新。理论上可以证明，当随机测量数仅略多于信号维度（量级为 $n\log n$）时，迭代序列以几何速率收敛到真实信号，即每步误差都以固定比例缩小，同时计算复杂度接近线性，对于基于编码衍射图案的物理模型同样适用。这项工作的重要性在于它首次为一个经典的非凸相位恢复问题提供了严格的收敛保证，同时给出了计算高效且数据需求近乎最优的实用算法，所发展的非凸优化分析框架也对更广泛的计算问题具有借鉴意义。
原文 arXiv:1407.1065;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1407.1065v3