Solving Random Quadratic Systems of Equations Is Nearly as Easy as\n Solving Linear Systems

Abstract

We consider the fundamental problem of solving quadratic systems of equations\nin $n$ variables, where $y_i = |\\langle \\boldsymbol{a}_i, \\boldsymbol{x}\n\\rangle|^2$, $i = 1, \\ldots, m$ and $\\boldsymbol{x} \\in \\mathbb{R}^n$ is\nunknown. We propose a novel method, which starting with an initial guess\ncomputed by means of a spectral method, proceeds by minimizing a nonconvex\nfunctional as in the Wirtinger flow approach. There are several key\ndistinguishing features, most notably, a distinct objective functional and\nnovel update rules, which operate in an adaptive fashion and drop terms bearing\ntoo much influence on the search direction. These careful selection rules\nprovide a tighter initial guess, better descent directions, and thus enhanced\npractical performance. On the theoretical side, we prove that for certain\nunstructured models of quadratic systems, our algorithms return the correct\nsolution in linear time, i.e. in time proportional to reading the data\n$\\{\\boldsymbol{a}_i\\}$ and $\\{y_i\\}$ as soon as the ratio $m/n$ between the\nnumber of equations and unknowns exceeds a fixed numerical constant. We extend\nthe theory to deal with noisy systems in which we only have $y_i \\approx\n|\\langle \\boldsymbol{a}_i, \\boldsymbol{x} \\rangle|^2$ and prove that our\nalgorithms achieve a statistical accuracy, which is nearly un-improvable. We\ncomplement our theoretical study with numerical examples showing that solving\nrandom quadratic systems is both computationally and statistically not much\nharder than solving linear systems of the same size---hence the title of this\npaper. For instance, we demonstrate empirically that the computational cost of\nour algorithm is about four times that of solving a least-squares problem of\nthe same size.\n