Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
This paper is concerned with finding a solution x to a quadratic system of equations y i = | a i , x | 2 , i = 1, . . . , m. We demonstrate that it is possible to solve unstructured random quadratic systems in n variables exactly from O(n) equations in linear time, that is, in time proportional to reading the data {a i } and {y i }. This is accomplished by a novel procedure, which starting from an initial guess given by a spectral initialization procedure, attempts to minimize a nonconvex objective. The proposed algorithm distinguishes from prior approaches by regularizing the initialization and descent procedures in an adaptive fashion, which discard terms bearing too much influence on the initial estimate or search directions. These careful selection rules-which effectively serve as a variance reduction scheme-provide a tighter initial guess, more robust descent directions, and thus enhanced practical performance. Further, this procedure also achieves a nearoptimal statistical accuracy in the presence of noise. Empirically, we demonstrate that the computational cost of our algorithm is about four times that of solving a least-squares problem of the same size.
Summary: The paper is concerned with solving a quadratic system of equations. Such problem, appears in a variety of applications, ranging from physics (phase retrieval), to mixed regression (which is of certain interest to the NIPS audience). In fact, the authors propose a quite general way of minimizing a non-convex objective function relying on truncated versions of its gradient (truncated Wirtinger flow), and this may have other implications as in matrix completion or dictionary learning.            Quality: The paper is a very nice piece of work.            Clarity: The paper is well-written, though the technicalities could not be included for obvious space limitations, but can be found in the supplemntary material (and the arxiv version).                  Originality: Phase retrieval via Wirtinger flow (WT) was already propose in [14]. In this paper, the authors propose key algorithmic changes based on a truncated version of WF (TWF) yielding enhanced performance compared WF. TWF operates only upon a subset of data enabling better descent directions, and moves in a more aggressive way in these directions. Under Gaussian design, the approach is shown to provably optimal (in sample complexity, reaching the information theoretic limit) in the noiseless case, stable to noise, and runs in linear-time complexity.             Comments:     1) Figure 5 (a) and (b): in the text, the corresponding experiments are in the noiseless setting. So speaking of Poisson and Gaussian likelihood in the legend is meaningless. Please correct.     2) Figure 5: (b) should be complex Gaussian design.     3) Figure 5 and page 8, line 410-413: the slope should rather be -1/2 because of the square-root on SNR.     4) I found that a clear discussion of the theoretical value of the universal constant c_0 is missing, and should be included and compared to the empirical bounds 5 (real) and 4.5 (complex) claimed in the text.