Sparse Fast Fourier Transform :
The discrete Fourier transform (DFT) is one of the most important and widely used computational tasks. Its
applications are broad and include signal processing, communications, and audio/image/video compression.
Hence, fast algorithms for DFT are highly valuable. Currently, the fastest such algorithm is the Fast Fourier
Transform (FFT), which computes the DFT of an n-dimensional signal in O(nlogn) time. The existence
of DFT algorithms faster than FFT is one of the central questions in the theory of algorithms.
A general algorithm for computing the exact DFT must take time at least proportional to its output size n.
In many applications, however, most of the Fourier coefficients of a signal are small or equal
to zero, i.e., the output of the DFT is sparse. This is the case for video signals, where a
typical 8x8 block in a video frame has on average 7 non-negligible frequency coefficients (i.e., 89% of the
coefficients are negligible). For sparse signals, the Ω(n) lower bound for the complexity of DFT no longer applies. If a signal has
a small number k of non-zero Fourier coefficients the output of the Fourier
transform can be represented succinctly using only k coefficients. Hence, for such signals, we can find
DFT algorithms whose runtime is sublinear in the signal size, n.
We present here several new results for sparse Fourier transform:
- An O(k log n)-time algorithm for the exactly k-sparse case.
- An O(k log n log(n/k))-time algorithm for the general case.
- An Ω(k log(n/k) loglog n) lower bound for sample complexity.
Both algorithms improve over FFT, for any k = o(n).
Moreover, if one assume that FFT is optimal, the algorithm for the exactly k-sparse case is optimal.
Under the same assumption, the result for the general case is at most one loglog n factor away from
the optimal runtime for the case of “large” sparsity k = n/log n.
This research is supported in part by NSF and DARPA.
The Faster-than-Fast Fourier Transform
For a large range of practically useful cases, MIT researchers find a way to increase the speed of one of the most important algorithms in the information sciences.
Larry Hardesty, MIT News Office
A Faster Fast Fourier Transform
New algorithm crunches sparse data with speed
David Schneider, IEEE Spectrum