The local convexity of solving systems of quadratic equations

This paper considers the recovery of a rank r positive semidefinite matrix X XTn× n from m scalar measurements of the form yᵢ := aᵢT X XT aᵢ (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) = ∑ᵢ (yᵢ - aᵢTUUTaᵢ)² which has an entire manifold of solutions given by ᵣ where Oᵣ is the orthogonal group of r× r orthogonal matrices; this is { 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 log²(n) samples from isotropic gaussian aᵢ, with high probability { (a)} this function admits a dimension-independent region of { local strong convexity} on lines perpendicular to the solution manifold, and { (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.