Abstract
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 and the need for real-time decision making, FFT’s runtime is no longer sufficient and faster algorithms that do not sample every data point are required. The Sparse Fourier Transform is a family of algorithms 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 a negligible contribution to the overall signal. Exploiting this sparsity, we can compute the Fourier Transform of sparse signals very quickly (in sub-linear time). In this talk, I will give an overview of the Sparse Fourier Transform algorithms with a focus on real-time applications like GPS receivers, dynamic spectrum access, 5G wireless network, and radio astronomy.