Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation

Abstract

We propose a flexible convex relaxation for the phase retrieval problem that operates in the natural domain of the signal. Therefore, we avoid the prohibitive computational cost associated with "lifting" and semidefinite programming (SDP) in methods such as PhaseLift and compete with recently developed non-convex techniques for phase retrieval. We relax the quadratic equations for phaseless measurements to inequality constraints each of which representing a symmetric "slab". Through a simple convex program, our proposed estimator finds an extreme point of the intersection of these slabs that is best aligned with a given anchor vector. We characterize geometric conditions that certify success of the proposed estimator. Furthermore, using classic results in statistical learning theory, we show that for random measurements the geometric certificates hold with high probability at an optimal sample complexity. Phase transition of our estimator is evaluated through simulations. Our numerical experiments also suggest that the proposed method can solve phase retrieval problems with coded diffraction measurements as well.

Accepted in AISTATS 2017. Extended the discussion of related work and added a few more references. Clarified some of the statements and notations

References in corpus (3)

• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
• Corruption Robust Phase Retrieval via Linear Programming

Cited by in corpus (24)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Compressive Phase Retrieval via Reweighted Amplitude Flow
• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms
• prDeep: Robust Phase Retrieval with a Flexible Deep Network
• Convolutional Phase Retrieval via Gradient Descent
• Corruption Robust Phase Retrieval via Linear Programming
• Denoising Poisson Phaseless Measurements via Orthogonal Dictionary Learning
• Online Stochastic Gradient Descent with Arbitrary Initialization Solves Non-smooth, Non-convex Phase Retrieval
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Solving Almost all Systems of Random Quadratic Equations
• Approximate Message Passing for Amplitude Based Optimization
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization
• Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery
• BranchHull: Convex bilinear inversion from the entrywise product of signals with known signs
• Bilinear Compressed Sensing under known Signs via Convex Programming
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Multiple Scattering Media Imaging via End-to-End Neural Network
• Phase retrieval for sub-Gaussian measurements
• Phase Retrieval by Alternating Minimization with Random Initialization
• $L^0$-regularized Variational Methods for Sparse Phase Retrieval
• Phase retrieval of complex-valued objects via a randomized Kaczmarz method
• Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problems
• A convex program for bilinear inversion of sparse vectors