Solving random quadratic systems of equations is nearly as easy as solving linear systems

Yuxin Chen, Emmanuel J. Candès

Research output: Contribution to journalConference articlepeer-review

224 Scopus citations

Abstract

This paper is concerned with finding a solution x to a quadratic system of equations yi = |〈ai; x〉|2, i = 1,..., m. We demonstrate that it is possible to solve unstructured random quadratic systems in n variables exactly from O(n) equations in linear time, that is, in time proportional to reading the data {ai} and {yi}. This is accomplished by a novel procedure, which starting from an initial guess given by a spectral initialization procedure, attempts to minimize a nonconvex objective. The proposed algorithm distinguishes from prior approaches by regularizing the initialization and descent procedures in an adaptive fashion, which discard terms bearing too much influence on the initial estimate or search directions. These careful selection rules-which effectively serve as a variance reduction scheme-provide a tighter initial guess, more robust descent directions, and thus enhanced practical performance. Further, this procedure also achieves a nearoptimal statistical accuracy in the presence of noise. Empirically, we demonstrate that the computational cost of our algorithm is about four times that of solving a least-squares problem of the same size.

Original languageEnglish (US)
Pages (from-to)739-747
Number of pages9
JournalAdvances in Neural Information Processing Systems
Volume2015-January
StatePublished - 2015
Event29th Annual Conference on Neural Information Processing Systems, NIPS 2015 - Montreal, Canada
Duration: Dec 7 2015Dec 12 2015

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems
  • Signal Processing

Fingerprint

Dive into the research topics of 'Solving random quadratic systems of equations is nearly as easy as solving linear systems'. Together they form a unique fingerprint.

Cite this