Solving most systems of random quadratic equations

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

Research output: Contribution to journalConference articlepeer-review

14 Scopus citations

Abstract

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
Volume2017-December
StatePublished - Jan 1 2017
Event31st Annual Conference on Neural Information Processing Systems, NIPS 2017 - Long Beach, United States
Duration: Dec 4 2017Dec 9 2017

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

Cite this