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 thesis 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.
Thesis Supervisor: Professor Dina Katabi