Solving Almost all Systems of Random Quadratic Equations

Abstract

This paper deals with finding an $n$-dimensional solution $x$ to a system of quadratic equations of the form $y_i=|⟨a_i,x⟩{|}^2$ for $1\le i\le m$, which is also known as phase retrieval and is NP-hard in general. We put forth a novel procedure for minimizing the amplitude-based least-squares empirical loss, that starts with a weighted maximal correlation initialization obtainable with a few power or Lanczos iterations, followed by successive refinements based upon a sequence of iteratively reweighted (generalized) gradient iterations. The two (both the initialization and gradient flow) stages distinguish themselves from prior contributions by the inclusion of a fresh (re)weighting regularization technique. The overall algorithm is conceptually simple, numerically scalable, and easy-to-implement. For certain random measurement models, the novel procedure is shown capable of finding the true solution $x$ in time proportional to reading the data $\{(a_i;y_i){\}}_{1\le i\le m}$. This holds with high probability and without extra assumption on the signal $x$ to be recovered, provided that the number $m$ of equations is some constant $c>0$ times the number $n$ of unknowns in the signal vector, namely, $m>cn$. Empirically, the upshots of this contribution are: i) (almost) $100\%$ perfect signal recovery in the high-dimensional (say e.g., $n\ge 2,000$) regime given only an information-theoretic limit number of noiseless equations, namely, $m=2n-1$ in the real-valued Gaussian case; and, ii) (nearly) optimal statistical accuracy in the presence of additive noise of bounded support. Finally, substantial numerical tests using both synthetic data and real images corroborate markedly improved signal recovery performance and computational efficiency of our novel procedure relative to state-of-the-art approaches.

arXiv comment27 pages, 8 figures

References in corpus (11)

• Alternating Minimization for Mixed Linear Regression
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax
• 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
• Sparse Phase Retrieval via Truncated Amplitude Flow
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption
• Phase Retrieval with One or Two Diffraction Patterns by Alternating Projection with Null Initialization

Cited by in corpus (6)

• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Sparse Phase Retrieval via Truncated Amplitude Flow
• SPRSF: Sparse Phase Retrieval via Smoothing Function
• Solving Random Systems of Quadratic Equations with Tanh Wirtinger Flow
• Multiscale Phase Retrieval
• Scalable Incremental Nonconvex Optimization Approach for Phase Retrieval