The Sparse Fourier Transform

The Sparse Fourier Transform

The Fourier transform is one of the most fundamental tools for computing the frequency representation of signals. It plays a central role in signal processing, communications, audio and video compression, medical imaging, genomics, astronomy, as well as many other areas. Because of its widespread use, fast algorithms for computing the Fourier transform can benefit a large number of applications. The fastest algorithm for computing the Fourier transform is the Fast Fourier Transform (FFT), which runs in near-linear time making it an indispensable tool for many applications. However, today, the runtime of the FFT algorithm is no longer fast enough especially for big data problems where each dataset can be few terabytes. Hence, faster algorithms that run in sublinear time, i.e., do not even sample all the data points, have become necessary. This book addresses the above problem by developing the Sparse Fourier Transform algorithms and building practical systems that use these algorithms to solve key problems in six different applications: wireless networks; mobile systems; computer graphics; medical imaging; biochemistry; and digital circuits. This is a revised version of the thesis that won the 2016 ACM Doctoral Dissertation Award.

The Sparse Fourier Transform

The Sparse Fourier Transform

Some functions can be well approximated by taking their Fourier transforms and discarding the terms that have small Fourier coefficients. The sparse Fourier transform is an algorithm that computes such an approximation more efficiently than computing the entire Fourier transform. The sparse Fourier transform has many applications to problems in mathematics and engineering. For example, in mathematics the sparse Fourier transform can be used to solve the chosen multiplier hidden number problem. In engineering, the sparse Fourier transform can be used to compress audio or video data. In Chapter 3 we present an algorithm that computes the sparse Fourier transform. This algorithm generalises and unifies the sparse fast Fourier transforms in [19] and [21]. These algorithms are of particular importance as they are the earliest algorithms for computing the sparse Fourier transform. The final chapter develops a method for reducing the problem of calculating the sparse Fourier transform over Zn to calculating it over Z2k where k is the smallest integer such that n