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

DOI10.1016/J.ACHA.2022.01.002zbMATH Open1485.94015arXiv2101.03540OpenAlexW3120243577MaRDI QIDQ2118400FDOQ2118400

Yanyan Li

Publication date: 22 March 2022

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

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.

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

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

zbMATH Keywords

nonconvexphase retrievalphaseless measurementsgeometric landscape

Mathematics Subject Classification ID

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

Cites Work

• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• High-Dimensional Probability
• On signal reconstruction without phase
• An algebraic characterization of injectivity in phase retrieval
• Phase recovery, MaxCut and complex semidefinite programming
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• Array imaging using intensity-only measurements
• Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• A geometric analysis of phase retrieval
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Phase Retrieval Using Alternating Minimization
• Phase Retrieval With Random Gaussian Sensing Vectors by Alternating Projections
• Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks
• Blind Recovery of Sparse Signals From Subsampled Convolution
• Non-Convex Phase Retrieval From STFT Measurements
• Title not available (Why is that?)
• Toward the Optimal Construction of a Loss Function Without Spurious Local Minima for Solving Quadratic Equations
• Phaseless Recovery Using the Gauss–Newton Method
• Solving Systems of Quadratic Equations Via Exponential-Type Gradient Descent Algorithm
• Perturbed Amplitude Flow for Phase Retrieval

Cited In (8)

• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
• Gradient descent with random initialization: fast global convergence for nonconvex 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
• Uniqueness and stability for the solution of a nonlinear least squares problem
• Affine phase retrieval for sparse signals via \(\ell_1\) minimization

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)