Solving most systems of random quadratic equations

Gang Wang, Georgios B Giannakis, Yousef Saad, Jie Chen

Research output: Contribution to journalConference articlepeer-review

17 Scopus citations


This paper deals with finding an n-dimensional solution x to a system of quadratic equations yi = |«ai, x»|2 1 ≤ i ≤ m, which in general is known to be NP-hard. We put forth a novel procedure, that starts with a weighted maximal correlation initialization obtainable with a few power iterations, followed by successive refinements based on iteratively reweighted gradient-type iterations. The novel techniques distinguish themselves from prior works by the inclusion of a fresh (re)weighting regularization. For certain random measurement models, the proposed procedure returns the true solution x with high probability in time proportional to reading the data {(ai; yi)}1≤i≤m, provided that the number m of equations is some constant c > 0 times the number n of unknowns, that is, m ≥ cn. Empirically, the upshots of this contribution are: i) perfect signal recovery in the high-dimensional regime given only an information-theoretic limit number of equations; and, ii) (near-)optimal statistical accuracy in the presence of additive noise. Extensive numerical tests using both synthetic data and real images corroborate its improved signal recovery performance and computational efficiency relative to state-of-the-art approaches.

Original languageEnglish (US)
Pages (from-to)1868-1878
Number of pages11
JournalAdvances in Neural Information Processing Systems
StatePublished - 2017
Event31st Annual Conference on Neural Information Processing Systems, NIPS 2017 - Long Beach, United States
Duration: Dec 4 2017Dec 9 2017

Bibliographical note

Funding Information:
G. Wang and G. B. Giannakis were partially supported by NSF grants 1500713 and 1514056. Y. Saad was partially supported by NSF grant 1505970. J. Chen was partially supported by the National Natural Science Foundation of China grants U1509215, 61621063, and the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208).


Dive into the research topics of 'Solving most systems of random quadratic equations'. Together they form a unique fingerprint.

Cite this