Phase Retrieval Using Alternating Minimization

DOI10.1109/TSP.2015.2448516zbMATH Open1394.94421OpenAlexW2963443408MaRDI QIDQ4580795FDOQ4580795

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

(69)

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

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)