Abstract
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 than the square root of 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.
Biography
Babak Hassibi is professor and executive officer of electrical engineering at the California Institute of Technology, where he has been since 2001. From 1998 to 2001 he was a member of the technical staff at the Mathematical Sciences Research Center at Bell Laboratories, Murray Hill, NJ, and prior to that he obtained his PhD in electrical engineering from Stanford University. His research interests span different aspects of communications, signal processing and control. Among other awards, he is a recipient of the David and Lucille Packard Foundation Fellowship, and the Presidential Early Career Award for Scientists.
