  Phase retrieval seeks to recover a signal x from the amplitude |Ax| 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-Saxton, 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.
