Solving large-scale systems of random quadratic equations via stochastic truncated amplitude flow

This work develops a new iterative algorithm, which is called stochastic truncated amplitude flow (STAF), to recover an unknown signal x ϵ Rⁿ from m "phaseless" quadratic equations of the form i = |aTi x|, 1 < i < m. This problem is also known as phase retrieval, which is NP-hard in general. Building on an amplitude-based nonconvex least-squares formulation, STAF proceeds in two stages: s1) Orthogonality-promoting initialization computed using a stochastic variance reduced gradient algorithm; and, s2) Refinements of the initial point through truncated stochastic gradient-type iterations. Both stages handle a single equation per iteration, therefore lending STAF well to Big Data applications. Specifically for independent Gaussian {ai}mi =1 vectors, STAF recovers exactly any x exponentially fast when there are about as many equations as unknowns. Finally, numerical tests demonstrate that STAF improves upon its competing alternatives.