An elementary proof of convex phase retrieval in the natural parameter space via the linear program PhaseMax

DOI10.4310/CMS.2018.V16.N7.A13zbMATH Open1441.94040arXiv1611.03935OpenAlexW2573309900WikidataQ128246975 ScholiaQ128246975MaRDI QIDQ667019FDOQ667019

Vladislav Voroninski, Paul E. Hand

Publication date: 12 March 2019

Published in: Communications in Mathematical Sciences (Search for Journal in Brave)

Abstract: The phase retrieval problem has garnered significant attention since the development of the PhaseLift algorithm, which is a convex program that operates in a lifted space of matrices. Because of the substantial computational cost due to lifting, many approaches to phase retrieval have been developed, including non-convex optimization algorithms which operate in the natural parameter space, such as Wirtinger Flow. Very recently, a convex formulation called PhaseMax has been discovered, and it has been proven to achieve phase retrieval via linear programming in the natural parameter space under optimal sample complexity. The current proofs of PhaseMax rely on statistical learning theory or geometric probability theory. Here, we present a short and elementary proof that PhaseMax exactly recovers real-valued vectors from random measurements under optimal sample complexity. Our proof only relies on standard probabilistic concentration and covering arguments, yielding a simpler and more direct proof than those that require statistical learning theory, geometric probability or the highly technical arguments for Wirtinger Flow-like approaches.

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

Recommendations

• Phase retrieval via Wirtinger flow: theory and algorithms
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Phase retrieval from low-rate samples
• Saving phase: injectivity and stability for phase retrieval
• A geometric analysis of phase retrieval

zbMATH Keywords

linear programmingphase retrievalPhaseMax

Mathematics Subject Classification ID

Linear programming (90C05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Geometric probability and stochastic geometry (60D05)

Cited In (12)

• Phaseless sampling and reconstruction of real-valued signals in shift-invariant spaces
• The numerics of phase retrieval
• PhaseMax: Stable guarantees from noisy sub-Gaussian measurements
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• A Spectral Estimation Framework for Phase Retrieval via Bregman Divergence Minimization
• Sampling complexity on phase retrieval from masked Fourier measurements via Wirtinger flow*
• Robust phase retrieval via median-truncated smoothed amplitude flow
• Solving equations of random convex functions via anchored regression
• Riemannian optimization for phase retrieval from masked Fourier measurements
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Title not available (Why is that?)
• Sparse signal recovery from phaseless measurements via hard thresholding pursuit

Uses Software

• PhaseMax
• PhaseLift
• Wirtinger Flow

This page was built for publication: An elementary proof of convex phase retrieval in the natural parameter space via the linear program PhaseMax

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