Phase retrieval in the high-dimensional regime

The main focus of this thesis is on the phase retrieval problem. This problem has a broad range of applications in advanced imaging systems, such as X-ray crystallography, coherent diffraction imaging, and astrophotography. Thanks to its broad applications and its mathematical elegance and sophistication, phase retrieval has attracted researchers with diverse backgrounds. Formally, phase retrieval is the problem of recovering a signal ∈ ℂⁿ from its phaseless linear measurements of the form |ᵢ∗| + ᵢ where sensing vectors ᵢ, = 1, 2, ..., , are in the same vector space as and ᵢ denotes the measurement noise. Finding an effective recovery method in a practical setup, analyzing the required sample complexity and convergence rate of a solution, and discussing the optimality of a proposed solution are some of the major mathematical challenges that researchers have tried to address in the last few years. In this thesis, our aim is to shed some light on some of these challenges and propose new ways to improve the imaging systems that have this problem at their core. Toward this goal, we focus on the high-dimensional setting where the ratio of the number of measurements to the ambient dimension of the signal remains bounded. This regime differs from the classical asymptotic regime in which the signal's dimension is fixed and the number of measurements is increasing. We obtain sharp results regarding the performance of the existing algorithms and the algorithms that are introduced in this thesis. To achieve this goal, we first develop a few sharp concentration inequalities. These inequalities enable us to obtain sharp bounds on the performance of our algorithms. We believe such results can be useful for researchers who work in other research areas as well. Second, we study the spectrum of some of the random matrices that play important roles in the phase retrieval problem, and use our tools to study the performance of some of the popular phase retrieval recovery schemes. Finally, we revisit the problem of structured signal recovery from phaseless measurements. We propose an iterative recovery method that can take advantage of any prior knowledge about the signal that is given as a compression code to efficiently solve the problem. We rigorously analyze the performance of our proposed method and provide extensive simulations to demonstrate its state-of-the-art performance