Phase Retrieval Using Alternating Minimization

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

Sujay Sanghavi, Praneeth Netrapalli, Prateek Jain

Publication date: 22 August 2018

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

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.

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

Mathematics Subject Classification ID

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

Cited In (69)

• Quantization-aware phase retrieval
• PLS for Big Data: a unified parallel algorithm for regularised group PLS
• Total Variation--Based Phase Retrieval for Poisson Noise Removal
• Nearly optimal bounds for the global geometric landscape of phase retrieval
• PhaseMax: Stable guarantees from noisy sub-Gaussian measurements
• Phase retrieval of real-valued signals in a shift-invariant space
• Linear Convergence of Randomized Kaczmarz Method for Solving Complex-Valued Phaseless Equations
• Blind Ptychographic Phase Retrieval via Convergent Alternating Direction Method of Multipliers
• Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
• Quadratic optimization with orthogonality constraint: explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods
• Complex phase retrieval from subgaussian measurements
• Phase Retrieval by Linear Algebra
• Admissible measurements and robust algorithms for ptychography
• 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
• Phase retrieval with background information
• 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
• 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
• Median-Truncated Gradient Descent: A Robust and Scalable Nonconvex Approach for Signal Estimation
• The Global Landscape of Phase Retrieval II: Perturbed Amplitude Models
• 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
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Phase retrieval via matrix completion
• Provable Phase Retrieval with Mirror Descent
• Constructing confidence intervals for the signals in sparse phase retrieval
• Scalable incremental nonconvex optimization approach for phase retrieval
• Phase retrieval with one or two diffraction patterns by alternating projections with the null initialization
• Title not available (Why is that?)
• Fourier phase retrieval with a single mask by Douglas-Rachford algorithms
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Fast rank-one alternating minimization algorithm for phase retrieval
• Nonconvex phase synchronization
• Estimation from nonlinear observations via convex programming with application to bilinear regression
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Phase Retrieval Algorithm via Nonconvex Minimization Using a Smoothing Function
• Convolutional Phase Retrieval via Gradient Descent
• Conjugate phase retrieval in Paley-Wiener space
• Misspecified nonconvex statistical optimization for sparse phase retrieval
• On global convergence of gradient descent algorithms for generalized phase retrieval problem
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Phase retrieval via sensor network localization
• Phase retrieval using alternating minimization in a batch setting
• Phase retrieval for sub-Gaussian measurements
• Solving phase retrieval via graph projection splitting
• Phase retrieval via sparse Wirtinger flow
• Stable phaseless sampling and reconstruction of real-valued signals with finite rate of innovation
• A Message-Passing Approach to Phase Retrieval of Sparse Signals
• Affine phase retrieval for sparse signals via \(\ell_1\) minimization
• Phase retrieval from the magnitudes of affine linear measurements
• Compressive phase retrieval: Optimal sample complexity with deep generative priors
• 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*
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• Uniqueness of STFT Phase Retrieval for Bandlimited Vector Functions
• Solving systems of phaseless equations via Riemannian optimization with optimal sampling complexity
• 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
• Finding robust minimizer for non-convex phase retrieval
• Dynamic Fourier ptychography with deep spatiotemporal priors
• Truncated amplitude flow with 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)