The Sparse Fourier Transform

Abstract

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 Z₂k where k is the smallest integer such that n<= ₂k, provided the function has certain special properties. This method is based on ideas from Shor's algorithm for factoring integers.