Sparse Phase Retrieval via Truncated Amplitude Flow
 Citation data:

IEEE Transactions on Signal Processing, ISSN: 1053587X, Vol: 66, Issue: 2, Page: 479491
 Publication Year:
 2018
article description
This paper develops a novel lineartime algorithm, termed SPARse Truncated Amplitude flow (SPARTA), to reconstruct a sparse signal from a small number of magnitudeonly measurements. It deals with what is also known as sparse phase retrieval (PR), which is NPhard in general and emerges in many science and engineering applications. Upon formulating sparse PR as an amplitudebased nonconvex optimization task, SPARTA works iteratively in two stages: In stage one, the support of the underlying sparse signal is recovered using an analytically welljustified rule, and subsequently a sparse orthogonalitypromoting 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 $n$dimensional $k$sparse ($k\ll n$) signal $\bm{x}$ with minimum (in modulus) nonzero entries on the order of $(1/\sqrt{k})\\bm{x}\_2$, SPARTA recovers the signal exactly (up to a global unimodular constant) from about $k^2\log n$ random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of $k^2n\log n$ with total runtime proportional to the time required to read the data, which improves upon the stateoftheart by at least a factor of $k$. 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.