Phase Retrieval via Reweighted Amplitude Flow

Research output: Contribution to journalArticle

11 Citations (Scopus)

Abstract

This paper deals with finding an n -dimensional solution x to a system of quadratic equations of the form y-i=a-ix2 for 1im, which is also known as the generalized phase retrieval problem. For this NP-hard problem, a novel approach is developed for minimizing the amplitude-based least-squares empirical loss, which starts with a weighted maximal correlation initialization obtainable through a few power or Lanczos iterations, followed by successive refinements based on a sequence of iteratively reweighted gradient iterations. The two stages (initialization and gradient flow) distinguish themselves from prior contributions by the inclusion of a fresh (re)weighting regularization procedure. For certain random measurement models, the novel scheme is shown to be able to recover the true solution x in time proportional to reading the data (a-i;y-i)1m. This holds with high probability and without extra assumption on the signal vector x to be recovered, provided that the number m of equations is some constant c>0 times the number n of unknowns in the signal vector, namely m>cn. Empirically, the upshots of this contribution are: first, (almost) 100% perfect signal recovery in the high-dimensional (say n2000) regime given only an information-theoretic limit number of noiseless equations, namely m=2n-1, in the real Gaussian case; and second, (nearly) optimal statistical accuracy in the presence of additive noise of bounded support. Finally, substantial numerical tests using both synthetic data and real images corroborate markedly improved recovery performance and computational efficiency of the novel scheme relative to the state-of-the-art approaches.

Original languageEnglish (US)
Pages (from-to)2818-2833
Number of pages16
JournalIEEE Transactions on Signal Processing
Volume66
Issue number11
DOIs
StatePublished - Jun 1 2018

Fingerprint

Recovery
Additive noise
Computational efficiency
Computational complexity

Keywords

  • Non-convex non-smooth optimization
  • convergence to the global optimum
  • iteratively reweighted gradient flow
  • regularization

Cite this

Phase Retrieval via Reweighted Amplitude Flow. / Wang, Gang; Giannakis, Georgios B; Saad, Yousef; Chen, Jie.

In: IEEE Transactions on Signal Processing, Vol. 66, No. 11, 01.06.2018, p. 2818-2833.

Research output: Contribution to journalArticle

@article{5cdf5f960cbf4485b4b7f5c0bdb40451,
title = "Phase Retrieval via Reweighted Amplitude Flow",
abstract = "This paper deals with finding an n -dimensional solution x to a system of quadratic equations of the form y-i=a-ix2 for 1im, which is also known as the generalized phase retrieval problem. For this NP-hard problem, a novel approach is developed for minimizing the amplitude-based least-squares empirical loss, which starts with a weighted maximal correlation initialization obtainable through a few power or Lanczos iterations, followed by successive refinements based on a sequence of iteratively reweighted gradient iterations. The two stages (initialization and gradient flow) distinguish themselves from prior contributions by the inclusion of a fresh (re)weighting regularization procedure. For certain random measurement models, the novel scheme is shown to be able to recover the true solution x in time proportional to reading the data (a-i;y-i)1m. This holds with high probability and without extra assumption on the signal vector x to be recovered, provided that the number m of equations is some constant c>0 times the number n of unknowns in the signal vector, namely m>cn. Empirically, the upshots of this contribution are: first, (almost) 100{\%} perfect signal recovery in the high-dimensional (say n2000) regime given only an information-theoretic limit number of noiseless equations, namely m=2n-1, in the real Gaussian case; and second, (nearly) optimal statistical accuracy in the presence of additive noise of bounded support. Finally, substantial numerical tests using both synthetic data and real images corroborate markedly improved recovery performance and computational efficiency of the novel scheme relative to the state-of-the-art approaches.",
keywords = "Non-convex non-smooth optimization, convergence to the global optimum, iteratively reweighted gradient flow, regularization",
author = "Gang Wang and Giannakis, {Georgios B} and Yousef Saad and Jie Chen",
year = "2018",
month = "6",
day = "1",
doi = "10.1109/TSP.2018.2818077",
language = "English (US)",
volume = "66",
pages = "2818--2833",
journal = "IEEE Transactions on Signal Processing",
issn = "1053-587X",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "11",

}

TY - JOUR

T1 - Phase Retrieval via Reweighted Amplitude Flow

AU - Wang, Gang

AU - Giannakis, Georgios B

AU - Saad, Yousef

AU - Chen, Jie

PY - 2018/6/1

Y1 - 2018/6/1

N2 - This paper deals with finding an n -dimensional solution x to a system of quadratic equations of the form y-i=a-ix2 for 1im, which is also known as the generalized phase retrieval problem. For this NP-hard problem, a novel approach is developed for minimizing the amplitude-based least-squares empirical loss, which starts with a weighted maximal correlation initialization obtainable through a few power or Lanczos iterations, followed by successive refinements based on a sequence of iteratively reweighted gradient iterations. The two stages (initialization and gradient flow) distinguish themselves from prior contributions by the inclusion of a fresh (re)weighting regularization procedure. For certain random measurement models, the novel scheme is shown to be able to recover the true solution x in time proportional to reading the data (a-i;y-i)1m. This holds with high probability and without extra assumption on the signal vector x to be recovered, provided that the number m of equations is some constant c>0 times the number n of unknowns in the signal vector, namely m>cn. Empirically, the upshots of this contribution are: first, (almost) 100% perfect signal recovery in the high-dimensional (say n2000) regime given only an information-theoretic limit number of noiseless equations, namely m=2n-1, in the real Gaussian case; and second, (nearly) optimal statistical accuracy in the presence of additive noise of bounded support. Finally, substantial numerical tests using both synthetic data and real images corroborate markedly improved recovery performance and computational efficiency of the novel scheme relative to the state-of-the-art approaches.

AB - This paper deals with finding an n -dimensional solution x to a system of quadratic equations of the form y-i=a-ix2 for 1im, which is also known as the generalized phase retrieval problem. For this NP-hard problem, a novel approach is developed for minimizing the amplitude-based least-squares empirical loss, which starts with a weighted maximal correlation initialization obtainable through a few power or Lanczos iterations, followed by successive refinements based on a sequence of iteratively reweighted gradient iterations. The two stages (initialization and gradient flow) distinguish themselves from prior contributions by the inclusion of a fresh (re)weighting regularization procedure. For certain random measurement models, the novel scheme is shown to be able to recover the true solution x in time proportional to reading the data (a-i;y-i)1m. This holds with high probability and without extra assumption on the signal vector x to be recovered, provided that the number m of equations is some constant c>0 times the number n of unknowns in the signal vector, namely m>cn. Empirically, the upshots of this contribution are: first, (almost) 100% perfect signal recovery in the high-dimensional (say n2000) regime given only an information-theoretic limit number of noiseless equations, namely m=2n-1, in the real Gaussian case; and second, (nearly) optimal statistical accuracy in the presence of additive noise of bounded support. Finally, substantial numerical tests using both synthetic data and real images corroborate markedly improved recovery performance and computational efficiency of the novel scheme relative to the state-of-the-art approaches.

KW - Non-convex non-smooth optimization

KW - convergence to the global optimum

KW - iteratively reweighted gradient flow

KW - regularization

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

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

U2 - 10.1109/TSP.2018.2818077

DO - 10.1109/TSP.2018.2818077

M3 - Article

AN - SCOPUS:85044366783

VL - 66

SP - 2818

EP - 2833

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

SN - 1053-587X

IS - 11

ER -