Sparse Phase Retrieval via Truncated Amplitude Flow

Gang Wang, Liang Zhang, Georgios B. Giannakis, Mehmet Akçakaya, Jie Chen

IEEE Transactions on Signal Processing · 2017 · 141 citations · 53 references

Concepts

Abstract

This paper develops a novel algorithm, termed 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 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 the second stage, the initialization is successively refined by means of hard thresholding based gradient-type iterations. SPARTA is a simple yet effective, scalable, and fast sparse PR solver. On the theoretical side, for any n-dimensional k-sparse (k ≪ n) signal x with minimum (in modulus) nonzero entries on the order of (1/√k)||x|| <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> , SPARTA recovers the signal exactly (up to a global unimodular constant) from about k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log n random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n log 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 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.

References

53