Nearly optimal bounds for the global geometric landscape of phase retrieval

DOI10.1088/1361-6420/ACDAB7MaRDI QIDQ6162747zbMATH OpenFDO

Authors Jian-Feng Cai, Meng Huang, Dong Li, Yang Wang

Publication date 16 June 2023

Published in Inverse Problems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

geometric landscapenonconvex optimizationphase retrieval

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The phase retrieval problem is concerned with recovering an unknown signal $$ from a set of magnitude-only measurements $$. A natural least squares formulation can be used to solve this problem efficiently even with random initialization, despite its non-convexity of the loss function. One way to explain this surprising phenomenon is the benign geometric landscape: (1) all local minimizers are global; and (2) the objective function has a negative curvature around each saddle point and local maximizer. In this paper, we show that $m=O(nlogn)$ Gaussian random measurements are sufficient to guarantee the loss function of a commonly used estimator has such benign geometric landscape with high probability. This is a step toward answering the open problem given by Sun-Qu-Wright, in which the authors suggest that $O(nlogn)$ or even $O(n)$ is enough to guarantee the favorable geometric property.

Recommendations

• A geometric analysis of phase retrieval
• The global landscape of phase retrieval. II: Quotient intensity models
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• The global landscape of phase retrieval. I: Perturbed amplitude models
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval

Cites work

• A geometric analysis of phase retrieval
• A nonconvex approach for phase retrieval: reshaped Wirtinger flow and incremental algorithms
• Benchmark problems for phase retrieval
• Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
• Editorial: Inverse wave propagation problems without phase information
• Geometry of the phase retrieval problem
• High-dimensional probability. An introduction with applications in data science
• Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Phase recovery, MaxCut and complex semidefinite programming
• Phase Retrieval Using Alternating Minimization
• Phase retrieval via randomized Kaczmarz: theoretical guarantees
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• 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 phaseless equations via Kaczmarz methods: a proof of concept study
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• The global landscape of phase retrieval. I: Perturbed amplitude models
• The global landscape of phase retrieval. II: Quotient intensity models
• The phase retrieval problem
• Toward the Optimal Construction of a Loss Function Without Spurious Local Minima for Solving Quadratic Equations

Cited in

(8)

• A geometric analysis of phase retrieval
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• The Geometry of Ambiguity in One-Dimensional Phase Retrieval
• The global landscape of phase retrieval. I: Perturbed amplitude models
• The global landscape of phase retrieval. II: Quotient intensity models
• Truncated amplitude flow with coded diffraction patterns
• The role of the time-dependent Hessian in high-dimensional optimization
• Recovery performance of PhaseLift for phase retrieval from coded diffraction patterns

This page was built for publication: Nearly optimal bounds for the global geometric landscape of phase retrieval

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