A geometric analysis of phase retrieval

Ju Sun, Qing Qu, John Wright

Research output: Chapter in Book/Report/Conference proceedingConference contribution

75 Scopus citations

Abstract

Given nonlinear measurements yk = |〈ak, x〉| for k = 1.,m, is it possible to recover x ⋯ Cn? This generalized phase retrieval (GPR) problem is a fundamental task in various disciplines. Natural nonconvex methods often work remarkably well for GPR in practice, but lack clear theoretical explanations. In this paper, we take a step towards bridging this gap. We show that when the sensing vectors ak's are generic (i.i.d. complex Gaussian) and the number of measurements is large enough (m ≥ Cn log3 n), with high probability (w.h.p.), a natural least-squares formulation for GPR has the following benign geometric structure: (1) all local minimizers are global-they are the target signal x and its equivalent copies; and (2) the objective function has a negative directional curvature around each saddle point. Such structure allows a number of algorithmic possibilities for efficient global optimization. We describe a second-order trust-region algorithm that provably finds a global minimizer in polynomial time, from arbitrary initializations.

Original languageEnglish (US)
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2379-2383
Number of pages5
ISBN (Electronic)9781509018062
DOIs
StatePublished - Aug 10 2016
Externally publishedYes
Event2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain
Duration: Jul 10 2016Jul 15 2016

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2016-August
ISSN (Print)2157-8095

Other

Other2016 IEEE International Symposium on Information Theory, ISIT 2016
Country/TerritorySpain
CityBarcelona
Period7/10/167/15/16

Bibliographical note

Funding Information:
This work was partially supported by funding from the Gordon and Betty Moore Foundation, the Alfred P. Sloan Foundation, and the grants ONR N00014-13-1-0492, NSF 1343282, NSF CCF 1527809, and NSF IIS 1546411

Publisher Copyright:
© 2016 IEEE.

Fingerprint

Dive into the research topics of 'A geometric analysis of phase retrieval'. Together they form a unique fingerprint.

Cite this