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

TLDR

The paper addresses the fundamental problem of solving quadratic systems of equations, whose computational complexity is currently unknown. The authors propose a novel method that uses a spectral initialization followed by Wirtinger flow–style minimization, aiming to demonstrate that random quadratic systems can be solved nearly as efficiently as linear systems. The method employs a spectral initial guess and adaptive update rules that drop overly influential terms, using a distinct objective functional and Wirtinger flow–style minimization. The algorithm achieves linear‑time recovery for certain unstructured models when the equation‑to‑unknown ratio exceeds a constant, extends to noisy systems with near‑optimal statistical accuracy, and empirically runs about four times slower than least‑squares, confirming near‑equivalence to linear system solving. © 2016 Wiley Periodicals, Inc.

Abstract

Abstract We consider the fundamental problem of solving quadratic systems of equations in , and is unknown. We propose a novel method, which starts with an initial guess computed by means of a spectral method and proceeds by minimizing a nonconvex functional as in the Wirtinger flow approach [13]. There are several key distinguishing features, most notably a distinct objective functional and novel update rules, which operate in an adaptive fashion and drop terms bearing too much influence on the search direction. These careful selection rules provide a tighter initial guess, better descent directions, and thus enhanced practical performance. On the theoretical side, we prove that for certain unstructured models of quadratic systems, our algorithms return the correct solution in linear time, i.e., in time proportional to reading the data { a i } and { y i } as soon as the ratio m / n between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems in which we only have and prove that our algorithms achieve a statistical accuracy, which is nearly unimprovable. We complement our theoretical study with numerical examples showing that solving random quadratic systems is both computationally and statistically not much harder than solving linear systems of the same size—hence the title of this paper. For instance, we demonstrate empirically that the computational cost of our algorithm is about four times that of solving a least squares problem of the same size. © 2016 Wiley Periodicals, Inc.