UTCS Colloquia - Eric Price, Faculty Candidate, MIT, "Fourier Sampling and Beyond" GDC 2.216

Contact Name: 
Kate Callard
GDC Auditorium 2.216
Apr 4, 2013 11:00am - 12:00pm


Signup Schedule: http://apps.cs.utexas.edu/talkschedules/cgi/list_events.cgi

Talk Audience: UTCS Faculty, Grads, Undergrads, Other Interested Parties

Host:  C Greg Plaxton

Talk Abstract: The Fast Fourier Transform (FFT) is a fundamental algorithm that computes the Discrete Fourier Transform of an n-dimensional signal in O(n log n) time. It is unknown whether the running time can be improved in general. However, in applications such as image, audio, and video compression where the output is "sparse" (i.e., k<<n coordinates are "large" and contain most of the energy), it is possible to estimate the large coordinates in less than O(n log n) time. We show the first algorithms that achieve this for any k=o(n).

The sparse Fourier transform problem lies in the broader area of sparse recovery and compressive sensing. This area considers the robust of a sparse vector x from relatively few linear measurements Ax, and has applications in diverse settings such as streaming algorithms, camera design, and genetic testing. We discuss multiple extensions to the sparse recovery framework, including a proof that the number of measurement can be improved-- in some cases exponentially-- if the measurements are chosen adaptively.

Speaker Bio: Eric Price is currently finishing his PhD at MIT under the supervision of Piotr Indyk. He received Bachelor's degrees in Computer Science and Mathematics from MIT. His research interests include sparse recovery, data structures, and information theory. Eric received a 2009 NSF Graduate Research Fellowship and a 2012 Simons Graduate Fellowship.