A geometric analysis of phase retrieval

DOI10.1007/S10208-017-9365-9MaRDI QIDQ1785008zbMATH OpenOpenAlexFDO

Authors G. Richomme

Publication date 27 September 2018

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.06664

zbMATH Keywords

function landscapeinverse problemsmathematical imagingnonconvex optimizationphase retrievalridable saddlessecond-order geometrytrust-region method

Mathematics Subject Classification ID

Optimality conditions for problems involving randomness (49K45) Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Applications of mathematical programming (90C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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 }mathbfx|$ for $k=1,dots,m$, is it possible to recover $mathbfxinmathbb{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 ($mgeCnlo{g}^{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 $mathbfx$, 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.

Recommendations

• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• Phase retrieval via Wirtinger flow: theory and algorithms
• The global landscape of phase retrieval. I: Perturbed amplitude models
• Phase retrieval for sub-Gaussian measurements

Cites work

• A Clustering Approach to Learning Sparsely Used Overcomplete Dictionaries
• A flexible convex relaxation for phase retrieval
• A nonconvex approach for phase retrieval: reshaped Wirtinger flow and incremental algorithms
• A partial derandomization of phaselift using spherical designs
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• A strong restricted isometry property, with an application to phaseless compressed sensing
• Analyzing tensor power method dynamics in overcomplete regime
• Array imaging using intensity-only measurements
• Blind Recovery of Sparse Signals From Subsampled Convolution
• Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method
• Complexity bounds for second-order optimality in unconstrained optimization
• Computing a Trust Region Step
• Concentration inequalities. A nonasymptotic theory of independence
• Cubic regularization of Newton method and its global performance
• Curvilinear path steplength algorithms for minimization which use directions of negative curvature
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Finding a Sparse Vector in a Subspace: Linear Sparsity Using Alternating Directions
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• Gradient descent only converges to minimizers: non-isolated critical points and invariant regions
• Guaranteed Matrix Completion via Non-Convex Factorization
• Guarantees of Riemannian optimization for low rank matrix recovery
• High-dimensional covariance decomposition into sparse Markov and independence models
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• scientific article; zbMATH DE number 3245393 (Why is no real title available?)
• Learning sparsely used overcomplete dictionaries via alternating minimization
• Low-rank matrix completion using alternating minimization
• Manopt, a Matlab toolbox for optimization on manifolds
• Matrix Completion From a Few Entries
• Near-Optimal Compressed Sensing of a Class of Sparse Low-Rank Matrices Via Sparse Power Factorization
• Non-Convex Phase Retrieval From STFT Measurements
• Nonconvex phase synchronization
• On affine scaling algorithms for nonconvex quadratic programming
• On signal reconstruction without phase
• Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow
• Painless reconstruction from magnitudes of frame coefficients
• Phase recovery, MaxCut and complex semidefinite programming
• Phase retrieval from coded diffraction patterns
• Phase retrieval via matrix completion
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phase retrieval with polarization
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• PhaseMax: Convex Phase Retrieval via Basis Pursuit
• Quantum tomography under prior information
• Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Sparse signal recovery from quadratic measurements via convex programming
• The local convexity of solving systems of quadratic equations
• The Pauli problem, state reconstruction and quantum-real numbers
• The trust region subproblem and semidefinite programming*
• Trust Region Methods
• Trust-region methods on Riemannian manifolds

Cited in

(only showing first 100 items - show all)

• Subgradient methods for sharp weakly convex functions
• On global convergence of gradient descent algorithms for generalized phase retrieval problem
• Using negative curvature in solving nonlinear programs
• Learning semidefinite regularizers
• The global optimization geometry of shallow linear neural networks
• The landscape of empirical risk for nonconvex losses
• Fast rank-one alternating minimization algorithm for phase retrieval
• Scalable incremental nonconvex optimization approach for phase retrieval
• Phase retrieval for sub-Gaussian measurements
• On DC based methods for phase retrieval
• Riemannian optimization for phase retrieval from masked Fourier measurements
• On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
• Near-optimal bounds for signal recovery from blind phaseless periodic short-time Fourier transform
• Finding the global optimum of a class of quartic minimization problem
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
• Proximal methods avoid active strict saddles of weakly convex functions
• Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries
• Phase retrieval using alternating minimization in a batch setting
• Guarantees of Riemannian optimization for low rank matrix completion
• Lower bounds for finding stationary points I
• Complex phase retrieval from subgaussian measurements
• Generalized phase retrieval: measurement number, matrix recovery and beyond
• Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
• Phase retrieval via sensor network localization
• Misspecified nonconvex statistical optimization for sparse phase retrieval
• Stability estimates for phase retrieval from discrete Gabor measurements
• Sparse signal recovery from phaseless measurements via hard thresholding pursuit
• A limited-memory Riemannian symmetric rank-one trust-region method with a restart strategy
• Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
• Nonconvex phase synchronization
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phase retrieval for sparse binary signal: uniqueness and algorithm
• Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
• A Geometrical Study of Matching Pursuit Parametrization
• Stochastic model-based minimization of weakly convex functions
• On the quadratic convergence of the cubic regularization method under a local error bound condition
• Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis
• Rank optimality for the Burer-Monteiro factorization
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• Solving phase retrieval via graph projection splitting
• Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
• Toward a mathematical theory of the crystallographic phase retrieval problem
• Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
• Analysis of asymptotic escape of strict saddle sets in manifold optimization
• Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
• Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
• Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
• A generalization of Wirtinger flow for exact interferometric inversion
• First-Order Methods for Nonconvex Quadratic Minimization
• PhaseMax: stable guarantees from noisy sub-Gaussian measurements
• Synchronization of Kuramoto oscillators in dense networks
• Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent
• The Geometry of Ambiguity in One-Dimensional Phase Retrieval
• Proximal gradient method for nonsmooth optimization over the Stiefel manifold
• Model-free nonconvex matrix completion: local minima analysis and applications in memory-efficient kernel PCA
• On the landscape of synchronization networks: a perspective from nonconvex optimization
• A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
• The nonsmooth landscape of phase retrieval
• Generalized approximate survey propagation for high-dimensional estimation ^*
• The global landscape of phase retrieval. I: Perturbed amplitude models
• The global landscape of phase retrieval. II: Quotient intensity models
• Asymptotic Properties of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization
• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• The numerics of phase retrieval
• Lower bounds for non-convex stochastic optimization
• Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
• Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
• Analysis of the optimization landscape of Linear Quadratic Gaussian (LQG) control
• Gradient-Type Methods for Optimization Problems with Polyak-Łojasiewicz Condition: Early Stopping and Adaptivity to Inexactness Parameter
• Adaptive trust-region method on Riemannian manifold
• Compressive phase retrieval: Optimal sample complexity with deep generative priors
• Self-Supervised Deep Learning for Image Reconstruction: A Langevin Monte Carlo Approach
• On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
• Affine phase retrieval for sparse signals via \(\ell_1\) minimization
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Signal Reconstruction from Phase-Only Measurements: Uniqueness Condition, Minimal Measurement Number and Beyond
• Provable Phase Retrieval with Mirror Descent
• Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
• Performance bounds of the intensity-based estimators for noisy phase retrieval
• Tractability from overparametrization: the example of the negative perceptron
• The performance of the amplitude-based model for complex phase retrieval
• SPIRAL: a superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
• Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
• Towards a bilipschitz invariant theory
• A new complexity metric for nonconvex rank-one generalized matrix completion
• Three proofs of the Benedetto-Fickus theorem
• A deterministic gradient-based approach to avoid saddle points
• Wirtinger gradient descent methods for low-dose Poisson phase retrieval
• Gradient descent provably escapes saddle points in the training of shallow ReLU networks
• An elementary proof of convex phase retrieval in the natural parameter space via the linear program PhaseMax
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Two nonmonotone proximal gradient methods for nonsmooth optimization over the Stiefel manifold
• Optimal sparse phase retrieval via a quasi-Bayesian approach
• Gradient-type methods for decentralized optimization problems with Polyak–Łojasiewicz condition over time-varying networks
• Riemannian trust-region methods for strict saddle functions with complexity guarantees
• Numerical methods for variational inequalities and saddle point problems with relative inexact information

Describes a project that uses

Uses Software

• Manopt
• GQTPAR
• GESPAR
• PhaseMax
• PhaseLift
• Wirtinger Flow

This page was built for publication: A geometric analysis of phase retrieval

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785008)