What’s the frequency, Kenneth?: A survey of Fourier sampling algorithms
Anna Gilbert
Department of Mathematics, University of Michigan
Date and time:
Friday, January 25, 2013 - 1:15pm
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.