Eastern Great Lakes Theory Workshop Talk

A Survey of Fourier Sampling Algorithms

Anna Gilbert, University of Michigan

Sunday, September 30, 9:00-10:00am

ABSTRACT

In the last decade, scientists, mathematicians, and engineers have recognized that our ability to generate data far exceeds our ability to record it, to analyze it, and to extract meaningful information from it. In recognition of this limitation, computer scientists have developed streaming algorithms that can efficiently process streams of data in sketches and then analyze those sketches very efficiently, mathematicians have developed mathematical models of highly efficient data acquisition and processing, and engineers have built systems for efficiently collecting signal or image information. One of the problems that all three disciplines have contributed to is that of Fourier sampling---designing an efficient sampling set (or collecting a small number of samples of a signal) so that, from those samples, one can determine very efficiently which frequencies are dominant in the signal (equivalently, one can construct an algorithm to find these frequencies). For this problem, computer scientists have developed algorithms that are faster than the FFT, electrical engineers have built analog to digital converters that sample at sub-Nyquist rates, and mathematicians have contributed solid theoretical underpinnings to these results. In this talk, we will cover the basic problem, the highly efficient recovery algorithms, and some of the analog-to-digital converter designs.

Speaker Bio

Anna Gilbert received an S.B. degree from the University of Chicago and a Ph.D. from Princeton University, both in mathematics. In 1997, she was a postdoctoral fellow at Yale University and AT&T Labs-Research. From 1998 to 2004, she was a member of technical staff at AT&T Labs-Research in Florham Park, NJ. Since then she has been with the Department of Mathematics at the University of Michigan, where she is now a Professor. She has received several awards, including a Sloan Research Fellowship (2006), an NSF CAREER award (2006), the National Academy of Sciences Award for Initiatives in Research (2008), the Association of Computing Machinery (ACM) Douglas Engelbart Best Paper award (2008), and the EURASIP Signal Processing Best Paper award (2010).

Her research interests include analysis, probability, networking, and algorithms. She is especially interested in randomized algorithms with applications to harmonic analysis, signal and image processing, networking, and massive datasets.

< Schedule < EaGL-V homepage