## Abstract

This paper deals with finding an n-dimensional solution x to a system of quadratic equations yi = |«a_{i}, 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 {(a_{i}; 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 language | English (US) |
---|---|

Pages (from-to) | 1868-1878 |

Number of pages | 11 |

Journal | Advances in Neural Information Processing Systems |

Volume | 2017-December |

State | Published - Jan 1 2017 |

Event | 31st Annual Conference on Neural Information Processing Systems, NIPS 2017 - Long Beach, United States Duration: Dec 4 2017 → Dec 9 2017 |