The local convexity of solving systems of quadratic equations (Q2410810): Difference between revisions
From MaRDI portal
Latest revision as of 14:43, 14 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The local convexity of solving systems of quadratic equations |
scientific article |
Statements
The local convexity of solving systems of quadratic equations (English)
0 references
19 October 2017
0 references
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.
0 references
quadratic equations
0 references
nonconvex optimization problems
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references