Faster Algorithms for the Sparse Fourier Transform


Event Speaker: 

Piotr Indyk (MIT)

Event Location: 


Event Date/Time: 

Tuesday, December 4, 2012 - 4:15pm

joint talk with Theory of Computation
Reception at 3:45pm in the RSA G5 Lounge
The Fast Fourier Transform (FFT) is one of the most fundamental numerical algorithms. It computes the Discrete Fourier Transform (DFT) of an n-dimensional signal in O(n log n) time. The algorithm plays an important role in many areas. It is not known whether its running time can be improved. However, in many applications (e.g., audio, image or video compression), most of the Fourier coefficients of a signal are "small" or equal to zero, i.e., the output of the transform is (approximately) sparse. In this case, it is possible to compute the set of non-zero coefficients faster than in O(n log n) time. 

In this talk, I will describe a new set of efficient algorithms for sparse Fourier Transform. One of the algorithms has running time of O(k log n), where k is the number of non-zero Fourier coefficients of the signal. This improves over the runtime of the FFT for any k = o(n). 

The talk will cover (a subset of) the material from the joint papers with Fadel Adib, Badih Ghazi, Haitham Hassanieh, Dina Katabi, Eric Price and Lixin Shi. 

The papers are available at
Piotr joined MIT in September 2000, after earning PhD from Stanford University. Earlier, he received Magister degree from Uniwersytet Warszawski in 1995. As of July 2010, he holds the title of Professor in the Department of Electrical Engineering and Computer Science.
Piotr's research interests include algorithms for high-dimensional geometric problems, algorithms using sublinear time and/or space and streaming algorithms.