Academic Commons

Theses Doctoral

High-dimensional Asymptotics for Phase Retrieval with Structured Sensing Matrices

Dudeja, Rishabh

Phase Retrieval is an inference problem where one seeks to recover an unknown complex-valued 𝓃-dimensional signal vector from the magnitudes of 𝓶 linear measurements. The linear measurements are specified using a 𝓶 × 𝓃 sensing matrix. This problem is a mathematical model for imaging systems arising in X-ray crystallography and other applications where it is infeasible to acquire the phase of the measurements. This dissertation presents some results regarding the analysis of this problem in the high-dimensional asymptotic regime where the number of measurements and the signal dimension diverge proportionally so that their ratio remains fixed. A limitation of existing high-dimensional analyses of this problem is that they model the sensing matrix as a random matrix with independent and identically (i.i.d.) distributed Gaussian entries. In practice, this matrix is highly structured with limited randomness.

This work studies a correction to the i.i.d. Gaussian sensing model, known as the sub-sampled Haar sensing model which faithfully captures a crucial orthogonality property of realistic sensing matrices. The first result of this thesis provides a precise asymptotic characterization of the performance of commonly used spectral estimators for phase retrieval in the sub-sampled Haar sensing model. This result can be leveraged to tune certain parameters involved in the spectral estimator optimally.

The second part of this dissertation studies the information-theoretic limits for better-than-random (or weak) recovery in the sub-sampled Haar sensing model. The main result in this part shows that appropriately tuned spectral methods achieve weak recovery with the information-theoretically optimal number of measurements. Simulations indicate that the performance curves derived for the sub-sampled Haar sensing model accurately describe the empirical performance curves for realistic sensing matrices such as randomly sub-sampled Fourier sensing matrices and Coded Diffraction Pattern (CDP) sensing matrices. The final part of this dissertation tries to provide a mathematical understanding of this empirical universality phenomenon: For the real-valued version of the phase retrieval problem, the main result of the final part proves that the dynamics of a class of iterative algorithms, called Linearized Approximate Message Passing schemes, are asymptotically identical in the sub-sampled Haar sensing model and a real-valued analog of the sub-sampled Fourier sensing model.


  • thumnail for Dudeja_columbia_0054D_16667.pdf Dudeja_columbia_0054D_16667.pdf application/pdf 2.05 MB Download File

More About This Work

Academic Units
Thesis Advisors
Maleki, Arian
Ph.D., Columbia University
Published Here
June 30, 2021