Contents Online
Communications in Mathematical Sciences
Volume 5 (2007)
Number 4
Empirical evaluation of a sub-linear time sparse DFT algorithm
Pages: 981 – 998
DOI: https://dx.doi.org/10.4310/CMS.2007.v5.n4.a13
Authors
Abstract
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.
Keywords
sub-linear time algorithms, Fourier transforms, compressive sensing
2010 Mathematics Subject Classification
65T40, 65T50, 68W25, 68W40
Published 1 January 2007