Sparse phase retrieval via truncated amplitude flow

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

doi:10.1109/TSP.2017.2771733

Sparse phase retrieval via truncated amplitude flow

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

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

74 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)x₂ , SPARTA recovers the signal exactly (up to a global unimodular constant) from about k² log n random Gaussian measurements with high probability. Furthermore, SPARTA incurs computational complexity on the order of k² 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	https://doi.org/10.1109/TSP.2017.2771733
State	Published - Jan 15 2018

Bibliographical note

Funding Information:
Manuscript received December 11, 2016; revised May 25, 2017 and August 25, 2017; accepted October 29, 2017. Date of publication November 8, 2017; date of current version December 22, 2017. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tsung-Hui Chang. The work of G. Wang, L. Zhang, and G. B. Giannakis was supported by NSF Grants 1500713 and 1514056. The work of M. Akc¸akaya was supported by NSF Grant 1651825. The work of J. Chen was partially supported by the National Natural Science Foundation of China Grants U1509215, 61621063, and the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). This paper was presented in part at the 42nd IEEE International Conference on Acoustics, Speech, and Signal Processing, New Orleans, LA, USA, March 5–9, 2017. (Corresponding author: Georgios B. Giannakis.) G. Wang is with the Digital Technology Center and the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA, and also with the State Key Laboratory of Intelligent Control and Decision of Complex Systems, Beijing Institute of Technology, Beijing 100081, China (e-mail: gangwang@umn.edu).

Funding Information:
The work of G. Wang, L. Zhang, and G. B. Giannakis was supported by NSF Grants 1500713 and 1514056. The work of M. Ak?akaya was supported by NSF Grant 1651825. The work of J. Chen was partially supported by the National Natural Science Foundation of China Grants U1509215, 61621063, and the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). This paper was presented in part at the 42nd IEEE International Conference on Acoustics, Speech, and Signal Processing, New Orleans, LA, USA, March 5?9, 2017. The authors would like to thank the anonymous reviewers for their thorough review and all constructive comments and suggestions, which helped to improve the quality of the manuscript. The authors also thank Prof. Xiaodong Li for sharing the codes of the thresholded Wirtinger flow algorithm.

Publisher Copyright:
© 2017 IEEE.

Keywords

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

Publisher link

10.1109/TSP.2017.2771733

Find It

Find It at U of M Libraries

Cite this

@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 Ak{\c c}akaya and Jie Chen",

note = "Funding Information: Manuscript received December 11, 2016; revised May 25, 2017 and August 25, 2017; accepted October 29, 2017. Date of publication November 8, 2017; date of current version December 22, 2017. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tsung-Hui Chang. The work of G. Wang, L. Zhang, and G. B. Giannakis was supported by NSF Grants 1500713 and 1514056. The work of M. Akc¸akaya was supported by NSF Grant 1651825. The work of J. Chen was partially supported by the National Natural Science Foundation of China Grants U1509215, 61621063, and the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). This paper was presented in part at the 42nd IEEE International Conference on Acoustics, Speech, and Signal Processing, New Orleans, LA, USA, March 5–9, 2017. (Corresponding author: Georgios B. Giannakis.) G. Wang is with the Digital Technology Center and the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA, and also with the State Key Laboratory of Intelligent Control and Decision of Complex Systems, Beijing Institute of Technology, Beijing 100081, China (e-mail: gangwang@umn.edu). Funding Information: The work of G. Wang, L. Zhang, and G. B. Giannakis was supported by NSF Grants 1500713 and 1514056. The work of M. Ak?akaya was supported by NSF Grant 1651825. The work of J. Chen was partially supported by the National Natural Science Foundation of China Grants U1509215, 61621063, and the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). This paper was presented in part at the 42nd IEEE International Conference on Acoustics, Speech, and Signal Processing, New Orleans, LA, USA, March 5?9, 2017. The authors would like to thank the anonymous reviewers for their thorough review and all constructive comments and suggestions, which helped to improve the quality of the manuscript. The authors also thank Prof. Xiaodong Li for sharing the codes of the thresholded Wirtinger flow algorithm. Publisher Copyright: {\textcopyright} 2017 IEEE.",

year = "2018",

month = jan,

day = "15",

doi = "10.1109/TSP.2017.2771733",

language = "English (US)",

volume = "66",

pages = "479--491",

journal = "IRE Transactions on Audio",

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 - Akçakaya, Mehmet

AU - Chen, Jie

N1 - Funding Information: Manuscript received December 11, 2016; revised May 25, 2017 and August 25, 2017; accepted October 29, 2017. Date of publication November 8, 2017; date of current version December 22, 2017. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tsung-Hui Chang. The work of G. Wang, L. Zhang, and G. B. Giannakis was supported by NSF Grants 1500713 and 1514056. The work of M. Akc¸akaya was supported by NSF Grant 1651825. The work of J. Chen was partially supported by the National Natural Science Foundation of China Grants U1509215, 61621063, and the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). This paper was presented in part at the 42nd IEEE International Conference on Acoustics, Speech, and Signal Processing, New Orleans, LA, USA, March 5–9, 2017. (Corresponding author: Georgios B. Giannakis.) G. Wang is with the Digital Technology Center and the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA, and also with the State Key Laboratory of Intelligent Control and Decision of Complex Systems, Beijing Institute of Technology, Beijing 100081, China (e-mail: gangwang@umn.edu). Funding Information: The work of G. Wang, L. Zhang, and G. B. Giannakis was supported by NSF Grants 1500713 and 1514056. The work of M. Ak?akaya was supported by NSF Grant 1651825. The work of J. Chen was partially supported by the National Natural Science Foundation of China Grants U1509215, 61621063, and the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). This paper was presented in part at the 42nd IEEE International Conference on Acoustics, Speech, and Signal Processing, New Orleans, LA, USA, March 5?9, 2017. The authors would like to thank the anonymous reviewers for their thorough review and all constructive comments and suggestions, which helped to improve the quality of the manuscript. The authors also thank Prof. Xiaodong Li for sharing the codes of the thresholded Wirtinger flow algorithm. Publisher Copyright: © 2017 IEEE.

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

AN - SCOPUS:85033715279

VL - 66

SP - 479

EP - 491

JO - IRE Transactions on Audio

JF - IRE Transactions on Audio

SN - 1053-587X

IS - 2

ER -

Sparse phase retrieval via truncated amplitude flow

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this