Abstract
Can we recover a complex signal from its Fourier magnitudes? More generally, given a set of m measurements, yk=|ak∗x| for k= 1 , … , m, is it possible to recover x∈ Cn (i.e., length-n complex vector)? This generalized phase retrieval (GPR) problem is a fundamental task in various disciplines and has been the subject of much recent investigation. Natural nonconvex heuristics often work remarkably well for GPR in practice, but lack clear theoretic explanations. In this paper, we take a step toward bridging this gap. We prove that when the measurement vectors ak’s are generic (i.i.d. complex Gaussian) and numerous enough (m≥ Cnlog 3n), with high probability, a natural least-squares formulation for GPR has the following benign geometric structure: (1) There are no spurious local minimizers, and all global minimizers are equal to the target signal x, up to a global phase, and (2) the objective function has a negative directional curvature around each saddle point. This structure allows a number of iterative optimization methods to efficiently find a global minimizer, without special initialization. To corroborate the claim, we describe and analyze a second-order trust-region algorithm.
Original language | English (US) |
---|---|
Pages (from-to) | 1131-1198 |
Number of pages | 68 |
Journal | Foundations of Computational Mathematics |
Volume | 18 |
Issue number | 5 |
DOIs | |
State | Published - Oct 1 2018 |
Externally published | Yes |
Bibliographical note
Funding Information:Acknowledgements 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 CCF 1527809 and NSF IIS 1546411. We thank Nicolas Boumal for helpful discussion related to the Manopt package. We thank Mahdi Soltanolkotabi for pointing us to his early result on the local convexity around the target set for GPR in Rn. We also thank Yonina Eldar, Kishore Jaganathan and Xiaodong Li for helpful feedback on a prior version of this paper. We also thank the anonymous reviewers for their careful reading of the paper and for constructive comments which have helped us to substantially improve the presentation.
Publisher Copyright:
© 2017, SFoCM.
Keywords
- Function landscape
- Inverse problems
- Mathematical imaging
- Nonconvex optimization
- Phase retrieval
- Ridable saddles
- Second-order geometry
- Trust-region method