SPARTA: Sparse phase retrieval via Truncated Amplitude flow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

A linear-time algorithm termed SPARse Truncated Amplitude flow (SPARTA) is developed for the phase retrieval (PR) of sparse signals. Upon formulating the sparse PR as a non-convex empirical loss minimization task, SPARTA emerges as an iterative solver consisting of two components: s1) a sparse orthogonality-promoting initialization leveraging support recovery and principal component analysis; and, s2) a series of refinements by hard thresholding based truncated gradient iterations. SPARTA is simple, scalable, and fast. It recovers any k-sparse n-dimensional signal (k ≪ n) of large enough minimum (in modulus) nonzero entries from about k2 log n measurements with high probability; this is achieved at computational complexity of order k2n log n, improving upon the state-of-the-art by at least a factor of k. SPARTA is robust against bounded additive noise. Simulated tests corroborate the merits of SPARTA relative to existing alternatives.

Original languageEnglish (US)
Title of host publication2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3974-3978
Number of pages5
ISBN (Electronic)9781509041176
DOIs
StatePublished - Jun 16 2017
Event2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - New Orleans, United States
Duration: Mar 5 2017Mar 9 2017

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)1520-6149

Other

Other2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017
CountryUnited States
CityNew Orleans
Period3/5/173/9/17

Bibliographical note

Funding Information:
Work in this paper was supported in part by NSF grants 1500713 and 1514056.

Publisher Copyright:
© 2017 IEEE.

Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

Keywords

  • Nonconvex optimization
  • hard thresholding
  • linear convergence
  • support recovery

Fingerprint Dive into the research topics of 'SPARTA: Sparse phase retrieval via Truncated Amplitude flow'. Together they form a unique fingerprint.

Cite this