Sparse Phase Retrieval via Truncated Amplitude Flow

Given observed data ${psi_i}_{i=1}^m$ and feature vectors ${a_iin R^n/C^n}_{i=1}^m$ , our goal is to solve for a -sparse from a system of (phaseless) quadratic equations psi_iapprox |langle a_i,xrangle| , 1le ile m .

With sample complexity O(k^2log n) and computational complexity O(k^2nlog n) , our SPARTA provably recovers the true solution exactly.

Sparse Phase Retrieval via Truncated Amplitude Flow.

Authors: G. Wang, L. Zhang, G. B. Giannakis, M. Akcakaya, and J. Chen

This paper develops a novel algorithm, termed emph{SPARse Truncated Amplitude flow} (SPARTA), to reconstruct a sparse signal from a small number of magnitude-only measurements. It deals with what is also known as sparse phase retrieval (PR), which is emph{NP-hard} in general and emerges in many science and engineering applications. Upon formulating sparse PR as an amplitude-based nonconvex optimization task, SPARTA works iteratively in two stages: In stage one, the support of the underlying sparse signal is recovered using an analytically well-justified rule, and subsequently a sparse orthogonality-promoting initialization is obtained via power iterations restricted on the support; and, in stage two, the initialization is successively refined by means of hard thresholding based truncated gradient iterations. SPARTA is a simple yet effective, scalable, and fast sparse PR solver. On the theoretical side, for any -dimensional -sparse ( kll n ) signal with minimum (in modulus) nonzero entries on the order of $(1/sqrt{k})|x|_2$ , SPARTA recovers the signal exactly (up to a global unimodular constant) from about k^2log n random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of k^2nlog n with total runtime proportional to the time required to read the data, which improves upon the state-of-the-art by at least a factor of . Finally, SPARTA is robust against additive noise of bounded support. Extensive numerical tests corroborate markedly improved recovery performance and speedups of SPARTA relative to existing alternatives.