The local convexity of solving systems of quadratic equations (Q2410810)

The authors consider the recovery of a rank \(r\) positive semidefinite matrix \(X\,X^T\in {\mathbb R}^{n\times n}\) from \(m\) scalar quadratic measurements of \(X\) of the form \(y_i:=a_i^T \,X\,X^T\,a_i\). 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 \(\{X\,O\}_{O\in {\mathcal O}_r}\), where \({\mathcal O}_r\) is the orthogonal group of \(r\times r\) orthogonal matrices. This is non-convex in the \(n\times r \) matrix \(U\), but methods like gradient descent are simple and easy to implement. In this paper, it is shown that once one has \(m\geq C n r \log^2(n)\) samples from isotropic Gaussian \(a_i\), with high probability, then: (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. This general technique (local convexity reachable by spectral initialization) should prove to be applicable to a broader class of nonconvex optimization problems.