Phase Recovery, MaxCut and Complex Semidefinite Programming

Abstract

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.

arXiv commentSubmitted revision

References in corpus (6)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Sparsity-based single-shot sub-wavelength coherent diffractive imaging
• Exact Matrix Completion via Convex Optimization
• Sparse Signal Recovery from Quadratic Measurements via Convex Programming
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Solving Quadratic Equations via PhaseLift when There Are About As Many Equations As Unknowns

Cited by in corpus (25)

• An overview of low-rank matrix recovery from incomplete observations
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• Nonconvex phase synchronization
• Sparse Phase Retrieval from Short-Time Fourier Measurements
• Uniqueness results for the phase retrieval problem of fractional Fourier transforms of variable order
• Augmented projections for ptychographic imaging
• Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
• Low Rank Phase Retrieval
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Compressive Phase Retrieval via Reweighted Amplitude Flow
• Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming
• Invertibility and Robustness of Phaseless Reconstruction
• Stable phase retrieval with low-redundancy frames
• Phase Retrieval with One or Two Diffraction Patterns by Alternating Projection with Null Initialization
• Near-optimal phase retrieval of sparse vectors
• Robust Wavefield Inversion via Phase Retrieval
• Measurement Matrix Design for Phase Retrieval Based on Mutual Information
• Approximating the Little Grothendieck Problem over the Orthogonal and Unitary Groups
• Phase retrieval from very few measurements
• Fourier Phase Retrieval with a Single Mask by Douglas-Rachford Algorithm
• Linear Phase Retrieval for Near-Field Measurements with Locally Known Phase Relations
• Reconstruction of Signals from Magnitudes of Redundant Representations: The Complex Case
• On Lipschitz Analysis and Lipschitz Synthesis for the Phase Retrieval Problem
• Phase Retrieval using Lipschitz Continuous Maps
• Sparse phase retrieval via group-sparse optimization