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
• Solving PhaseLift by Low-Rank Riemannian Optimization Methods for Complex Semidefinite Constraints
• Spectral Compressed Sensing via Projected Gradient Descent
• Phase retrieval from short-time fractional Fourier measurements using alternating direction method of multipliers
• Local saddles of relaxed averaged alternating reflections algorithms on phase retrieval
• Phase retrieval of real-valued signals in a shift-invariant space
• Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
• Stable phase retrieval in infinite dimensions
• Numerical optimization algorithms for wavefront phase retrieval from multiple measurements
• Guarantees of Riemannian optimization for low rank matrix recovery
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• Phase retrieval from coded diffraction patterns
• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• Low-rank spectral optimization via gauge duality
• Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons
• Coded aperture design for solving the phase retrieval problem in X-ray crystallography
• Universal latent space model fitting for large networks with edge covariates
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• Fast Phase Retrieval from Local Correlation Measurements
• Convex-concave backtracking for inertial Bregman proximal gradient algorithms in nonconvex optimization
• Self-calibration and biconvex compressive sensing
• Subgradient methods for sharp weakly convex functions
• An optimal statistical and computational framework for generalized tensor estimation
• Phase retrieval from Fourier measurements with masks
• Approximate global minimizers to pairwise interaction problems via convex relaxation
• Phase retrieval with PhaseLift algorithm
• Entrywise eigenvector analysis of random matrices with low expected rank
• Riemannian optimization for phase retrieval from masked Fourier measurements
• A message-passing approach to phase retrieval of sparse signals
• A geometric analysis of phase retrieval
• Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
• Stable low-rank matrix recovery via null space properties
• Explicit frames for deterministic phase retrieval via PhaseLift
• Real phase retrieval from unordered partial frame coefficients
• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• A flexible convex relaxation for phase retrieval
• Fourier phase retrieval with a single mask by Douglas-Rachford algorithms

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)