## Solving Most Systems of Random Quadratic Equations
Paper details
## Solving Most Systems of Random Quadratic Equations (Preprint),(Poster)Authors: G. Wang, G. B. Giannakis, Y. Saad, and J. Chen This paper deals with finding an -dimensional solution to a system of quadratic equations of the form for , 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 in time proportional to reading the data . This holds with high probability and without extra assumption on the signal to be recovered, provided that the number of equations is some constant times the number of unknowns in the signal vector, namely, . Empirically, the upshots of this contribution are: i) (almost) perfect signal recovery in the high-dimensional (say e.g., ) regime given only an emph{information-theoretic limit} number of noiseless equations, namely, 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. |