A Geometric Analysis of Phase Retrieval (2016-02-22T00:00:00.000000Z)

TL;DR

It is proved that when the measurement vectors are generic, 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, up to a global phase, and (2) the objective function has a negative directional curvature around each saddle point.

Abstract

Can we recover a complex signal from its Fourier magnitudes? More generally, given a set of m measurements, $$y_k = \left| \varvec{a}_k^* \varvec{x} \right| $$yk=ak∗x for $$k = 1, \ldots , m$$k=1,…,m, is it possible to recover $$\varvec{x} \in \mathbb C^n$$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 $$\varvec{a}_k$$ak’s are generic (i.i.d. complex Gaussian) and numerous enough ($$m \ge C n \log ^3 n$$m≥Cnlog3n), 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 $$\varvec{x}$$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.

Authors

John Wright

3 papers

Ju Sun

3 papers

Qing Qu

2 papers

TL;DR

Abstract

Authors

References130 items

Numerical Optimization

A Geometric Analysis of Phase Retrieval

Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space

An Elementary Proof of Convex Phase Retrieval in the Natural Parameter Space via the Linear Program PhaseMax

Solving large-scale systems of random quadratic equations via stochastic truncated amplitude flow

PhaseMax: Convex Phase Retrieval via Basis Pursuit

Phase Retrieval Meets Statistical Learning Theory: A Flexible Convex Relaxation

Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach

Phase Retrieval With Random Gaussian Sensing Vectors by Alternating Projections

Non-Convex Phase Retrieval From STFT Measurements

Phaseless Recovery Using the Gauss–Newton Method

Gauss-Newton Method for Phase Retrieval

The non-convex Burer-Monteiro approach works on smooth semidefinite programs

Phase Retrieval via Incremental Truncated Wirtinger Flow

Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow

No bad local minima: Data independent training error guarantees for multilayer neural networks

Reshaped Wirtinger Flow for Solving Quadratic System of Equations

Matrix Completion has No Spurious Local Minimum

Deep Learning without Poor Local Minima

Global Optimality of Local Search for Low Rank Matrix Recovery

Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions

Provable Non-convex Phase Retrieval with Outliers: Median TruncatedWirtinger Flow

Efficient approaches for escaping higher order saddle points in non-convex optimization

Gradient Descent Converges to Minimizers

On the low-rank approach for semidefinite programs arising in synchronization and community detection

Nonconvex Phase Synchronization

Speeding up sum-of-squares for tensor decomposition and planted sparse vectors

Blind Recovery of Sparse Signals From Subsampled Convolution

RIP-like Properties in Subsampled Blind Deconvolution

Greed is Super: A Fast Algorithm for Super-Resolution

Guarantees of Riemannian Optimization for Low Rank Matrix Recovery

Phase Retrieval: An Overview of Recent Developments

When Are Nonconvex Problems Not Scary?

Tensor vs. Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations

Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees

Computing Matrix Squareroot via Non Convex Local Search

Low-rank Solutions of Linear Matrix Equations via Procrustes Flow

The Local Convexity of Solving Quadratic Equations

A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements

Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow

Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems

Complete dictionary recovery over the sphere

Phase Retrieval with Application to Optical Imaging: A contemporary overview

Escaping From Saddle Points - Online Stochastic Gradient for Tensor Decomposition

Simple, Efficient, and Neural Algorithms for Sparse Coding

Provable Tensor Methods for Learning Mixtures of Classifiers

Finding a Sparse Vector in a Subspace: Linear Sparsity Using Alternating Directions

Guaranteed Matrix Completion via Non-Convex Factorization

Analyzing Tensor Power Method Dynamics: Applications to Learning Overcomplete Latent Variable Models

Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems

Fast Exact Matrix Completion with Finite Samples

Non-convex Robust PCA

Phase Retrieval via Wirtinger Flow: Theory and Algorithms

Provable Tensor Factorization with Missing Data

Fast matrix completion without the condition number

A strong restricted isometry property, with an application to phaseless compressed sensing

Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates

More Algorithms for Provable Dictionary Learning

Understanding Alternating Minimization for Matrix Completion

Near Optimal Compressed Sensing of Sparse Rank-One Matrices via Sparse Power Factorization

Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization

Alternating Minimization for Mixed Linear Regression

Phase Retrieval from Coded Diffraction Patterns

A Partial Derandomization of PhaseLift Using Spherical Designs

Exact Recovery of Sparsely Used Overcomplete Dictionaries

New Algorithms for Learning Incoherent and Overcomplete Dictionaries

Manopt, a matlab toolbox for optimization on manifolds

Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery

Erratum: High Resolution 3D X-Ray Diffraction Microscopy [Phys. Rev. Lett.89, 088303 (2002)]

Phase Retrieval Using Alternating Minimization

Concentration Inequalities: A Nonasymptotic Theory of Independence

Sparse phase retrieval: Convex algorithms and limitations

Quadratic Basis Pursuit

GESPAR: Efficient Phase Retrieval of Sparse Signals

Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices

Efficient phase retrieval of sparse signals