Communications in Mathematical Sciences
Volume 5 (2007)
Empirical evaluation of a sub-linear time sparse DFT algorithm
Pages: 981 – 998
In this paper we empirically evaluate a recently proposed Fast Approximate Discrete Fourier Transform (FADFT) algorithm, FADFT-2, for the first time. FADFT-2 returns approximate Fourier representations for frequency-sparse signals and works by random sampling. Its implemen- tation is benchmarked against two competing methods. The first is the popular exact FFT imple- mentation FFTW Version 3.1. The second is an implementation of FADFT-2's ancestor, FADFT-1. Experiments verify the theoretical runtimes of both FADFT-1 and FADFT-2. In doing so it is shown that FADFT-2 not only generally outperforms FADFT-1 on all but the sparsest signals, but is also significantly faster than FFTW 3.1 on large sparse signals. Furthermore, it is demonstrated that FADFT-2 is indistinguishable from FADFT-1 in terms of noise tolerance despite FADFT-2's better execution time.
sub-linear time algorithms; Fourier transforms; compressive sensing
2010 Mathematics Subject Classification
65T40, 65T50, 68W25, 68W40