A geometric analysis of phase retrieval

DOI10.1007/s10208-017-9365-9zbMath1401.94049arXiv1602.06664OpenAlexW3113425034MaRDI QIDQ1785008

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

inverse problemsnonconvex optimizationtrust-region methodphase retrievalmathematical imagingsecond-order geometryfunction landscaperidable saddles

Mathematics Subject Classification ID

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

Related Items

Analysis of Asymptotic Escape of Strict Saddle Sets in Manifold Optimization ⋮ The numerics of phase retrieval ⋮ Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA ⋮ Subgradient methods for sharp weakly convex functions ⋮ Role of sparsity and structure in the optimization landscape of non-convex matrix sensing ⋮ Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity ⋮ Proximal methods avoid active strict saddles of weakly convex functions ⋮ Unnamed Item ⋮ Stability estimates for phase retrieval from discrete Gabor measurements ⋮ Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries ⋮ Guarantees of Riemannian optimization for low rank matrix completion ⋮ Sparse signal recovery from phaseless measurements via hard thresholding pursuit ⋮ Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations ⋮ Escaping Strict Saddle Points of the Moreau Envelope in Nonsmooth Optimization ⋮ A limited-memory Riemannian symmetric rank-one trust-region method with a restart strategy ⋮ 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 ⋮ Unnamed Item ⋮ A Generalization of Wirtinger Flow for Exact Interferometric Inversion ⋮ Misspecified nonconvex statistical optimization for sparse phase retrieval ⋮ Using negative curvature in solving nonlinear programs ⋮ 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 ⋮ First-Order Methods for Nonconvex Quadratic Minimization ⋮ Performance bounds of the intensity-based estimators for noisy phase retrieval ⋮ Tractability from overparametrization: the example of the negative perceptron ⋮ Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points ⋮ Lower bounds for finding stationary points I ⋮ Stochastic Model-Based Minimization of Weakly Convex Functions ⋮ PhaseMax: Stable guarantees from noisy sub-Gaussian measurements ⋮ Synchronization of Kuramoto oscillators in dense networks ⋮ Complex phase retrieval from subgaussian measurements ⋮ Median-Truncated Gradient Descent: A Robust and Scalable Nonconvex Approach for Signal Estimation ⋮ On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Condition ⋮ 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 ⋮ Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold ⋮ On DC based methods for phase retrieval ⋮ Rank Optimality for the Burer--Monteiro Factorization ⋮ On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization ⋮ Nonconvex Phase Synchronization ⋮ Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods ⋮ Solving phase retrieval via graph projection splitting ⋮ Phase retrieval for sparse binary signal: uniqueness and algorithm ⋮ On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint ⋮ A Bregman Forward-Backward Linesearch Algorithm for Nonconvex Composite Optimization: Superlinear Convergence to Nonisolated Local Minima ⋮ Generalized approximate survey propagation for high-dimensional estimation ^* ⋮ Unnamed Item ⋮ The Global Landscape of Phase Retrieval II: Perturbed Amplitude Models ⋮ The Global Landscape of Phase Retrieval II: Quotient Intensity Models ⋮ Near-optimal bounds for signal recovery from blind phaseless periodic short-time Fourier transform ⋮ 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 ⋮ Toward a Mathematical Theory of the Crystallographic Phase Retrieval Problem ⋮ Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points ⋮ 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

Uses Software

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal rates of convergence for noisy sparse phase retrieval via thresholded Wirtinger flow
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• Complexity bounds for second-order optimality in unconstrained optimization
• The Pauli problem, state reconstruction and quantum-real numbers
• A strong restricted isometry property, with an application to phaseless compressed sensing
• Painless reconstruction from magnitudes of frame coefficients
• On affine scaling algorithms for nonconvex quadratic programming
• A semidefinite framework for trust region subproblems with applications to large scale minimization
• A flexible convex relaxation for phase retrieval
• Quantum tomography under prior information
• A partial derandomization of phaselift using spherical designs
• Trust-region methods on Riemannian manifolds
• The local convexity of solving systems of quadratic equations
• On signal reconstruction without phase
• Cubic regularization of Newton method and its global performance
• Phase recovery, MaxCut and complex semidefinite programming
• Phase retrieval from coded diffraction patterns
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Nonconvex Phase Synchronization
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Sparse Signal Recovery from Quadratic Measurements via Convex Programming
• Phase Retrieval with Polarization
• High-Dimensional Covariance Decomposition into Sparse Markov and Independence Models
• Manopt, a Matlab toolbox for optimization on manifolds
• Guaranteed Matrix Completion via Non-Convex Factorization
• Finding a Sparse Vector in a Subspace: Linear Sparsity Using Alternating Directions
• Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• A Clustering Approach to Learning Sparsely Used Overcomplete Dictionaries
• Blind Recovery of Sparse Signals From Subsampled Convolution
• Complete Dictionary Recovery Over the Sphere II: Recovery by Riemannian Trust-Region Method
• Array imaging using intensity-only measurements
• Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization
• Computing a Trust Region Step
• Curvilinear path steplength algorithms for minimization which use directions of negative curvature
• Trust Region Methods
• Non-Convex Phase Retrieval From STFT Measurements
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Near-Optimal Compressed Sensing of a Class of Sparse Low-Rank Matrices Via Sparse Power Factorization
• PhaseMax: Convex Phase Retrieval via Basis Pursuit
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• Gradient Descent Only Converges to Minimizers: Non-Isolated Critical Points and Invariant Regions
• The trust region subproblem and semidefinite programming*
• Matrix Completion From a Few Entries
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Low-rank matrix completion using alternating minimization
• Phase Retrieval via Matrix Completion

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