Phase Retrieval Using Alternating Minimization

DOI10.1109/TSP.2015.2448516MaRDI QIDQ4580795zbMATH OpenOpenAlexFDO

Authors Praneeth Netrapalli, Prateek Jain, Sujay Sanghavi

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Phase retrieval problems involve solving linear equations, but with missing sign (or phase, for complex numbers) information. More than four decades after it was first proposed, the seminal error reduction algorithm of (Gerchberg and Saxton 1972) and (Fienup 1982) is still the popular choice for solving many variants of this problem. The algorithm is based on alternating minimization; i.e. it alternates between estimating the missing phase information, and the candidate solution. Despite its wide usage in practice, no global convergence guarantees for this algorithm are known. In this paper, we show that a (resampling) variant of this approach converges geometrically to the solution of one such problem -- finding a vector $mathbfx$ from $mathbfy,mathbfA$, where $mathbfy=left|mathbf{A}^{op}mathbfxight|$ and $|mathbfz|$ denotes a vector of element-wise magnitudes of $mathbfz$ -- under the assumption that $mathbfA$ is Gaussian. Empirically, we demonstrate that alternating minimization performs similar to recently proposed convex techniques for this problem (which are based on "lifting" to a convex matrix problem) in sample complexity and robustness to noise. However, it is much more efficient and can scale to large problems. Analytically, for a resampling version of alternating minimization, we show geometric convergence to the solution, and sample complexity that is off by log factors from obvious lower bounds. We also establish close to optimal scaling for the case when the unknown vector is sparse. Our work represents the first theoretical guarantee for alternating minimization (albeit with resampling) for any variant of phase retrieval problems in the non-convex setting.

Cited in

(77)

• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• On global convergence of gradient descent algorithms for generalized phase retrieval problem
• Fourier phase retrieval with a single mask by Douglas-Rachford algorithms
• Phase retrieval from Fourier measurements with masks
• Fast rank-one alternating minimization algorithm for phase retrieval
• Estimation from nonlinear observations via convex programming with application to bilinear regression
• Scalable incremental nonconvex optimization approach for phase retrieval
• Stable phaseless sampling and reconstruction of real-valued signals with finite rate of innovation
• Phase retrieval with PhaseLift algorithm
• Phase retrieval for sub-Gaussian measurements
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Conjugate phase retrieval in Paley-Wiener space
• Riemannian optimization for phase retrieval from masked Fourier measurements
• Recovery under side constraints
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• Constructing confidence intervals for the signals in sparse phase retrieval
• Phase retrieval of real-valued signals in a shift-invariant space
• Phase retrieval using alternating minimization in a batch setting
• Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
• Complex phase retrieval from subgaussian measurements
• Phaseless compressive sensing using partial support information
• PLS for Big Data: a unified parallel algorithm for regularised group PLS
• Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Phase retrieval from the magnitudes of affine linear measurements
• Fundamental limits of weak recovery with applications to phase retrieval
• Phase retrieval via sensor network localization
• Phase retrieval via sparse Wirtinger flow
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Misspecified nonconvex statistical optimization for sparse phase retrieval
• Admissible measurements and robust algorithms for ptychography
• Nonconvex phase synchronization
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Fast Phase Retrieval from Local Correlation Measurements
• Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
• scientific article; zbMATH DE number 7295466 (Why is no real title available?)
• Phase Retrieval Algorithm via Nonconvex Minimization Using a Smoothing Function
• Total variation-based phase retrieval for Poisson noise removal
• Solving phase retrieval via graph projection splitting
• Quantization-aware phase retrieval
• Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
• Convolutional Phase Retrieval via Gradient Descent
• PhaseMax: stable guarantees from noisy sub-Gaussian measurements
• Optimization-Based AMP for Phase Retrieval: The Impact of Initialization and $\ell_{2}$ Regularization
• Blind Ptychographic Phase Retrieval via Convergent Alternating Direction Method of Multipliers
• A min-norm approach for estimating phase distribution in an interferogram
• Phase retrieval by linear algebra
• A message-passing approach to phase retrieval of sparse signals
• Phase retrieval with background information
• A spectral estimation framework for phase retrieval via Bregman divergence minimization
• The global landscape of phase retrieval. I: Perturbed amplitude models
• The global landscape of phase retrieval. II: Quotient intensity models
• Sampling complexity on phase retrieval from masked Fourier measurements via Wirtinger flow
• Uniqueness of STFT Phase Retrieval for Bandlimited Vector Functions
• Phase retrieval via matrix completion
• Linear convergence of Frank-Wolfe for rank-one matrix recovery without strong convexity
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• Inertial proximal ADMM for separable multi-block convex optimizations and compressive affine phase retrieval
• Finding robust minimizer for non-convex phase retrieval
• Dynamic Fourier ptychography with deep spatiotemporal priors
• Compressive phase retrieval: Optimal sample complexity with deep generative priors
• Affine phase retrieval for sparse signals via \(\ell_1\) minimization
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• Provable Phase Retrieval with Mirror Descent
• Performance bounds of the intensity-based estimators for noisy phase retrieval
• Uniqueness and stability for the solution of a nonlinear least squares problem
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• Truncated amplitude flow with coded diffraction patterns
• Convergence analysis of Wirtinger flow for Poisson phase retrieval
• Bisparse blind deconvolution through hierarchical sparse recovery
• Optimal sparse phase retrieval via a quasi-Bayesian approach
• Spectral estimators for structured generalized linear models via approximate message passing
• A learned proximal alternating minimization algorithm and its induced network for a class of two-block nonconvex and nonsmooth optimization
• Sparse partial least squares with group and subgroup structure
• 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: Phase Retrieval Using Alternating Minimization

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