The local convexity of solving systems of quadratic equations

Abstract

This paper considers the recovery of a rank $r$ positive semidefinite matrix $X{X}^T\in {\mathbb{R}}^{n\times n}$ from $m$ scalar measurements of the form $y_i:=a_i^{T}X{X}^T{a}_i$ (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)={\sum }_i(y_i-a_i^{T}U{U}^T{a}_i{)}^2$ which has an entire manifold of solutions given by $\{XO{\}}_{O\in {\mathcal{O}}_r}$ where ${\mathcal{O}}_r$ is the orthogonal group of $r\times r$ orthogonal matrices; this is {\it non-convex} in the $n\times 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\ge Cnr{\log }^2(n)$ samples from isotropic gaussian $a_i$, 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.

36 pages, 3 figures

References in corpus (5)

• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• Complete Dictionary Recovery over the Sphere
• Reconstruction of Signals from Magnitudes of Redundant Representations

Cited by in corpus (13)

• An overview of low-rank matrix recovery from incomplete observations
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• When Are Nonconvex Problems Not Scary?
• Solving Large-scale Systems of Random Quadratic Equations via Stochastic Truncated Amplitude Flow
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Dropping Convexity for Faster Semi-definite Optimization
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• A Non-Convex Blind Calibration Method for Randomised Sensing Strategies
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Generalized phase retrieval : measurement number, matrix recovery and beyond
• On Gradient Descent Algorithm for Generalized Phase Retrieval Problem
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations