The Local Convexity of Solving Quadratic Equations

Authors:
  • CWChris D. White
    Chris D. White
  • RWRachel Ward
    Rachel Ward
  • SSSujay Sanghavi
    Sujay Sanghavi

Abstract
We consider the nonconvex problem of reconstructing an $n$-dimensional vector $x \in \mathbb{R}^n$ from $m$ quadratic measurements of the form $y_i := |\langle x, a_i\rangle|^2$. A spate of recent work has focused on the special case where the measurements $a_i$ are isotropic Gaussian vectors; for this it is known that $x$ can be recovered to accuracy $\eta$ by {\em (a)} computationally intensive convex optimization in a large lifted space, using $O(n)$ measurements, {\em (b)} non-convex methods based on gradient descent, or {\em (c)} non-convex methods with the number of measurements having an additional $O(\log1/\eta)$ dependence on the accuracy $\eta$. In this paper we consider the more general setting where $a_i$ are assumed to be sub-gaussian, with general full-rank covariance. For the natural non-convex objective $\min_u \sum_i (y_i - |\langle u, a_i\rangle|^2)^2$, we quantify a radius of local {\em strong convexity} around the true $x$, once the number of measurements is $m \geq C n \log^3(n)$. This implies that, in this region, gradient descent (or any other descent method) with no re-sampling will converge linearly to $x$. Furthermore, we show that for Gaussian measurements, the simple spectral initialization from Netrapalli, et al [2013] will land within the radius of convexity; this implies fast non-convex recovery without the number of samples depending on accuracy. We believe that the technique of spectral initialization into a ball of strong convexity around a global solution should prove applicable to a broader class of non-convex optimization problems.