UTCS Colloquia - Eric Price, Faculty Candidate, MIT, "Fourier Sampling and Beyond" GDC 2.216
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.
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct