PhaseLift for Coded Diffraction Patterns: Optimal Sampling Rate
2026-08-03 • Information Theory
Information Theory
AI summaryⓘ
The authors study how to recover a complex signal from measurements of its Fourier intensities after applying random masks, a key problem in imaging. They focus on a method called PhaseLift and prove it can perfectly recover the signal using about log(n) masks, which is the smallest number theoretically possible. This result also translates to needing roughly n log(n) total measurements. Their proof uses a new mathematical approach that strategically adapts the measurement masks and controls errors without increasing problem size.
Phase retrievalFourier intensitiescoded diffraction patternsrandom masksPhaseLiftsampling ratecomplex-valued signaldual certificategolfing schemesignal recovery
Authors
Gao Huang, Song Li
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 $\pmb{x}_0\in\mathbb{C}^n$, up to a global phase, from $\mathcal{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=\mathcal{O}( n\log 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.