Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow

Abstract

This paper presents a new algorithm, termed \emph{truncated amplitude flow} (TAF), to recover an unknown vector $\mathbf{x}$ from a system of quadratic equations of the form $y_i=|⟨{\mathbf{a}}_i,\mathbf{x}⟩{|}^2$, where ${\mathbf{a}}_i$'s are given random measurement vectors. This problem is known to be \emph{NP-hard} in general. We prove that as soon as the number of equations is on the order of the number of unknowns, TAF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with both the number of unknowns and the number of equations. Our TAF approach adopts the \emph{amplitude-based} empirical loss function, and proceeds in two stages. In the first stage, we introduce an \emph{orthogonality-promoting} initialization that can be obtained with a few power iterations. Stage two refines the initial estimate by successive updates of scalable \emph{truncated generalized gradient iterations}, which are able to handle the rather challenging nonconvex and nonsmooth amplitude-based objective function. In particular, when vectors $\mathbf{x}$ and ${\mathbf{a}}_i$'s are real-valued, our gradient truncation rule provably eliminates erroneously estimated signs with high probability to markedly improve upon its untruncated version. Numerical tests using synthetic data and real images demonstrate that our initialization returns more accurate and robust estimates relative to spectral initializations. Furthermore, even under the same initialization, the proposed amplitude-based refinement outperforms existing Wirtinger flow variants, corroborating the superior performance of TAF over state-of-the-art algorithms.

37 Pages, 16 figures

References in corpus (8)

• Sparse Phase Retrieval from Short-Time Fourier Measurements
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval
• Inexact Alternating Optimization for Phase Retrieval In the Presence of Outliers
• Sparse Phase Retrieval via Truncated Amplitude Flow
• Solving Almost all Systems of Random Quadratic Equations

Cited by in corpus (26)

• Optimal Spectral Initialization for Signal Recovery with Applications to Phase Retrieval
• Phaseless Rcovery using Gauss-Newton Method
• Low Rank Phase Retrieval
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Power System State Estimation via Feasible Point Pursuit: Algorithms and Cramer-Rao Bound
• Undersampled Phase Retrieval via Majorization-Minimization
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• "Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
• Reshaped Wirtinger Flow and Incremental Algorithm for Solving Quadratic System of Equations
• Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval
• Information capacity of direct detection optical transmission systems
• Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms
• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• Inexact Alternating Optimization for Phase Retrieval In the Presence of Outliers
• Randomized Block Frank-Wolfe for Convergent Large-Scale Learning
• Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space
• On The 2D Phase Retrieval Problem
• Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption
• Solving Almost all Systems of Random Quadratic Equations
• Phase Retrieval via Sparse Wirtinger Flow
• Approximate Message Passing for Amplitude Based Optimization
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization
• SPRSF: Sparse Phase Retrieval via Smoothing Function
• Non-Convex Structured Phase Retrieval
• Solving Random Systems of Quadratic Equations with Tanh Wirtinger Flow
• Provable Low Rank Phase Retrieval