Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms
Oussama Dhifallah, Christos Thrampoulidis, and Yue M. Lu O. Dhifallah is with the John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA (e-mail: Thrampoulidis is with the Research Laboratory of Electronics (RLE) at Massachusetts Institute of Technology, Cambridge, MA 02139, USA (e-mail: M. Lu is with the John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA (e-mail: work was supported in part by the US National Science Foundation under grants CCF-1319140 and CCF-1718698. Preliminary and partial results of this work have been presented at the 55th Annual Allerton Conference on Communication, Control, and Computing in 2017 [1].
Abstract
We study algorithms for solving quadratic systems of equations based on optimization methods over polytopes. Our work is inspired by a recently proposed convex formulation of the phase retrieval problem, which estimates the unknown signal by solving a simple linear program over a polytope constructed from the measurements. We present a sharp characterization of the high-dimensional geometry of the aforementioned polytope under Gaussian measurements. This characterization allows us to derive asymptotically exact performance guarantees for PhaseMax, which also reveal a phase transition phenomenon with respect to its sample complexity. Moreover, the geometric insights gained from our analysis lead to a new nonconvex formulation of the phase retrieval problem and an accompanying iterative algorithm, which we call PhaseLamp. We show that this new algorithm has superior recovery performance over the original PhaseMax method. Finally, as yet another variation on the theme of performing phase retrieval via polytope optimization, we propose a weighted version of PhaseLamp and demonstrate, through numerical simulations, that it outperforms several state-of-the-art algorithms under both gener
中文速览
相位恢复（phase retrieval）要从只含幅值、丢失相位信息的测量中还原未知信号，核心难点在于测量方程是非凸的二次型。研究者以近年提出的凸规划方法 PhaseMax 为出发点，对其在高维高斯测量下的可行域多面体（polytope）几何结构给出了精确刻画，并由此推导出 PhaseMax 恢复性能的渐近精确公式，揭示了关于采样数与初始猜测质量的清晰相变边界。在此几何洞察的驱动下，作者进一步提出了非凸新算法 PhaseLamp，其核心思想是对一个凸域上的凸函数极大化问题做反复线性化求解，每轮迭代本质上就是以上一步估计为锚点运行一次 PhaseMax；理论分析证明 PhaseLamp 所需的最小测量数严格少于 PhaseMax，加权版本在高斯测量和更贴近实际的傅里叶型（coded-diffraction）测量下均超越多个现有最优算法，对推动相位恢复向低样本复杂度、高实用性方向发展具有重要意义。
原文 arXiv:1805.09555;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1805.09555v1