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 language | English (US) |
---|---|
Title of host publication | 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 3974-3978 |
Number of pages | 5 |
ISBN (Electronic) | 9781509041176 |
DOIs | |
State | Published - Jun 16 2017 |
Externally published | Yes |
Event | 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - New Orleans, United States Duration: Mar 5 2017 → Mar 9 2017 |
Publication series
Name | ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings |
---|---|
ISSN (Print) | 1520-6149 |
Other
Other | 2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 |
---|---|
Country/Territory | United States |
City | New Orleans |
Period | 3/5/17 → 3/9/17 |
Bibliographical note
Publisher Copyright:© 2017 IEEE.
Keywords
- Nonconvex optimization
- hard thresholding
- linear convergence
- support recovery