HOMOTOPY CONTINUATION METHODS FOR PHASE RETRIEVAL

Abstract

In this dissertation, we discuss the problem of recovering a signal from a set of phaseless measurements. This type of problem shows up in numerous applications and is known for its numerical difficulty. It finds use in X-ray Crystallography, Microscopy, Quantum Information, and many others. We formulate the problem using a non-convex quadratic loss function whose global minimum recovers the phase of the measurement.Our approach to this problem is via a Homotopy Continuation Method. These methods have found great use in solving systems of nonlinear equations in numer- ical algebraic geometry. The idea is to initialize the solution of a related system at a known global optimal, then continuously deform the criterion and follow the solution path until we find the minimum of the desired loss function. We analyze convergence properties and asymptotic results for these algorithms, as well as gather some numerical statistics. The main contribution of this thesis is deriving conditions for convergence of the algorithm and an asymptotic rate for when these conditions are satisfied. We also show that the algorithm achieves good numerical accuracy. The dissertation is split into several chapters, and further divided by the real and complex case. Chapter 1 gives some background to Abstract Phase Retrieval and Homotopy Continuation Methods. Chapter 2 covers the nature of the algorithm (named the Golden Retriever), gives a summary and description of the theoretical results, and shows some numerical results. Chapter 3 covers the details of the derivation and results in the real case, and Chapter 4 covers the same for the complex case.