Sparse phase retrieval via truncated amplitude flow

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

Research output: Contribution to journalArticlepeer-review

106 Scopus citations

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)x2 , SPARTA recovers the signal exactly (up to a global unimodular constant) from about k2 log n random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of k2 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.

Original languageEnglish (US)
Pages (from-to)479-491
Number of pages13
JournalIEEE Transactions on Signal Processing
Volume66
Issue number2
DOIs
StatePublished - Jan 15 2018

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

Keywords

  • Compressive sampling
  • Iterative hard thresholding
  • Linear convergence to the global optimum.
  • Nonconvex optimization
  • Support recovery

Fingerprint

Dive into the research topics of 'Sparse phase retrieval via truncated amplitude flow'. Together they form a unique fingerprint.

Cite this