Phase Retrieval via Wirtinger Flow: Theory and Algorithms

2015/02/03 by Emmanuel J. Candès, Xiaodong Li, Mahdi Soltanolkotabi · 55 citations
Physics and Astronomy · Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced X-ray Imaging Techniques #Advanced Electron Microscopy Techniques and Applications #Optical measurement and interference techniques

paper · doi:10.1109/tit.2015.2399924

Abstract

We study the problem of recovering the phase from magnitude measurements; specifically, we wish to reconstruct a complex-valued signal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX"> \boldsymbol x∈ \mathbb Cⁿ </tex-math></inline-formula> about which we have phaseless samples of the form <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">y_r = |⟨ \boldsymbol a_r, \boldsymbol x ⟩ |² </tex-math></inline-formula> , <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">r = 1,… , m </tex-math></inline-formula> (knowledge of the phase of these samples would yield a linear system). This paper develops a nonconvex 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 nonconvex optimization schemes that may have implications for computational problems beyond phase retrieval.

Citations

• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming

Cited by

• Approximate bregman proximal gradient algorithm for relatively smooth nonconvex optimization
• Lower bounds for finding stationary points I
• An optimal statistical and computational framework for generalized tensor estimation
• On the Injectivity of STFT Phase Retrieval with super-exponential decaying window function
• Nonconvex matrix factorization is geodesically convex: global landscape analysis for fixed-rank matrix optimization from a Riemannian perspective
• Discovering Sparse Recovery Algorithms Using Neural Architecture Search
• Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data
• Single-Axis Ptychographic Coherent Diffractive Imaging for Spectroscopic and Wavefront Retrieval
• Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrieval
• A generalization bound for exit wave reconstruction via deep unfolding
• Phase Retrieval: From Computational Imaging to Machine Learning: A tutorial
• An Invitation to Hypercomplex Phase Retrieval: Theory and applications
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Bilinear Compressive Security
• Structured Random Models for Phase Retrieval with Optical Diffusers
• Transport of Event Equation: Phase Retrieval from Defocus Events
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Consistency Models as Plug-and-Play Priors for Inverse Problems
• Phase Retrieval in \mathbb C⁴ Requires Exactly Eleven Measurements
• Landscape Analysis of Simultaneous Blind Deconvolution and Phase Retrieval via Structured Low-Rank Tensor Recovery
• Recovery Performance of PhaseLift for Phase Retrieval from Coded Diffraction Patterns
• Hybrid-illumination multiplexed Fourier ptychographic microscopy with robust aberration correction
• Phase retrieval of quaternion signals via conjugate gradient method
• TReF-6: Inferring Task-Relevant Frames from a Single Demonstration for One-Shot Skill Generalization
• Unfolding Framework with Complex-Valued Deformable Attention for High-Quality Computer-Generated Hologram Generation
• High-Speed FHD Full-Color Video Computer-Generated Holography
• Revisiting the Geometrically Decaying Step Size: Linear Convergence for Smooth or Non-Smooth Functions
• A Smoothing Newton Method for Rank-one Matrix Recovery
• High-Precision Modal Analysis of Multimode Waveguides from Amplitudes via Large-Step Nonconvex Optimization
• Sparse Signal Recovery From Quadratic Systems with Full-Rank Matrices
• Fourier ptychographic microscopy with sparse representation. [europepmc]
• Sub-Diffraction Visible Imaging Using Macroscopic Fourier Ptychography and Regularization by Denoising. [europepmc]
• Dictionary Learning Phase Retrieval from Noisy Diffraction Patterns. [europepmc]
• Phaseless Terahertz Coded-Aperture Imaging Based on Incoherent Detection. [europepmc]
• Using automatic differentiation as a general framework for ptychographic reconstruction. [europepmc]
• Phaseless Terahertz Coded-Aperture Imaging for Sparse Target Based on Phase Retrieval Algorithm. [europepmc]
• Long-Distance Sub-Diffraction High-Resolution Imaging Using Sparse Sampling. [europepmc]
• Non-invasive focusing and imaging in scattering media with a fluorescence-based transmission matrix. [europepmc]
• Acoustic hologram optimisation using automatic differentiation. [europepmc]
• Efficient ptychographic phase retrieval via a matrix-free Levenberg-Marquardt algorithm. [europepmc]
• Perceptually motivated loss functions for computer generated holographic displays. [europepmc]
• Pixel Super-Resolution Phase Retrieval for Lensless On-Chip Microscopy via Accelerated Wirtinger Flow. [europepmc]
• Learning to Sense for Coded Diffraction Imaging. [europepmc]
• Direct high-resolution X-ray imaging exploiting pseudorandomness. [europepmc]
• Poisson Phase Retrieval in Very Low-count Regimes. [europepmc]
• Fast and robust Fourier ptychographic microscopy with position misalignment correction. [europepmc]
• On the use of deep learning for phase recovery. [europepmc]
• High-resolution, large field-of-view label-free imaging via aberration-corrected, closed-form complex field reconstruction. [europepmc]
• CrysFormer: Protein structure determination via Patterson maps, deep learning, and partial structure attention. [europepmc]
• Variable Splitting and Fusing for Image Phase Retrieval. [europepmc]
• Large-scale scattering-augmented optical encryption. [europepmc]
• Numerical Analysis of Mask-Based Phase Reconstruction in Phaseless Spherical Near-Field Antenna Measurements. [europepmc]
• Rapid wavefront shaping using an optical gradient acquisition. [europepmc]
• phaser: a unified and extensible framework for fast electron ptychography. [europepmc]
• Speckle-based X-ray microtomography via preconditioned Wirtinger flow. [europepmc]

Related

• Phase Retrieval via Incremental Truncated Wirtinger Flow
• Solving phase retrieval with random initial guess is nearly as good as by spectral initialization
• Robust Wirtinger Flow for Phase Retrieval with Arbitrary Corruption
• Phase Retrieval: From Computational Imaging to Machine Learning: A tutorial
• Phase Retrieval: An Overview of Recent Developments