A geometric analysis of phase retrieval
From MaRDI portal
Abstract: Can we recover a complex signal from its Fourier magnitudes? More generally, given a set of measurements, for , is it possible to recover (i.e., length- 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 's are generic (i.i.d. complex Gaussian) and the number of measurements is large enough (), 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 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
- 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?)
- 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
- 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 Wirtinger flow: theory and algorithms
- Phase retrieval via matrix completion
- Phase retrieval with polarization
- PhaseMax: Convex Phase Retrieval via Basis Pursuit
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- Quantum tomography under prior information
- Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
- Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
- Solving quadratic equations via phaselift when there are about as many equations as unknowns
- Sparse signal recovery from quadratic measurements via convex programming
- The Pauli problem, state reconstruction and quantum-real numbers
- The local convexity of solving systems of quadratic equations
- The trust region subproblem and semidefinite programming*
- Trust Region Methods
- Trust-region methods on Riemannian manifolds
Cited in
(94)- Guarantees of Riemannian optimization for low rank matrix completion
- Generalized approximate survey propagation for high-dimensional estimation *
- The global optimization geometry of shallow linear neural networks
- Affine phase retrieval for sparse signals via \(\ell_1\) minimization
- Analysis of asymptotic escape of strict saddle sets in manifold optimization
- scientific article; zbMATH DE number 7415093 (Why is no real title available?)
- The numerics of phase retrieval
- Nearly optimal bounds for the global geometric landscape of phase retrieval
- Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
- Complex phase retrieval from subgaussian measurements
- Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
- Towards a bilipschitz invariant theory
- Near-optimal bounds for signal recovery from blind phaseless periodic short-time Fourier transform
- Learning semidefinite regularizers
- Compressive phase retrieval: Optimal sample complexity with deep generative priors
- Generalized phase retrieval: measurement number, matrix recovery and beyond
- 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
- First-Order Methods for Nonconvex Quadratic Minimization
- Subgradient methods for sharp weakly convex functions
- Asymptotic Properties of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization
- Toward a mathematical theory of the crystallographic phase retrieval problem
- Riemannian optimization for phase retrieval from masked Fourier measurements
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- Stochastic model-based minimization of weakly convex functions
- Provable sample-efficient sparse phase retrieval initialized by truncated power method
- Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
- Scalable incremental nonconvex optimization approach for phase retrieval
- Likelihood landscape and maximum likelihood estimation for the discrete orbit recovery model
- Provable Phase Retrieval with Mirror Descent
- Three proofs of the Benedetto-Fickus theorem
- Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
- The performance of the amplitude-based model for complex phase retrieval
- Proximal methods avoid active strict saddles of weakly convex functions
- A new complexity metric for nonconvex rank-one generalized matrix completion
- scientific article; zbMATH DE number 7370623 (Why is no real title available?)
- Phase retrieval for sparse binary signal: uniqueness and algorithm
- A limited-memory Riemannian symmetric rank-one trust-region method with a restart strategy
- Low-Rank Univariate Sum of Squares Has No Spurious Local Minima
- Signal Reconstruction from Phase-Only Measurements: Uniqueness Condition, Minimal Measurement Number and Beyond
- Lower bounds for finding stationary points I
- PhaseMax: stable guarantees from noisy sub-Gaussian measurements
- The nonsmooth landscape of phase retrieval
- Self-Supervised Deep Learning for Image Reconstruction: A Langevin Monte Carlo Approach
- Fast rank-one alternating minimization algorithm for phase retrieval
- Performance bounds of the intensity-based estimators for noisy phase retrieval
- Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis
- A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
- The global landscape of phase retrieval. II: Quotient intensity models
- On the quadratic convergence of the cubic regularization method under a local error bound condition
- The global landscape of phase retrieval. I: Perturbed amplitude models
- Nonconvex phase synchronization
- A deterministic gradient-based approach to avoid saddle points
- Rank optimality for the Burer-Monteiro factorization
- Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
- Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
- A generalization of Wirtinger flow for exact interferometric inversion
- Lower bounds for non-convex stochastic optimization
- Tractability from overparametrization: the example of the negative perceptron
- Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries
- On DC based methods for phase retrieval
- Sparse signal recovery from phaseless measurements via hard thresholding pursuit
- On global convergence of gradient descent algorithms for generalized phase retrieval problem
- Misspecified nonconvex statistical optimization for sparse phase retrieval
- Phase retrieval via sensor network localization
- Phase retrieval using alternating minimization in a batch setting
- Using negative curvature in solving nonlinear programs
- Gradient-Type Methods for Optimization Problems with Polyak-Łojasiewicz Condition: Early Stopping and Adaptivity to Inexactness Parameter
- Proximal gradient method for nonsmooth optimization over the Stiefel manifold
- The Geometry of Ambiguity in One-Dimensional Phase Retrieval
- Model-free nonconvex matrix completion: local minima analysis and applications in memory-efficient kernel PCA
- Gradient descent provably escapes saddle points in the training of shallow ReLU networks
- Analysis of the optimization landscape of Linear Quadratic Gaussian (LQG) control
- Wirtinger gradient descent methods for low-dose Poisson phase retrieval
- Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
- Phase retrieval for sub-Gaussian measurements
- Revisiting Landscape Analysis in Deep Neural Networks: Eliminating Decreasing Paths to Infinity
- SPIRAL: a superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
- Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
- On the Global Convergence of Randomized Coordinate Gradient Descent for Nonconvex Optimization
- The landscape of empirical risk for nonconvex losses
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
- A Geometrical Study of Matching Pursuit Parametrization
- Adaptive trust-region method on Riemannian manifold
- On the landscape of synchronization networks: a perspective from nonconvex optimization
- Synchronization of Kuramoto oscillators in dense networks
- Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
- An elementary proof of convex phase retrieval in the natural parameter space via the linear program PhaseMax
- On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
- Stability estimates for phase retrieval from discrete Gabor measurements
- Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
- Solving phase retrieval via graph projection splitting
- Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
- Phase retrieval via Wirtinger flow: theory and algorithms
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)
