The problem of reconstructing a signal from measurements of the “amplitude” of its Fourier transform is a classic problem referred to as phase recovery and occurs in numerous applications in science and engineering. Since amplitude information is not sufficient to recover the signal, some form of prior information must be assumed. In this talk, we will assume that the underlying signal is sparse (i.e., has only a few non-zero entries); this is a very reasonable assumption in applications in astronomy, x-ray crystallography, wireless communications, etc., and is a theme that has recently garnered a great deal of attention in the context of compressed sensing. We first prove that, provided the support of the unknown signal is not “periodic”, it can be uniquely (up to time shifts and reflections) reconstructed from the magnitude of its Fourier transform. We then focus on practical algorithms to perform this recovery. We show that standard “lifting” methods that relax the problem to a semi-definite program (SDP) do not work. Instead, we employ a two-phase strategy: we first recover the support of the unknown signal using a combinatorial algorithm (of quadratic complexity), and then use the support information to recover the signal using an SDP. We prove that the algorithm is successful, provided the sparsity is less \sqrt{n}, where n is the length of the unknown signal. This is the first such guarantee for phase recovery of sparse signals. We mention some generalizations, open problems, and connections to compressed sensing, low-rank matrix recovery and the turnpike problem.
Copyright. All Rights Reserved.