PhaseLift for Coded Diffraction Patterns: Optimal Sampling Rate

2026/08/03 by Gao Huang, Song Li
Computer Science · Mathematics · #cs.IT #math.IT #math.PR

paper · pdf

32 pages, 4 figures

arxiv created 2026/08/03 · arxiv updated 2026/08/04

Abstract

Recovering a complex-valued signal from coded diffraction patterns, namely the Fourier intensities obtained after modulating the signal with a collection of masks, is a fundamental structured phase retrieval problem arising in diffraction imaging and related applications. Despite its practical importance, the theoretical analysis of this structured framework remains scarce. In the standard random mask model, the optimal sampling rate achievable by computationally tractable recovery methods has remained open. In this paper, we establish the optimal sampling rate for the PhaseLift feasibility program. More precisely, PhaseLift achieves exact recovery of an unknown signal \pmbx₀∈ℂⁿ, up to a global phase, from O(log n) random masks, with polynomially decaying failure probability. Since Ω(log n) masks are necessary to identify certain signals under the erasure mask ensemble, our result thereby achieves the optimal mask complexity. Equivalently, PhaseLift attains the optimal total sampling rate of m=O( nlog n) scalar intensity measurements. The proof is based on an approximate dual certificate construction via a refined golfing scheme that combines adaptive mask allocation with a dimension-independent truncation threshold.

Citations

• Stable Phase Retrieval: Optimal Rates in Poisson and Heavy-tailed Models
• Recovery Performance of PhaseLift for Phase Retrieval from Coded Diffraction Patterns
• Phase Retrieval via Gain-Based Photonic XY-Hamiltonian Optimization
• Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix
• Robust Outlier Bound Condition to Phase Retrieval with Adversarial Sparse Outliers
• Multiple-level Green Noise Mask Design for Practical Fourier Phase Retrieval
• Uniqueness of phase retrieval from three measurements
• Affine Phase Retrieval via Second-Order Methods
• Complex phase retrieval from subgaussian measurements
• Fourier Phase Retrieval: Uniqueness and Algorithms
• Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval
• Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
• Phase Retrieval with One or Two Diffraction Patterns by Alternating Projection with Null Initialization
• Stable low-rank matrix recovery via null space properties
• Solving Random Quadratic Systems of Equations Is Nearly as Easy as\n Solving Linear Systems
• Phase Retrieval with Application to Optical Imaging: A contemporary overview
• Low rank matrix recovery from rank one measurements
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Phase Retrieval from Coded Diffraction Patterns
• Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming
• Phase retrieval from power spectra of masked signals
• Solving Quadratic Equations via PhaseLift when There Are About As Many Equations As Unknowns
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements\n via Convex Programming
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Phase Retrieval via Matrix Completion