Solving Random Systems of Quadratic Equations via Truncated Generalized Gradient Flow
This paper puts forth a novel algorithm, termed truncated generalized gradient flow (TGGF), to solve for x ∈ R n /C n a system of m quadratic equations
random is known to be NP-hard in general. We prove that as soon as the number of equations m is on the order of the number of unknowns n, TGGF recovers the solution exactly (up to a global unimodular constant) with high probability and complexity growing linearly with the time required to read the data {(a i ;
. Specifically, TGGF proceeds in two stages: s1) A novel orthogonality-promoting initialization that is obtained with simple power iterations; and, s2) a refinement of the initial estimate by successive updates of scalable truncated generalized gradient iterations. The former is in sharp contrast to the existing spectral initializations, while the latter handles the rather challenging nonconvex and nonsmooth amplitude-based cost function. Empirical results demonstrate that: i) The novel orthogonalitypromoting initialization method returns more accurate and robust estimates relative to its spectral counterparts; and, ii) even with the same initialization, our refinement/truncation outperforms Wirtinger-based alternatives, all corroborating the superior performance of TGGF over state-of-the-art algorithms.
The problem of recovering a vector from quadratic measurements (a.k.a. phase retrieval) is studied. This paper follows the now-standard recipe of formulating a (non-convex) optimization problem, which is solved by a gradient-descent-like method with suitable initialization. However, key changes are made to both the initialization and the gradient-descent stage: 1) As in existing works, the initialization is obtained as an eigenvector of a matrix. However, the matrix proposed in this paper is quite different from that used in existing methods. The improved sample complexity due to this change is demonstrated clearly in the numerical experiments (Figs. 3 and 4). 2) The refinement post-initialization is essentially gradient-descent, but ignoring a few undesirable data points at each iteration. The novelty here compared to existing works is that both the objective function and the truncation rule are new. The improved sample complexity due to this change is depicted in Fig. 1.  The overall advantages of the new method in terms of sample complexity are depicted in Fig. 5. The computational complexity is not significantly better than existing methods.
1) Figure 1 provides a comparison of different algorithms which are all initialized using the truncated spectral initialization. Here, the success rate of TWF is significantly worse than TGGF. It would be very interesting to see what happens if the initialization is replaced by the new initialization proposed in this paper. Is the success rate of TWF still worse than TGGF? If not, then it will tell us that the improvement of TGGF can be essentially attributed to the improved initialization. If yes, then it increases the strength of this paper by giving evidence for improvement which is due to the second stage. 2) The TWF paper also provides some experiments using structured sensing vectors (coded diffraction patterns). How does TGGF perform if the sensing vectors are structured and not random? 3) While the empirical results in the noisy case are very good, theoretical results for the noisy case are missing. This is not a major concern about this paper, because the empirical results for both the noiseless and noisy case, and the theoretical results for the noiseless case are already good. 4) For the noisy case, the measurement model is considered to be |a_i^Tx + eta_i| instead of |a_i^Tx|^2 + eta_i as in some earlier papers. Also, eta_i is assumed to be Gaussian, not Poisson or arbitrary. Since the paper anyway does not provide theoretical results for the noisy case, can numerical experiments for the case of Poisson noise be provided, which is a good model for imaging applications? 5) Is the improvement of TGGF over TWF purely in terms of the sample complexity? Say n=1000 and m=8000. How does the rate of convergence of TGGF compare with that of TWF?