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

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)