Part of Advances in Neural Information Processing Systems 29 (NIPS 2016)
Gang Wang, Georgios Giannakis
This paper puts forth a novel algorithm, termed \emph{truncated generalized gradient flow} (TGGF), to solve for \bmx∈Rn/Cn a system of m quadratic equations yi=|⟨\bmai,\bmx⟩|2, i=1,2,…,m, which even for {\bmai∈Rn/Cn}mi=1 random is known to be \emph{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 {(\bmai;yi)}mi=1. Specifically, TGGF proceeds in two stages: s1) A novel \emph{orthogonality-promoting} initialization that is obtained with simple power iterations; and, s2) a refinement of the initial estimate by successive updates of scalable \emph{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 \emph{amplitude-based} cost function. Numerical tests 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.