Fast Phase Retrieval from Local Correlation Measurements

DOI10.1137/15M1053761zbMATH Open1352.49035arXiv1501.02377MaRDI QIDQ3179618FDOQ3179618

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

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

Cited In (20)

• 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
• Maximum Likelihood Estimation of Regularization Parameters in High-Dimensional Inverse Problems: An Empirical Bayesian Approach. Part II: Theoretical Analysis
• Phase retrieval and system identification in dynamical sampling via Prony's method
• Phaseless reconstruction from space-time samples
• Coded aperture ptychography: uniqueness and reconstruction
• Raster Grid Pathology and the Cure
• BlockPR
• 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
• Toward a Mathematical Theory of the Crystallographic Phase Retrieval Problem
• Robust Phase Retrieval Algorithm for Time-Frequency Structured Measurements
• Toward fast and provably accurate near-field ptychographic phase retrieval
• Well-conditioned ptychographic imaging via lost subspace completion

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)