English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider the fundamental problem of solving quadratic systems of equationsin $n$ variables, where $y_i = |\langle \boldsymbol{a}_i, \boldsymbol{x}\rangle|^2$, $i = 1, \ldots, m$ and $\boldsymbol{x} \in \mathbb{R}^n$ isunknown. We propose a novel method, which starting with an initial guesscomputed by means of a spectral method, proceeds by minimizing a nonconvexfunctional as in the Wirtinger flow approach. There are several keydistinguishing features, most notably, a distinct objective functional andnovel update rules, which operate in an adaptive fashion and drop terms bearingtoo much influence on the search direction. These careful selection rulesprovide a tighter initial guess, better descent directions, and thus enhancedpractical performance. On the theoretical side, we prove that for certainunstructured models of quadratic systems, our algorithms return the correctsolution in linear time, i.e. in time proportional to reading the data$\{\boldsymbol{a}_i\}$ and $\{y_i\}$ as soon as the ratio $m/n$ between thenumber of equations and unknowns exceeds a fixed numerical constant. We extendthe theory to deal with noisy systems in which we only have $y_i \approx|\langle \boldsymbol{a}_i, \boldsymbol{x} \rangle|^2$ and prove that ouralgorithms achieve a statistical accuracy, which is nearly un-improvable. Wecomplement our theoretical study with numerical examples showing that solvingrandom quadratic systems is both computationally and statistically not muchharder than solving linear systems of the same size---hence the title of thispaper. For instance, we demonstrate empirically that the computational cost ofour algorithm is about four times that of solving a least-squares problem ofthe same size.

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