Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms

Abstract

We study algorithms for solving quadratic systems of equations based on optimization methods over polytopes. Our work is inspired by a recently proposed convex formulation of the phase retrieval problem, which estimates the unknown signal by solving a simple linear program over a polytope constructed from the measurements. We present a sharp characterization of the high-dimensional geometry of the aforementioned polytope under Gaussian measurements. This characterization allows us to derive asymptotically exact performance guarantees for PhaseMax, which also reveal a phase transition phenomenon with respect to its sample complexity. Moreover, the geometric insights gained from our analysis lead to a new nonconvex formulation of the phase retrieval problem and an accompanying iterative algorithm, which we call PhaseLamp. We show that this new algorithm has superior recovery performance over the original PhaseMax method. Finally, as yet another variation on the theme of performing phase retrieval via polytope optimization, we propose a weighted version of PhaseLamp and demonstrate, through numerical simulations, that it outperforms several state-of-the-art algorithms under both generic Gaussian measurements as well as more realistic Fourier-type measurements that arise in phase retrieval applications.

References in corpus (7)

• A Field Guide to Forward-Backward Splitting with a FASTA Implementation
• A framework to characterize performance of LASSO algorithms
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• Precise Error Analysis of Regularized M-estimators in High-dimensions

Cited by in corpus (11)

• Phase Retrieval for Partially Coherent Observations
• The Impact of Regularization on High-dimensional Logistic Regression
• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• A Model of Double Descent for High-dimensional Binary Linear Classification
• Phase Transitions in Transfer Learning for High-Dimensional Perceptrons
• On the Inherent Regularization Effects of Noise Injection During Training
• Sharp Asymptotics and Optimal Performance for Inference in Binary Models
• Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximization
• The Performance Analysis of Generalized Margin Maximizer (GMM) on Separable Data
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective