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

By Yuxin Chen, E.J. Candes. 2015

623 citations recorded by the source corpus.

We consider the fundamental problem of solving quadratic systems of equations in yi=|〈ai,x〉|2, i=1,…,m , and x∈ℝn 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 {ai} and {yi} 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 yi≈|〈ai,x〉|2 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.

Subfields: Artificial Intelligence, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “important class of non-convex functions [16, 40, 44, 78, 79] satisfying the restricted secant inequality (RSI).”
Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “These include neural networks [18, 17, 35], matrix completion [36] and phase retrieval [6].”
The landscape of empirical risk for nonconvex losses (2016, background): “stimate is reﬁned by gradient descent (or another local procedure) initialized at θˆ(0). This general approach was studied in a number of problems including matrix completion [KOM09], phase retrieval [CC15], tensor decomposition [AGJ15]. In some cases, the local optimization stage is only proved to ”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “Some notable examples satisfying RSI include two-layer neural networks [7], matrix completion [13], dictionary learning [2], and phase retrieval [3].”
Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow (2016, methodology): “, [6]) or (3) fall under two categories: nonconvex and convex ones.”
The Landscape of the Spiked Tensor Model (2017, background): “A small subset of examples include matrix completion [17, 23], phase retrieval [12, 41], high-dimensional regression with missing data [29], and two-layer neural networks [22, 44].”
Stochastic model-based minimization of weakly convex functions (2018, background): “Numerous other nonconvex approaches to phase retrieval exist, which rely on diﬀerent problem formulations; for example, [12,15,64].”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, background): “However, one-point convexity is only known to apply to relatively simpler nonconvex tasks such as matrix completion [44], dictionary learning [11], phase transition [14] and a two-layer neural network [31], but not for complicated tasks such as training a deep neural network.”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “Another line of work [17, 23] considers the phase retrieval problem, which can be reformulated as recovering a rank one (r = 1) matrix from random quadratic measurements.”
PhaseMax: Convex Phase Retrieval via Basis Pursuit (2016, methodology): “On this dataset, measurements seem to be quite valuable, and the truncated Wirtinger flow method (with default truncation parameters as described in [28]) performs slightly worse than the original Wirtinger flow, which uses the full dataset.”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, methodology): “There is a growing list of statistical estimation problems for which nonconvex approaches are guaranteed to find global optimal solutions, including but not limited to phase retrieval [18,25,90], low-rank matrix sensing and completion [7,32,48,115,130], blind deconvolution and self-calibration [72,7”
Spectral Method and Regularized MLE Are Both Optimal for Top-$K$ Ranking (2017, neutral): “matrix completion (Keshavan, Montanari and Oh, 2010), phase retrieval (Chen and Candès, 2017), graph clustering (Rohe, Chatterjee and Yu, 2011; Abbe et al.”
Global Guarantees for Enforcing Deep Generative Priors by Empirical Risk (2017, background): “Additionally, rigorous guarantees of nonconvex recovery include other results in phase retrieval [52], [53], blind deconvolution [54]–[56], robust subspace recovery [57], discrete joint alignment [58], and more.”
A Geometric Analysis of Phase Retrieval (2016, methodology): “B Ju Sun sunju@stanford.edu Qing Qu qq2105@columbia.edu John Wright jw2966@columbia.edu 1 Department of Mathematics, Stanford University, Stanford, CA 94305, USA 2 Department of Electrical Engineering, Columbia University, New York City, NY 10027, USA Keywords Phase retrieval · Nonconvex optimizatio”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “Theorem 27 (Truncated spectral method for phase retrieval [21]): Consider phase retrieval in Section IV-B.”