Sparse Phase Retrieval via Truncated Amplitude Flow

Citation data:

IEEE Transactions on Signal Processing, ISSN: 1053-587X, Vol: 66, Issue: 2, Page: 479-491

Publication Year:
2018
Captures 8
Readers 8
Citations 8
Citation Indexes 8
DOI:
10.1109/tsp.2017.2771733
Author(s):
Gang Wang; Liang Zhang; Georgios B. Giannakis; Mehmet Akcakaya; Jie Chen
Publisher(s):
Institute of Electrical and Electronics Engineers (IEEE)
Tags:
Computer Science; Engineering
article description
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, SPARTA recovers the signal exactly (up to a global unimodular constant) from about klog n random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of kn 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.