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

2012/11/14 by Emmanuel J. Candès, Thomas Strohmer, Vladislav Voroninski · 1,240 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Advanced X-ray Imaging Techniques #Algorithm #Combinatorics #Computer science #Convex optimization #Discrete mathematics #Geometry #Mathematical optimization #Mathematics #Norm (philosophy) #Optical measurement and interference techniques #Phase (matter) #Physics #Regular polygon #SIGNAL (programming language) #Semidefinite programming #Sparse and Compressive Sensing Techniques #Unit sphere

paper · doi:10.1002/cpa.21432

published in Communications on Pure and Applied Mathematics 66(8), 1241-1274 (Wiley)

openalex publication_date 2012/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15

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 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 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 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 cross-correlation vectors, with applications to phase retrieval and blind 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
• Convergence Analysis of Reshaped Wirtinger Flow with Random Initialization for Phase Retrieval
• 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
• Saving phase: Injectivity and stability for phase retrieval
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron
• Sharp Oracle Inequalities for Low-complexity Priors
• Solving Random Systems of Quadratic Equations with Tanh Wirtinger Flow
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• High-Precision Modal Analysis of Multimode Waveguides from Amplitudes via Large-Step Nonconvex Optimization
• A Unified Framework for Identifiability Analysis in Bilinear Inverse Problems with Applications to Subspace and Sparsity Models
• Sparse Signal Recovery From Quadratic Systems with Full-Rank Matrices
• Robust Phase Retrieval and Super-Resolution from One Bit Coded Diffraction Patterns
• Hessian Eigenspectra of More Realistic Nonlinear Models
• A Theoretical Perspective of Solving Phaseless Compressed Sensing via Its Nonconvex Relaxation
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
• A convex lifting approach for the Calderón problem
• Sparse Phase Retrieval via Sparse PCA Despite Model Misspecification: A Simplified and Extended Analysis
• Matrix Recovery from Rank-One Projection Measurements via Nonconvex Minimization
• Exact Crystalline Structure Recovery in X-ray Crystallography from Coded Diffraction Patterns
• The Condition Number in Phase Retrieval from Intensity Measurements
• Blind Deconvolution using Convex Programming
• Phase retrieval with rank d measurements -- descending algorithms phase transitions
• Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view
• Phase transition of descending phase retrieval algorithms
• Phase retrieval from very few measurements
• The local convexity of solving systems of quadratic equations
• Phaseless compressive sensing using partial support information
• Multiple Illumination Phaseless Super-Resolution (MIPS) with Applications To Phaseless DOA Estimation and Diffraction Imaging
• Phase Retrieval with One or Two Diffraction Patterns by Alternating Projection with Null Initialization
• Balancing Sparsity and Rank Constraints in Quadratic Basis Pursuit
• Hierarchical restricted isometry property for Kronecker product measurements
• A strong restricted isometry property, with an application to phaseless compressed sensing
• Phase Retrieval via Gain-Based Photonic XY-Hamiltonian Optimization
• New Conditions for Sparse Phase Retrieval
• From Symmetry to Geometry: Tractable Nonconvex Problems
• Uniqueness of phase retrieval from offset linear canonical transform
• The recovery of complex sparse signals from few phaseless measurements
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Efficient Neural and Numerical Methods for High-Quality Online Speech Spectrogram Inversion via Gradient Theorem
• Robust Sparse Phase Retrieval: Statistical Guarantee, Optimality Theory and Convergent Algorithm
• Phase retrieval and matrix sensing via benign and overparametrized nonconvex optimization
• Robust Sparse Phase Retrieval Made Easy
• Solving ptychography with a convex relaxation
• Online Regularization by Denoising with Applications to Phase Retrieval
• Fourier Phase Retrieval with a Single Mask by Douglas-Rachford Algorithm
• Simultaneous Phase Retrieval and Blind Deconvolution via Convex Programming
• Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference
• Stable Recovery from the Magnitude of Symmetrized Fourier Measurements
• PhaseLift for Coded Diffraction Patterns: Optimal Sampling Rate
• Accelerated Wirtinger Flow: A fast algorithm for ptychography
• Hadamard Wirtinger Flow for Sparse Phase Retrieval
• Misspecified Nonconvex Statistical Optimization for Phase Retrieval
• Phase-only signal reconstruction by MagnitudeCut
• Multireference Alignment using Semidefinite Programming
• Coordinate Descent Algorithms for Phase Retrieval
• Solving Quadratic Equations via PhaseLift when There Are About As Many Equations As Unknowns
• Local Linear Convergence of Forward-Backward under Partial Smoothness
• Fast Phase Retrieval from Local Correlation Measurements
• Phaseless Sampling and Reconstruction of Real-Valued Signals in Shift-Invariant Spaces
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix\n Recovery
• Fast Integral Image Estimation at 1% measurement rate
• Uniqueness in inverse acoustic scattering with phaseless near-field measurements
• Tensor optimization for optical-interferometric imaging
• Minimum Number of Copies in the Measurement of Multi-Photon Entanglement
• Regularization-free estimation in trace regression with symmetric positive semidefinite matrices
• Low-Rank Adaptation Redux for Large Models
• Lecture notes on non-convex algorithms for low-rank matrix recovery
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
• Near-optimal phase retrieval of sparse vectors
• Instability, Computational Efficiency and Statistical Accuracy
• Recovery of defects from the information at detectors
• Fundamental Performance Limits for Ideal Decoders in High-Dimensional Linear Inverse Problems
• Positive Semidefinite Matrix Factorization: A Connection With Phase Retrieval and Affine Rank Minimization
• Low-Rank Phase Retrieval
• Robust Phase Retrieval with the Swept Approximate Message Passing (prSAMP) Algorithm
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Phase Retrieval From Binary Measurements
• Single-frame far-field diffractive imaging with randomized illumination
• Bilinear Compressed Sensing Under Known Signs via Convex Programming
• The Clifford group fails gracefully to be a unitary 4-design
• Exact Multistatic Interferometric Imaging via Generalized Wirtinger Flow
• Intensity-only measurement of partially uncontrollable transmission matrix: demonstration with wave-field shaping in a microwave cavity
• Wavefront Estimation From a Single Measurement: Uniqueness and Algorithms
• Optimal sparse phase retrieval via a quasi-Bayesian approach
• A Message-Passing Perspective on Ptychographic Phase Retrieval
• Phase retrieval using unitary 2-designs
• Phase Retrieval Without Small-Ball Probability Assumptions
• 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