Phase retrieval via Wirtinger flow: theory and algorithms

DOI10.1109/TIT.2015.2399924zbMATH Open1359.94069arXiv1407.1065OpenAlexW3102206315MaRDI QIDQ2978701FDOQ2978701

Authors: Emmanuel J. Candès, Xiaodong Li, Mahdi Soltanolkotabi 

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We study the problem of recovering the phase from magnitude measurements; specifically, we wish to reconstruct a complex-valued signal x of C^n about which we have phaseless samples of the form y_r = |< a_r,x >|^2, r = 1,2,...,m (knowledge of the phase of these samples would yield a linear system). This paper develops a non-convex formulation of the phase retrieval problem as well as a concrete solution algorithm. In a nutshell, this algorithm starts with a careful initialization obtained by means of a spectral method, and then refines this initial estimate by iteratively applying novel update rules, which have low computational complexity, much like in a gradient descent scheme. The main contribution is that this algorithm is shown to rigorously allow the exact retrieval of phase information from a nearly minimal number of random measurements. Indeed, the sequence of successive iterates provably converges to the solution at a geometric rate so that the proposed scheme is efficient both in terms of computational and data resources. In theory, a variation on this scheme leads to a near-linear time algorithm for a physically realizable model based on coded diffraction patterns. We illustrate the effectiveness of our methods with various experiments on image data. Underlying our analysis are insights for the analysis of non-convex optimization schemes that may have implications for computational problems beyond phase retrieval.

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

Recommendations

• Phase retrieval via matrix completion
• Phase retrieval via matrix completion
• Phase retrieval from coded diffraction patterns
• A geometric analysis of phase retrieval
• A nonconvex approach for phase retrieval: reshaped Wirtinger flow and incremental algorithms

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (only showing first 100 items - show all)

• On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Condition
• Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization
• On signal reconstruction from FROG measurements
• Title not available (Why is that?)
• On phase retrieval via matrix completion and the estimation of low rank PSD matrices
• Phase retrieval via randomized Kaczmarz: theoretical guarantees
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Complex phase retrieval from subgaussian measurements
• Multigrid Optimization for Large-Scale Ptychographic Phase Retrieval
• New Bregman proximal type algoritms for solving DC optimization problems
• An Approximate Factorization Method for Inverse Acoustic Scattering with Phaseless Total-Field Data
• Near-optimal bounds for signal recovery from blind phaseless periodic short-time Fourier transform
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• Admissible measurements and robust algorithms for ptychography
• A direct solver for the phase retrieval problem in ptychographic imaging
• First-order methods almost always avoid strict saddle points
• Sparse power factorization: balancing peakiness and sample complexity
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Inertial proximal ADMM for separable multi-block convex optimizations and compressive affine phase retrieval
• Solving equations of random convex functions via anchored regression
• On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations
• Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery
• Fundamental limits of weak recovery with applications to phase retrieval
• Stochastic model-based minimization of weakly convex functions
• Normal approximation and confidence region of singular subspaces
• Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
• Constructing confidence intervals for the signals in sparse phase retrieval
• Scalable incremental nonconvex optimization approach for phase retrieval
• Learning without loss
• Quartic first-order methods for low-rank minimization
• PhaseMax: stable guarantees from noisy sub-Gaussian measurements
• The nonsmooth landscape of phase retrieval
• Improved performance guarantees for orthogonal group synchronization via generalized power method
• Phase retrieval: theory, model and algorithms
• Lower bounds for finding stationary points I
• A frequency-domain analysis of inexact gradient methods
• Analytical convergence regions of accelerated gradient descent in nonconvex optimization under regularity condition
• A modified scaled spectral-conjugate gradient-based algorithm for solving monotone operator equations
• FR-type algorithm for finding approximate solutions to nonlinear monotone operator equations
• Global convergence of model function based Bregman proximal minimization algorithms
• On the effect of zero-flipping on the stability of the phase retrieval problem in the Paley-Wiener class
• High-dimensional index volatility models via Stein's identity
• New analysis of linear convergence of gradient-type methods via unifying error bound conditions
• Harmonic mean iteratively reweighted least squares for low-rank matrix recovery
• Phase retrieval from the norms of affine transformations
• Eigenvector phase retrieval: recovering eigenvectors from the absolute value of their entries
• On DC based methods for phase retrieval
• Tensor-free proximal methods for lifted bilinear/quadratic inverse problems with applications to phase retrieval
• Misspecified nonconvex statistical optimization for sparse phase retrieval
• Phase retrieval using alternating minimization in a batch setting
• Geometry of the phase retrieval problem
• Holographic phase retrieval and reference design
• Perturbed Amplitude Flow for Phase Retrieval
• Solving (most) of a set of quadratic equalities: composite optimization for robust phase retrieval
• Robust Phase Retrieval Algorithm for Time-Frequency Structured Measurements
• Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
• Phase retrieval: a data-driven wavelet frame based approach
• Some recent developments in the unique determinations in phaseless inverse acoustic scattering theory
• Solving phase retrieval via graph projection splitting
• Optimal combination of linear and spectral estimators for generalized linear models
• On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
• New hybrid three-term spectral-conjugate gradient method for finding solutions of nonlinear monotone operator equations with applications
• Guarantees of Riemannian optimization for low rank matrix completion
• ADMM based Fourier phase retrieval with untrained generative prior
• Polarimetric Fourier phase retrieval
• A stochastic ADMM algorithm for large-scale ptychography with weighted difference of anisotropic and isotropic total variation
• Quantization-aware phase retrieval
• Approximate message passing with spectral initialization for generalized linear models*
• Title not available (Why is that?)
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
• Lipschitz analysis of generalized phase retrievable matrix frames
• Inverting spectrogram measurements via aliased Wigner distribution deconvolution and angular synchronization
• Towards a bilipschitz invariant theory
• Robust amplitude method with \(L_{1/2}\)-regularization for compressive phase retrieval
• Robust High-Dimensional Regression with Coefficient Thresholding and Its Application to Imaging Data Analysis
• Phaseless compressive sensing using partial support information
• Smoothed amplitude flow-based phase retrieval algorithm
• On averaging block Kaczmarz methods for solving nonlinear systems of equations
• Cardinality minimization, constraints, and regularization: a survey
• Communication-Efficient Distributed Eigenspace Estimation
• Asymptotic Properties of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization
• Robust phase retrieval via median-truncated smoothed amplitude flow
• One-dimensional phase retrieval: regularization, box relaxation and uniqueness
• Phaselift is robust to a constant fraction of arbitrary errors
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Inverse source problem of the biharmonic equation from multifrequency phaseless data
• Provable Phase Retrieval with Mirror Descent
• Three proofs of the Benedetto-Fickus theorem
• Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
• Uniqueness of STFT Phase Retrieval for Bandlimited Vector Functions
• Fast iterative algorithms for blind phase retrieval: a survey
• Randomized Kaczmarz method for single particle X-ray image phase retrieval
• A new complexity metric for nonconvex rank-one generalized matrix completion
• Well-conditioned ptychograpic imaging via lost subspace completion
• An Efficient and Robust Scalar Auxialiary Variable Based Algorithm for Discrete Gradient Systems Arising from Optimizations
• Title not available (Why is that?)
• Phase retrieval for sparse binary signal: uniqueness and algorithm
• On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations

Uses Software

• PhaseLift

This page was built for publication: Phase retrieval via Wirtinger flow: theory and algorithms

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