PROJECT TITLE :

Scalable Solvers of Random Quadratic Equations via Stochastic Truncated Amplitude Flow - 2017

ABSTRACT:

A novel approach termed stochastic truncated amplitude flow (STAF) is developed to reconstruct an unknown n-dimensional real-/complicated-valued signal x from m “phaseless” quadratic equations of the form ?i = I(ai, x)I. This problem, also called section retrieval from magnitude-solely info, is NP-exhausting normally. Adopting an amplitude-primarily based nonconvex formulation, STAF results in an iterative solver comprising two stages: s1) Orthogonality-promoting initialization through a stochastic variance reduced gradient algorithm; and, s2) a series of iterative refinements of the initialization using stochastic truncated gradient iterations. Both stages involve one equation per iteration, so rendering STAF a easy, scalable, and quick approach amenable to giant-scale implementations that are helpful when n is large. When aii= 1m are independent Gaussian, STAF provably recovers precisely any x ? Rn exponentially fast based mostly on order of n quadratic equations. STAF is also robust within the presence of additive noise of bounded support. Simulated tests involving real Gaussian ai vectors demonstrate that STAF empirically reconstructs any x ? Rnexactly from about 2.3n magnitude-solely measurements, outperforming state-of-the-art approaches and narrowing the gap from the data-theoretic range of equations m = 2n - one. Extensive experiments using synthetic data and real pictures corroborate markedly improved performance of STAF over existing alternatives.