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

nonconvexphase retrievalphaseless measurementsgeometric landscape

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 Retrieval Using Alternating Minimization
• Phase Retrieval With Random Gaussian Sensing Vectors by Alternating Projections
• Phase recovery, MaxCut and complex semidefinite programming
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phaseless Recovery Using the Gauss–Newton Method
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• Solving systems of quadratic equations via exponential-type gradient descent algorithm
• 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

(18)

• Affine phase retrieval for sparse signals via \(\ell_1\) minimization
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
• Smoothed amplitude flow-based phase retrieval algorithm
• A geometric analysis of phase retrieval
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Provable Phase Retrieval with Mirror Descent
• An Efficient and Robust Scalar Auxialiary Variable Based Algorithm for Discrete Gradient Systems Arising from Optimizations
• The nonsmooth landscape of phase retrieval
• A spectral estimation framework for phase retrieval via Bregman divergence minimization
• The global landscape of phase retrieval. II: Quotient intensity models
• The global landscape of phase retrieval. I: Perturbed amplitude models
• On global convergence of gradient descent algorithms for generalized phase retrieval problem
• Uniqueness and stability for the solution of a nonlinear least squares problem
• Phase retrieval using alternating minimization in a batch setting
• Phase transitions of spectral initialization for high-dimensional non-convex estimation
• Phase retrieval for sub-Gaussian measurements

Describes a project that uses

Uses Software

• Wirtinger Flow
• PhaseLift

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)