Compressive Phase Retrieval via Reweighted Amplitude Flow

Liang Zhang; Gang Wang; Georgios B. Giannakis; Jie Chen

doi:10.1109/TSP.2018.2862395

Compressive Phase Retrieval via Reweighted Amplitude Flow

Liang Zhang, Gang Wang, Georgios B. Giannakis, Jie Chen

Electrical and Computer Engineering

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

7 Scopus citations

Abstract

The problem of reconstructing a sparse signal vector from magnitude-only measurements (a.k.a. compressive phase retrieval) emerges in diverse applications, but it is NP-hard in general. Building on recent advances in nonconvex optimization, this paper puts forth a new algorithm that is termed compressive reweighted amplitude flow (CRAF) and abbreviated as CRAF, for compressive phase retrieval. Specifically, CRAF operates in two stages. The first stage seeks a sparse initial guess via a new spectral procedure. In the second stage, CRAF implements a few hard thresholding based iterations using reweighted gradients. When there are sufficient measurements, CRAF provably recovers the underlying signal vector exactly with high probability under suitable conditions. Moreover, its sample complexity coincides with that of state-of-the-art procedures. Finally, numerical tests showcase improved performance of the new spectral initialization, as well as improved exact recovery relative to competing alternatives. Empirically, the number of measurements required for exact recovery by CRAF is about 40% less than those of competing alternatives in our experiments using real images.

Original language	English (US)
Article number	8424911
Pages (from-to)	5029-5040
Number of pages	12
Journal	IEEE Transactions on Signal Processing
Volume	66
Issue number	19
DOIs	https://doi.org/10.1109/TSP.2018.2862395
State	Published - Oct 1 2018

Bibliographical note

Funding Information:
Manuscript received January 2, 2018; revised May 24, 2018; accepted July 23, 2018. Date of publication August 3, 2018; date of current version August 24, 2018. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tsung-Hui Chang. The work of L. Zhang, G. Wang, and G. B. Giannakis was supported by National Science Foundation under Grant 1423316, Grant 1442686, Grant 1508993, and Grant 1509040. The work of J. Chen was supported in part by the National Natural Science Foundation of China under Grant U1509215 and Grant 61621063, and in part by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). (Corresponding author: Georgios B. Giannakis.) L. Zhang and G. B. Giannakis are with the Digital Technology Center and the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA (e-mail:, zhan3523@umn.edu; georgios@umn.edu).

Funding Information:
The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tsung-Hui Chang. The work of L. Zhang, G. Wang, and G. B. Giannakis was supported by National Science Foundation under Grant 1423316, Grant 1442686, Grant 1508993, and Grant 1509040. The work of J. Chen was supported in part by the National Natural Science Foundation of China under Grant U1509215 and Grant 61621063, and in part by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208).

Publisher Copyright:
© 2018 IEEE.

Keywords

Nonconvex optimization
iteratively reweighting
linear convergence to the global optimum
model-based hard thresholding

Publisher link

10.1109/TSP.2018.2862395

Find It

Find It at U of M Libraries

Cite this

@article{83e87714f1e64f5ca89eb717bd1f2370,

title = "Compressive Phase Retrieval via Reweighted Amplitude Flow",

abstract = "The problem of reconstructing a sparse signal vector from magnitude-only measurements (a.k.a. compressive phase retrieval) emerges in diverse applications, but it is NP-hard in general. Building on recent advances in nonconvex optimization, this paper puts forth a new algorithm that is termed compressive reweighted amplitude flow (CRAF) and abbreviated as CRAF, for compressive phase retrieval. Specifically, CRAF operates in two stages. The first stage seeks a sparse initial guess via a new spectral procedure. In the second stage, CRAF implements a few hard thresholding based iterations using reweighted gradients. When there are sufficient measurements, CRAF provably recovers the underlying signal vector exactly with high probability under suitable conditions. Moreover, its sample complexity coincides with that of state-of-the-art procedures. Finally, numerical tests showcase improved performance of the new spectral initialization, as well as improved exact recovery relative to competing alternatives. Empirically, the number of measurements required for exact recovery by CRAF is about 40% less than those of competing alternatives in our experiments using real images.",

keywords = "Nonconvex optimization, iteratively reweighting, linear convergence to the global optimum, model-based hard thresholding",

author = "Liang Zhang and Gang Wang and Giannakis, {Georgios B.} and Jie Chen",

note = "Funding Information: Manuscript received January 2, 2018; revised May 24, 2018; accepted July 23, 2018. Date of publication August 3, 2018; date of current version August 24, 2018. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tsung-Hui Chang. The work of L. Zhang, G. Wang, and G. B. Giannakis was supported by National Science Foundation under Grant 1423316, Grant 1442686, Grant 1508993, and Grant 1509040. The work of J. Chen was supported in part by the National Natural Science Foundation of China under Grant U1509215 and Grant 61621063, and in part by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). (Corresponding author: Georgios B. Giannakis.) L. Zhang and G. B. Giannakis are with the Digital Technology Center and the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA (e-mail:, zhan3523@umn.edu; georgios@umn.edu). Funding Information: The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tsung-Hui Chang. The work of L. Zhang, G. Wang, and G. B. Giannakis was supported by National Science Foundation under Grant 1423316, Grant 1442686, Grant 1508993, and Grant 1509040. The work of J. Chen was supported in part by the National Natural Science Foundation of China under Grant U1509215 and Grant 61621063, and in part by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). Publisher Copyright: {\textcopyright} 2018 IEEE.",

year = "2018",

month = oct,

day = "1",

doi = "10.1109/TSP.2018.2862395",

language = "English (US)",

volume = "66",

pages = "5029--5040",

journal = "IRE Transactions on Audio",

issn = "1053-587X",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "19",

}

TY - JOUR

T1 - Compressive Phase Retrieval via Reweighted Amplitude Flow

AU - Zhang, Liang

AU - Wang, Gang

AU - Giannakis, Georgios B.

AU - Chen, Jie

N1 - Funding Information: Manuscript received January 2, 2018; revised May 24, 2018; accepted July 23, 2018. Date of publication August 3, 2018; date of current version August 24, 2018. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tsung-Hui Chang. The work of L. Zhang, G. Wang, and G. B. Giannakis was supported by National Science Foundation under Grant 1423316, Grant 1442686, Grant 1508993, and Grant 1509040. The work of J. Chen was supported in part by the National Natural Science Foundation of China under Grant U1509215 and Grant 61621063, and in part by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). (Corresponding author: Georgios B. Giannakis.) L. Zhang and G. B. Giannakis are with the Digital Technology Center and the Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA (e-mail:, zhan3523@umn.edu; georgios@umn.edu). Funding Information: The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tsung-Hui Chang. The work of L. Zhang, G. Wang, and G. B. Giannakis was supported by National Science Foundation under Grant 1423316, Grant 1442686, Grant 1508993, and Grant 1509040. The work of J. Chen was supported in part by the National Natural Science Foundation of China under Grant U1509215 and Grant 61621063, and in part by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1208). Publisher Copyright: © 2018 IEEE.

PY - 2018/10/1

Y1 - 2018/10/1

N2 - The problem of reconstructing a sparse signal vector from magnitude-only measurements (a.k.a. compressive phase retrieval) emerges in diverse applications, but it is NP-hard in general. Building on recent advances in nonconvex optimization, this paper puts forth a new algorithm that is termed compressive reweighted amplitude flow (CRAF) and abbreviated as CRAF, for compressive phase retrieval. Specifically, CRAF operates in two stages. The first stage seeks a sparse initial guess via a new spectral procedure. In the second stage, CRAF implements a few hard thresholding based iterations using reweighted gradients. When there are sufficient measurements, CRAF provably recovers the underlying signal vector exactly with high probability under suitable conditions. Moreover, its sample complexity coincides with that of state-of-the-art procedures. Finally, numerical tests showcase improved performance of the new spectral initialization, as well as improved exact recovery relative to competing alternatives. Empirically, the number of measurements required for exact recovery by CRAF is about 40% less than those of competing alternatives in our experiments using real images.

AB - The problem of reconstructing a sparse signal vector from magnitude-only measurements (a.k.a. compressive phase retrieval) emerges in diverse applications, but it is NP-hard in general. Building on recent advances in nonconvex optimization, this paper puts forth a new algorithm that is termed compressive reweighted amplitude flow (CRAF) and abbreviated as CRAF, for compressive phase retrieval. Specifically, CRAF operates in two stages. The first stage seeks a sparse initial guess via a new spectral procedure. In the second stage, CRAF implements a few hard thresholding based iterations using reweighted gradients. When there are sufficient measurements, CRAF provably recovers the underlying signal vector exactly with high probability under suitable conditions. Moreover, its sample complexity coincides with that of state-of-the-art procedures. Finally, numerical tests showcase improved performance of the new spectral initialization, as well as improved exact recovery relative to competing alternatives. Empirically, the number of measurements required for exact recovery by CRAF is about 40% less than those of competing alternatives in our experiments using real images.

KW - Nonconvex optimization

KW - iteratively reweighting

KW - linear convergence to the global optimum

KW - model-based hard thresholding

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

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

U2 - 10.1109/TSP.2018.2862395

DO - 10.1109/TSP.2018.2862395

M3 - Article

AN - SCOPUS:85051006150

VL - 66

SP - 5029

EP - 5040

JO - IRE Transactions on Audio

JF - IRE Transactions on Audio

SN - 1053-587X

IS - 19

M1 - 8424911

ER -

Compressive Phase Retrieval via Reweighted Amplitude Flow

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this