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 × ϵ Rⁿ from m "phaseless" quadratic equations of the form ψ₁=|a^τ_i 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 {a_i}^m_i=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.