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

DOI10.4310/CMS.2018.V16.N7.A13MaRDI QIDQ667019zbMATHOpenAlexWikidataFDO

Authors Vladislav Voroninski, Paul E. Hand

Publication date 12 March 2019

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

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

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)

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.

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

Cited in

(13)

• Sparse signal recovery from phaseless measurements via hard thresholding pursuit
• scientific article; zbMATH DE number 7306888 (Why is no real title available?)
• Riemannian optimization for phase retrieval from masked Fourier measurements
• Phase retrieval of complex-valued objects via a randomized Kaczmarz method
• Phaseless sampling and reconstruction of real-valued signals in shift-invariant spaces
• PhaseMax: stable guarantees from noisy sub-Gaussian measurements
• The numerics of phase retrieval
• Robust phase retrieval via median-truncated smoothed amplitude flow
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• A spectral estimation framework for phase retrieval via Bregman divergence minimization
• Sampling complexity on phase retrieval from masked Fourier measurements via Wirtinger flow
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Solving equations of random convex functions via anchored regression

Describes a project that uses

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)