A Geometric Analysis of Phase Retrieval

Abstract

Can we recover a complex signal from its Fourier magnitudes? More generally, given a set of $m$ measurements, $y_k=|{\mathbf{a}}_k^{\ast }\mathbf{x}|$ for $k=1,\dots ,m$, is it possible to recover $\mathbf{x}\in {\mathbb{C}}^n$ (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 theoretical explanations. In this paper, we take a step towards bridging this gap. We prove that when the measurement vectors ${\mathbf{a}}_k$'s are generic (i.i.d. complex Gaussian) and the number of measurements is large enough ($m\ge Cn{\log }^{3}n$), 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 $\mathbf{x}$, up to a global phase; and (2) the objective function has a negative 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.

61 pages, 5 figures. A short version can be found here http://sunju.org/docs/PR_G4_16.pdf . Revised according to reviewers' feedback

References in corpus (6)

• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Nonconvex phase synchronization
• Provable Tensor Factorization with Missing Data
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Fast matrix completion without the condition number
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions

Cited by in corpus (34)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• The Numerics of Phase Retrieval
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• Multi-Frequency Phase Retrieval for Antenna Measurements
• Perturbed Amplitude Flow for Phase Retrieval
• First-Order Methods for Nonconvex Quadratic Minimization
• A variational model for data fitting on manifolds by minimizing the acceleration of a Bézier curve
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Stability estimates for phase retrieval from discrete Gabor measurements
• Synchronization of Kuramoto Oscillators in Dense Networks
• A Generalization of Wirtinger Flow for Exact Interferometric Inversion
• Sparse Signal Recovery from Phaseless Measurements via Hard Thresholding Pursuit
• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• Quantum algorithms for escaping from saddle points
• Towards Low-Photon Nanoscale Imaging: Holographic Phase Retrieval via Maximum Likelihood Optimization
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Sample-Efficient Sparse Phase Retrieval via Stochastic Alternating Minimization
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Tractability from overparametrization: The example of the negative perceptron
• Solving Phase Retrieval via Graph Projection Splitting
• Provable Sample-Efficient Sparse Phase Retrieval Initialized by Truncated Power Method
• Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
• Subspace Phase Retrieval
• Considerations for extracting moiré-level strain from dark field intensities in transmission electron microscopy
• Gradient descent provably escapes saddle points in the training of shallow ReLU networks
• On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems
• SPRING: an effective and reliable framework for image reconstruction in single-particle Coherent Diffraction Imaging
• Generalized Approximate Survey Propagation for High-Dimensional Estimation
• Three proofs of the Benedetto-Fickus theorem
• Provable Phase Retrieval with Mirror Descent
• SPIRAL: A superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Catapult Dynamics and Phase Transitions in Quadratic Nets