Sparse phase retrieval via truncated amplitude flow

Research output: Contribution to journalArticle

21 Citations (Scopus)

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

Fingerprint

Additive noise
Computational complexity
Recovery

Keywords

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

Cite this

Sparse phase retrieval via truncated amplitude flow. / Wang, Gang; Zhang, Liang; Giannakis, Georgios B; Akcakaya, Mehmet; Chen, Jie.

In: IEEE Transactions on Signal Processing, Vol. 66, No. 2, 15.01.2018, p. 479-491.

Research output: Contribution to journalArticle

@article{1ad1f495da7046188036507c6335d32e,
title = "Sparse phase retrieval via truncated amplitude flow",
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.",
keywords = "Compressive sampling, Iterative hard thresholding, Linear convergence to the global optimum., Nonconvex optimization, Support recovery",
author = "Gang Wang and Liang Zhang and Giannakis, {Georgios B} and Mehmet Akcakaya and Jie Chen",
year = "2018",
month = "1",
day = "15",
doi = "10.1109/TSP.2017.2771733",
language = "English (US)",
volume = "66",
pages = "479--491",
journal = "IEEE Transactions on Signal Processing",
issn = "1053-587X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

TY - JOUR

T1 - Sparse phase retrieval via truncated amplitude flow

AU - Wang, Gang

AU - Zhang, Liang

AU - Giannakis, Georgios B

AU - Akcakaya, Mehmet

AU - Chen, Jie

PY - 2018/1/15

Y1 - 2018/1/15

N2 - 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.

AB - 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.

KW - Compressive sampling

KW - Iterative hard thresholding

KW - Linear convergence to the global optimum.

KW - Nonconvex optimization

KW - Support recovery

UR - http://www.scopus.com/inward/record.url?scp=85033715279&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85033715279&partnerID=8YFLogxK

U2 - 10.1109/TSP.2017.2771733

DO - 10.1109/TSP.2017.2771733

M3 - Article

VL - 66

SP - 479

EP - 491

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 2

ER -