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

2012/11/14 by Emmanuel J. Candès, Thomas Strohmer, Vladislav Voroninski · 96 citations
Physics and Astronomy · Computer Science · Engineering · #Advanced X-ray Imaging Techniques #Optical measurement and interference techniques #Sparse and Compressive Sensing Techniques

paper · doi:10.1002/cpa.21432

Abstract

Abstract Suppose we wish to recover a signal \input amssym \font\abc=cmmib10\def\bi#1\hbox\abc#1 \bi x ∈ \Bbb Cⁿ from m intensity measurements of the form \font\abc=cmmib10\def\bi#1\hbox\abc#1 |⟨ \bi x,\bi z_i ⟩|² , i = 1, 2, …, m ; that is, from data in which phase information is missing. We prove that if the vectors \font\abc=cmmib10\def\bi#1\hbox\abc#1\bi z_i are sampled independently and uniformly at random on the unit sphere, then the signal x can be recovered exactly (up to a global phase factor) by solving a convenient semidefinite program–‐a trace‐norm minimization problem; this holds with large probability provided that m is on the order of n log n , and without any assumption about the signal whatsoever. This novel result demonstrates that in some instances, the combinatorial phase retrieval problem can be solved by convex programming techniques. Finally, we also prove that our methodology is robust vis‐à‐vis additive noise. © 2012 Wiley Periodicals, Inc.

Cited by

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Phaseless Reconstruction from Space-Time Samples
• A general framework for denoising phaseless diffraction measurements
• Almost everywhere injectivity conditions for the matrix recovery problem
• Spectral Method for Phase Retrieval: an Expectation Propagation Perspective
• On the Search for Tight Frames of Low Coherence
• Spectral Experts for Estimating Mixtures of Linear Regressions
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• Stable Blind Deconvolution over the Reals from Additional\n Autocorrelations
• Nonlinear frames and sparse reconstructions in Banach spaces
• Fast Compressive Phase Retrieval from Fourier Measurements
• The estimation performance of nonlinear least squares for phase retrieval
• Tight convex relaxations for sparse matrix factorization
• Learning Illumination Patterns for Coded Diffraction Phase Retrieval
• The Cahill-Casazza-Daubechies problem on Hölder stable phase retrieval
• Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Phase Retrieval Based on DC and DnCNN
• Phase retrieval by random binary questions: Which complementary subspace is closer?
• InstaHide: Instance-hiding Schemes for Private Distributed Learning
• Dynamical phase retrieval for Schrödinger evolution on finite graphs
• Provable Low Rank Phase Retrieval
• Phase Retrieval with Application to Optical Imaging: A contemporary overview
• 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
• Leveraging Diversity and Sparsity in Blind Deconvolution
• PhaseLiftOff: an Accurate and Stable Phase Retrieval Method Based on Difference of Trace and Frobenius Norms
• Quantum Tomography From Few Full-Rank Observables
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Learning Polynomials of Few Relevant Dimensions
• Sparse phase retrieval via group-sparse optimization
• Generalized phase retrieval : measurement number, matrix recovery and beyond
• Hydrogen density mapping in biomolecular crystals through dynamic nuclear polarization
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence
• Stable Camera Motion Estimation Using Convex Programming
• Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
• Provably Convergent Algorithms for Solving Inverse Problems Using Generative Models
• Phased and phaseless domain reconstruction in inverse scattering problem via scattering coefficients
• Structured Random Models for Phase Retrieval with Optical Diffusers
• A direct solver for the phase retrieval problem in ptychographic imaging
• Scaling Limit: Exact and Tractable Analysis of Online Learning Algorithms with Applications to Regularized Regression and PCA
• Stationary Points of a Shallow Neural Network with Quadratic Activations and the Global Optimality of the Gradient Descent Algorithm
• Average Kernel Sizes -- Computable Sharp Accuracy Bounds for Inverse Problems
• Linear Convergence of An Iterative Phase Retrieval Algorithm with Data Reuse
• Universality in Learning from Linear Measurements
• Phase retrieval of complex-valued objects via a randomized Kaczmarz method
• A Conditional Gradient-Based Augmented Lagrangian Framework
• On the Benefits of Weight Normalization for Overparameterized Matrix Sensing
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as\n Solving Linear Systems
• On the Performance of Amplitude-Based Models for Low-Rank Matrix Recovery
• Rapid, robust, and reliable blind deconvolution via nonconvex optimization
• Improved Algorithms for Matrix Recovery from Rank-One Projections
• Phase Retrieval in \mathbb C⁴ Requires Exactly Eleven Measurements
• Alternating Phase Projected Gradient Descent with Generative Priors for\n Solving Compressive Phase Retrieval
• Sublinear-Time Algorithms for Compressive Phase Retrieval
• Regularized Gradient Descent: A Nonconvex Recipe for Fast Joint Blind Deconvolution and Demixing
• Global and Local Analyses of Nonlinear Low-Rank Matrix Recovery Problems
• Towards Seeing Bones at Radio Frequency
• Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning
• Frame Phase-retrievability and Exact phase-retrievable frames
• Low rank matrix recovery from Clifford orbits
• Recovery Performance of PhaseLift for Phase Retrieval from Coded Diffraction Patterns
• DOA estimation in structured phase-noisy environments: technical report
• A convex program for bilinear inversion of sparse vectors
• prDeep: Robust Phase Retrieval with a Flexible Deep Network
• Controlling Light Transmission Through Highly Scattering Media Using\n Semi-Definite Programming as a Phase Retrieval Computation Method
• Stochastic Methods for Composite and Weakly Convex Optimization Problems
• On Lipschitz Analysis and Lipschitz Synthesis for the Phase Retrieval Problem
• New error measures and methods for realizing protein graphs from\n distance data
• Low-rank matrix recovery via rank one tight frame measurements
• Phase Retrieval with Application to Optical Imaging
• Intrinsic training dynamics of deep neural networks
• Reconstruction of signals from their autocorrelation and\n cross-correlation vectors, with applications to phase retrieval and blind\n channel estimation
• Determination of all pure quantum states from a minimal number of observables
• Phase retrieval for imaging problems
• A Smoothing Newton Method for Rank-one Matrix Recovery
• Conjugate phase retrieval on graphs and with applications in shift-invariant spaces
• Inverse Problems, Deep Learning, and Symmetry Breaking
• Towards the optimal construction of a loss function without spurious local minima for solving quadratic equations
• Solving Systems of Quadratic Equations via Exponential-type Gradient Descent Algorithm
• Optimal Sample Complexity for Stable Matrix Recovery
• Recovering Jointly Sparse Signals via Joint Basis Pursuit
• Partially coherent phase imaging with simultaneous source recovery. [europepmc]
• A Motion Detection Algorithm Using Local Phase Information. [europepmc]
• Motion-corrected Fourier ptychography. [europepmc]
• Sparse Functional Identification of Complex Cells from Spike Times and the Decoding of Visual Stimuli. [europepmc]
• A new mathematical approach to finding global solutions of the magnetic structure determination problem. [europepmc]
• Imaging through scattering media using semidefinite programming. [europepmc]
• Phaseless Terahertz Coded-Aperture Imaging for Sparse Target Based on Phase Retrieval Algorithm. [europepmc]
• Learning to Sense for Coded Diffraction Imaging. [europepmc]
• Poisson Phase Retrieval in Very Low-count Regimes. [europepmc]
• On the use of deep learning for phase recovery. [europepmc]
• CrysFormer: Protein structure determination via Patterson maps, deep learning, and partial structure attention. [europepmc]
• Numerical Analysis of Mask-Based Phase Reconstruction in Phaseless Spherical Near-Field Antenna Measurements. [europepmc]
• Speckle-based X-ray microtomography via preconditioned Wirtinger flow. [europepmc]
• Phase retrieval via gain-based photonic XY-Hamiltonian optimization [europepmc]

Related

• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements\n via Convex Programming
• PhaseMax: Convex Phase Retrieval via Basis Pursuit
• PhaseLiftOff: an Accurate and Stable Phase Retrieval Method Based on Difference of Trace and Frobenius Norms
• A Precise Analysis of PhaseMax in Phase Retrieval
• Corruption Robust Phase Retrieval via Linear Programming