The Fourier transform is one of the most widely used computational tools. It is used in signal processing, communications, audio and video compression, medical imaging, genomics, astronomy, etc. The fastest algorithm for computing the Fourier transform is FFT, which has O(n log n) time complexity. The near-linear time of the FFT made it an indispensable tool in many applications. However, with the emergence of big data problems, in which processed data sets can exceed terabytes, FFT’s runtime is no longer sufficient and faster algorithms that do not sample every data point are required.
My work addresses this problem by designing the Sparse Fourier Transform, a family of algorithms and system architectures that compute the frequency spectrum faster than FFT. The Sparse Fourier Transform is based on the insight that many real-world signals are sparse –i.e., most of the frequencies have negligible contribution to the overall signal. Exploiting this sparsity, my work develops algorithms for computing the Fourier Transform of sparse signals very quickly (in sub-linear time). It also develops system architectures for leveraging the Sparse Fourier Transform to solve key problems in six diverse fields: wireless networks, computer graphics, medical imaging, digital circuits, astronomy, and biochemistry.
In this talk, I will give an overview of the Sparse Fourier Transform algorithms and applications. Specifically, I will show how the Sparse Fourier Transform can recover the spectrum of sparse signals faster than FFT. I will then demonstrate how to use it to: (1) Build a faster lower-power GPS receiver . (2) Improve the quality of medical images while reducing the time a patient would need to spend in an MRI machine. (3) Reconstruct light-field photography images while reducing the sampling requirements and improving reconstruction quality
Haitham Hassanieh is a Ph.D. candidate at the department of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. His research interests span both systems and theory. He worked on developing theory for the Sparse Fourier Transform algorithms and leveraging them to build systems with practical benefits in six different areas. His work on the Sparse Fourier Transform was recognized by Technology Review as one of the ten breakthrough technologies of 2012. He also worked on build wireless systems and designing networking protocols for low power wireless networks such as RFIDs and implantable medical devices. His work on securing implantable devices received the SIGCOMM best paper award.