Phase Retrieval via Reweighted Amplitude Flow

Gang Wang, Georgios B. Giannakis, Yousef Saad, Jie Chen

Research output: Contribution to journalArticlepeer-review

57 Scopus citations

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

Bibliographical note

Funding Information:
Manuscript received August 15, 2017; revised January 25, 2018 and March 10, 2018; accepted March 13, 2018. Date of publication March 23, 2018; date of current version April 19, 2018. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Marco Moretti. The work of G. Wang and G. B. Giannakis was partially supported by the National Science Foundation (NSF) under Grant 1500713 and Grant 1514056. The work of Y. Saad was supported by the NSF under Grant 1505970. 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). This paper was presented in part at the Thirty-second Annual Conference on Neural Information Processing Systems, Long Beach, CA, USA, Dec. 4–9, 2017 [1]. (Corresponding author: Georgios B. Giannakis.) G. Wang 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:, gangwang@umn.edu; georgios@umn.edu).

Publisher Copyright:
© 1991-2012 IEEE.

Keywords

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

Fingerprint

Dive into the research topics of 'Phase Retrieval via Reweighted Amplitude Flow'. Together they form a unique fingerprint.

Cite this