Compressive Phase Retrieval via Reweighted Amplitude Flow

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

Research output: Contribution to journalArticle

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 languageEnglish (US)
Article number8424911
Pages (from-to)5029-5040
Number of pages12
JournalIEEE Transactions on Signal Processing
Volume66
Issue number19
DOIs
StatePublished - Oct 1 2018

Fingerprint

Recovery
Experiments

Keywords

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

Cite this

Compressive Phase Retrieval via Reweighted Amplitude Flow. / Zhang, Liang; Wang, Gang; Giannakis, Georgios B; Chen, Jie.

In: IEEE Transactions on Signal Processing, Vol. 66, No. 19, 8424911, 01.10.2018, p. 5029-5040.

Research output: Contribution to journalArticle

@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",
year = "2018",
month = "10",
day = "1",
doi = "10.1109/TSP.2018.2862395",
language = "English (US)",
volume = "66",
pages = "5029--5040",
journal = "IEEE Transactions on Signal Processing",
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

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

VL - 66

SP - 5029

EP - 5040

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 19

M1 - 8424911

ER -