Phase recovery, MaxCut and complex semidefinite programming

• 成果类型: Article
• 署名作者: Waldspurger, Irene; d'Aspremont, Alexandre; Mallat, Stephane
• 署名单位: Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0738-9
• 发表日期: 2015
• 页码: 47-81
• 关键词: quadratic optimization; Approximation algorithms; maximum cut; relaxation; retrieval

摘要

Phase retrieval seeks to recover a signal from the amplitude of linear measurements . We cast the phase retrieval problem as a non-convex quadratic program over a complex phase vector and formulate a tractable relaxation (called PhaseCut) similar to the classical MaxCut semidefinite program. We solve this problem using a provably convergent block coordinate descent algorithm whose structure is similar to that of the original greedy algorithm in Gerchberg and Saxton (Optik 35:237-246, 1972), where each iteration is a matrix vector product. Numerical results show the performance of this approach over three different phase retrieval problems, in comparison with greedy phase retrieval algorithms and matrix completion formulations.