PROJECT WEBPAGE
Go to Project's Main Webpage:
http://groups.csail.mit.edu/netmit/sFFT/
overview
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.
papers
Nearly Optimal Sparse Fourier Transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi and Eric Price
STOC 2012. PDF
Simple and Practical Algorithm for Sparse Fourier Transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi and Eric Price
SODA 2012. PDF
people
Haitham Al Hassanieh
Massachusetts Institute of Technology
Eric Price
Massachusetts Institute of Technology
Piotr Indyk
Massachusetts Institute of Technology
Dina Katabi
Massachusetts Institute of Technology
|
|
|
|
|