Solving phase retrieval with random initial guess is nearly as good as by spectral initialization

DOI10.1016/J.ACHA.2022.01.002MaRDI QIDQ2118400zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 22 March 2022

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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

zbMATH Keywords

geometric landscapenonconvexphase retrievalphaseless measurements

Mathematics Subject Classification ID

Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The problem of recovering a signal $mathbfxinmathbb{R}^n$ from a set of magnitude measurements $y_i=|langlemathbf{a}_i,mathbfxangle|,;i=1,ldots,m$ is referred as phase retrieval, which has many applications in fields of physical sciences and engineering. In this paper we show that the smoothed amplitude flow model for phase retrieval has benign geometric structure under the optimal sampling complexity. In particular, we show that when the measurements $mathbf{a}_{i}inmathbb{R}^n$ are Gaussian random vectors and the number of measurements $mgeCn$, our smoothed amplitude flow model has no spurious local minimizers with high probability, ie., the target solution $mathbfx$ is the unique global minimizer (up to a global phase) and the loss function has a negative directional curvature around each saddle point. Due to this benign geometric landscape, the phase retrieval problem can be solved by the gradient descent algorithms without spectral initialization. Numerical experiments show that the gradient descent algorithm with random initialization performs well even comparing with state-of-the-art algorithms with spectral initialization in empirical success rate and convergence speed.

Recommendations

• The global landscape of phase retrieval. I: Perturbed amplitude models
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• A geometric analysis of phase retrieval
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Phase retrieval via Wirtinger flow: theory and algorithms

Cites work

• A geometric analysis of phase retrieval
• A nonconvex approach for phase retrieval: reshaped Wirtinger flow and incremental algorithms
• An algebraic characterization of injectivity in phase retrieval
• Array imaging using intensity-only measurements
• Blind Recovery of Sparse Signals From Subsampled Convolution
• Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
• High-dimensional probability. An introduction with applications in data science
• Non-Convex Phase Retrieval From STFT Measurements
• On signal reconstruction without phase
• Perturbed Amplitude Flow for Phase Retrieval
• Phase recovery, MaxCut and complex semidefinite programming
• Phase Retrieval Using Alternating Minimization
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phase Retrieval With Random Gaussian Sensing Vectors by Alternating Projections
• Phaseless Recovery Using the Gauss–Newton Method
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Solving systems of quadratic equations via exponential-type gradient descent algorithm
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks
• Toward the Optimal Construction of a Loss Function Without Spurious Local Minima for Solving Quadratic Equations

Cited in

(23)

• On global convergence of gradient descent algorithms for generalized phase retrieval problem
• A geometric analysis of phase retrieval
• Phase retrieval for sub-Gaussian measurements
• Phase retrieval using alternating minimization in a batch setting
• Smoothed amplitude flow-based phase retrieval algorithm
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Phase transitions of spectral initialization for high-dimensional non-convex estimation
• Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
• The nonsmooth landscape of phase retrieval
• A spectral estimation framework for phase retrieval via Bregman divergence minimization
• The global landscape of phase retrieval. I: Perturbed amplitude models
• The global landscape of phase retrieval. II: Quotient intensity models
• An Efficient and Robust Scalar Auxialiary Variable Based Algorithm for Discrete Gradient Systems Arising from Optimizations
• 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
• Provable Phase Retrieval with Mirror Descent
• Uniqueness and stability for the solution of a nonlinear least squares problem
• Stability in phase retrieval: characterizing condition numbers and the optimal vector set
• An oracle gradient regularized Newton method for quadratic measurements regression
• The role of the time-dependent Hessian in high-dimensional optimization
• Recovery performance of PhaseLift for phase retrieval from coded diffraction patterns
• The condition number in phase retrieval from intensity measurements

Describes a project that uses

Uses Software

• PhaseLift
• Wirtinger Flow

This page was built for publication: Solving phase retrieval with random initial guess is nearly as good as by spectral initialization

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