Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval

Abstract

We develop procedures, based on minimization of the composition $f(x)=h(c(x))$ of a convex function $h$ and smooth function $c$, for solving random collections of quadratic equalities, applying our methodology to phase retrieval problems. We show that the prox-linear algorithm we develop can solve phase retrieval problems---even with adversarially faulty measurements---with high probability as soon as the number of measurements $m$ is a constant factor larger than the dimension $n$ of the signal to be recovered. The algorithm requires essentially no tuning---it consists of solving a sequence of convex problems---and it is implementable without any particular assumptions on the measurements taken. We provide substantial experiments investigating our methods, indicating the practical effectiveness of the procedures and showing that they succeed with high probability as soon as $m/n\ge 2$ when the signal is real-valued.

55 pages, 9 figures

References in corpus (1)

• The Complex Gradient Operator and the CR-Calculus

Cited by in corpus (14)

• The proximal point method revisited
• Compressive Phase Retrieval via Reweighted Amplitude Flow
• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation
• Solving Almost all Systems of Random Quadratic Equations
• Approximate Message Passing for Amplitude Based Optimization
• Robust and Scalable Power System State Estimation via Composite Optimization
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization
• Line Search and Trust-Region Methods for Convex-Composite Optimization
• A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis
• About some works of Boris Polyak on convergence of gradient methods and their development
• On the Global Minimizers of Real Robust Phase Retrieval with Sparse Noise
• Phase retrieval for sub-Gaussian measurements
• Scalable Incremental Nonconvex Optimization Approach for Phase Retrieval