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 language | English (US) |
|---|---|
| Pages (from-to) | 479-491 |
| Number of pages | 13 |
| Journal | IEEE Transactions on Signal Processing |
| Volume | 66 |
| Issue number | 2 |
| DOIs | |
| State | Published - Jan 15 2018 |
Fingerprint
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 journal › Article
}
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 -