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 ∈ ℝⁿ/Cⁿ a system of m quadratic equations y_i = |(a_i, x)|², i = 1, 2,⋯, m, which even for {a_i ∈ ℝⁿ/Cⁿ}^m_i=1 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; y_i)}^m_i=1. 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 orthogonality-promoting 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.