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

arXiv: https://arxiv.org/abs/1505.05114 · HTML: https://mlsanity.com/paper/1505.05114/

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2015.

## Built on by (most cited first, 30 of 50)

- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Hessian Eigenspectra of More Realistic Nonlinear Models](https://mlsanity.com/paper/2103.01519/) (2021)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [Bayes-optimal learning of an extensive-width neural network from quadratically many samples](https://mlsanity.com/paper/2408.03733/) (2024)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [Group-invariant max filtering](https://mlsanity.com/paper/2205.14039/) (2022)
- [Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors](https://mlsanity.com/paper/2106.15358/) (2021)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Bandit Phase Retrieval](https://mlsanity.com/paper/2106.01660/) (2021)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)
- [Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery](https://mlsanity.com/paper/2502.01583/) (2025)
- [Misspecified Phase Retrieval with Generative Priors](https://mlsanity.com/paper/2210.05571/) (2022)
- [The Role of the Time-Dependent Hessian in High-Dimensional Optimization](https://mlsanity.com/paper/2403.02418/) (2024)
- [Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime](https://mlsanity.com/paper/2104.10790/) (2021)
- [Spectral Estimators for Structured Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2308.14507/) (2023)
- [Sparse GCA and Thresholded Gradient Descent](https://mlsanity.com/paper/2107.00371/) (2021)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors](https://mlsanity.com/paper/2309.09032/) (2023)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [PRISTA-Net: Deep Iterative Shrinkage Thresholding Network for Coded Diffraction Patterns Phase Retrieval](https://mlsanity.com/paper/2309.04171/) (2023)
- [Stable Phase Retrieval with Mirror Descent](https://mlsanity.com/paper/2405.10754/) (2024)
- [Total Least Squares Phase Retrieval](https://mlsanity.com/paper/2102.00927/) (2021)
- [Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems](https://mlsanity.com/paper/2205.13827/) (2022)
- [Provable Phase Retrieval with Mirror Descent](https://mlsanity.com/paper/2210.09248/) (2022)
- [Robust Gradient Descent for Phase Retrieval](https://mlsanity.com/paper/2410.10623/) (2024)
- [Synthetic Principal Component Design: Fast Covariate Balancing with Synthetic Controls](https://mlsanity.com/paper/2211.15241/) (2022)
- [A New Inexact Proximal Linear Algorithm with Adaptive Stopping Criteria for Robust Phase Retrieval](https://mlsanity.com/paper/2304.12522/) (2023)
- [Poisson-Gaussian Holographic Phase Retrieval with Score-based Image Prior](https://mlsanity.com/paper/2305.07712/) (2023)

## Abstract (arXiv)

We consider the fundamental problem of solving quadratic systems of equations in n variables, where yi = |langle boldsymbolai, boldsymbolx rangle|2, i = 1, ldots, m and boldsymbolx ∈ ℝn is unknown. We propose a novel method, which starting with an initial guess computed by means of a spectral method, proceeds by minimizing a nonconvex functional as in the Wirtinger flow approach. 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 boldsymbolai 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 ≈ |langle boldsymbolai, boldsymbolx rangle|2 and prove that our algorithms achieve a statistical accuracy, which is nearly un-improvable. 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.