# The local convexity of solving systems of quadratic equations

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2015.

## Built on by (most cited first, 6 of 6)

- [Convergence of Alternating Gradient Descent for Matrix Factorization](https://mlsanity.com/paper/2305.06927/) (2023)
- [Sudakov-Fernique post-AMP, and a new proof of the local convexity of the TAP free energy](https://mlsanity.com/paper/2208.09550/) (2022)
- [Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization](https://mlsanity.com/paper/2302.07851/) (2023)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems](https://mlsanity.com/paper/2205.13827/) (2022)
- [Acceleration and Implicit Regularization in Gaussian Phase Retrieval](https://mlsanity.com/paper/2311.12888/) (2023)

## Abstract (arXiv)

This paper considers the recovery of a rank r positive semidefinite matrix X XT∈ℝn× n from m scalar measurements of the form yi := aiT X XT ai (i.e., quadratic measurements of X). Such problems arise in a variety of applications, including covariance sketching of high-dimensional data streams, quadratic regression, quantum state tomography, among others. A natural approach to this problem is to minimize the loss function f(U) = sumi (yi - aiTUUTai)2 which has an entire manifold of solutions given by XOO∈Or where Or is the orthogonal group of r× r orthogonal matrices; this is it non-convex in the n× r matrix U, but methods like gradient descent are simple and easy to implement (as compared to semidefinite relaxation approaches). In this paper we show that once we have m ≥ C nr log2(n) samples from isotropic gaussian ai, with high probability em (a) this function admits a dimension-independent region of em local strong convexity on lines perpendicular to the solution manifold, and em (b) with an additional polynomial factor of r samples, a simple spectral initialization will land within the region of convexity with high probability. Together, this implies that gradient descent with initialization (but no re-sampling) will converge linearly to the correct X, up to an orthogonal transformation. We believe that this general technique (local convexity reachable by spectral initialization) should prove applicable to a broader class of nonconvex optimization problems.