Fast Phase Retrieval from Local Correlation Measurements

DOI10.1137/15M1053761zbMATH Open1352.49035MaRDI QIDQ3179618FDOQ3179618

Authors: Aditya Viswanathan, M. A. Iwen, Yang Wang 

Publication date: 19 December 2016

Published in: SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Abstract: We develop a fast phase retrieval method which can utilize a large class of local phaseless correlation-based measurements in order to recover a given signal $$ (up to an unknown global phase) in near-linear $mathcalOleft(dlo{g}^{4}dight)$-time. Accompanying theoretical analysis proves that the proposed algorithm is guaranteed to deterministically recover all signals $$ satisfying a natural flatness (i.e., non-sparsity) condition for a particular choice of deterministic correlation-based measurements. A randomized version of these same measurements is then shown to provide nonuniform probabilistic recovery guarantees for arbitrary signals $$. Numerical experiments demonstrate the method's speed, accuracy, and robustness in practice -- all code is made publicly available. Finally, we conclude by developing an extension of the proposed method to the sparse phase retrieval problem; specifically, we demonstrate a sublinear-time compressive phase retrieval algorithm which is guaranteed to recover a given $s$-sparse vector $$ with high probability in just $mathcalO(slo{g}^{5}scdotlogd)$-time using only $mathcalO(slo{g}^{4}scdotlogd)$ magnitude measurements. In doing so we demonstrate the existence of compressive phase retrieval algorithms with near-optimal linear-in-sparsity runtime complexities.

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

Recommendations

• Phase retrieval from very few measurements
• Optimal reconstruction of images from localized phase
• Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization
• Stable phase retrieval from locally stable and conditionally connected measurements
• Phase retrieval from low-rate samples
• Phase retrieval
• Toward fast and provably accurate near-field ptychographic phase retrieval
• Phase retrieval for sub-Gaussian measurements
• Phase retrieval versus phaseless reconstruction

zbMATH Keywords

phase retrievalptychographyangular synchronizationsublinear-time algorithmscompressive phase retrieval

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Approximation algorithms (68W25) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Problems with incomplete information (optimization) (49N30) Inverse problems in optimal control (49N45) Numerical methods for discrete and fast Fourier transforms (65T50)

Cites Work

• A mathematical introduction to compressive sensing
• A simple proof of the restricted isometry property for random matrices
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Angular synchronization by eigenvectors and semidefinite programming
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Decoding by Linear Programming
• Eigenvectors of block circulant and alternating circulant matrices
• Extensions of Lipschitz mappings into a Hilbert space
• Fast Phase Retrieval from Local Correlation Measurements
• GESPAR: Efficient Phase Retrieval of Sparse Signals
• Graph implementations for nonsmooth convex programs
• Improved recovery guarantees for phase retrieval from coded diffraction patterns
• Iterative Algorithms for Ptychographic Phase Retrieval
• Iterative hard thresholding for compressed sensing
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Phase Retrieval Using Alternating Minimization
• Phase retrieval for sparse signals
• Phase retrieval from coded diffraction patterns
• Phase retrieval via Wirtinger flow: theory and algorithms
• Phase retrieval with polarization
• Phase retrieval: stability and recovery guarantees
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Robust sparse phase retrieval made easy
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
• Solving quadratic equations via phaselift when there are about as many equations as unknowns
• Sparse signal recovery from quadratic measurements via convex programming
• Stable optimizationless recovery from phaseless linear measurements
• Templates for convex cone problems with applications to sparse signal recovery
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit

Cited In (22)

• Local and global phaseless sampling in real spline spaces
• Phase retrieval from local measurements: improved robustness via eigenvector-based angular synchronization
• Lower Lipschitz bounds for phase retrieval from locally supported measurements
• Near-optimal bounds for signal recovery from blind phaseless periodic short-time Fourier transform
• Admissible measurements and robust algorithms for ptychography
• A direct solver for the phase retrieval problem in ptychographic imaging
• Fast Phase Retrieval from Local Correlation Measurements
• Toward a mathematical theory of the crystallographic phase retrieval problem
• A message-passing approach to phase retrieval of sparse signals
• Phase retrieval and system identification in dynamical sampling via Prony's method
• Phaseless reconstruction from space-time samples
• Well-conditioned ptychograpic imaging via lost subspace completion
• Coded aperture ptychography: uniqueness and reconstruction
• Raster Grid Pathology and the Cure
• BlockPR
• Maximum likelihood estimation of regularization parameters in high-dimensional inverse problems: an empirical Bayesian approach. II: Theoretical analysis
• Phase retrieval via sensor network localization
• On connections between amplitude flow and error reduction for phase retrieval and ptychography
• Phase retrieval for \(L^2([-\pi, \pi])\) via the provably accurate and noise robust numerical inversion of spectrogram measurements
• Background removal for ptychography via Wigner distribution deconvolution
• Robust Phase Retrieval Algorithm for Time-Frequency Structured Measurements
• Toward fast and provably accurate near-field ptychographic phase retrieval

Uses Software

• CVX
• CoSaMP
• TFOCS
• SparsePR
• GESPAR
• PhaseLift
• Wirtinger Flow

This page was built for publication: Fast Phase Retrieval from Local Correlation Measurements

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