Empirical evaluation of a sub-linear time sparse DFT algorithm
Iwen, M.A. ; Gilbert, A. ; Strauss, M.
Commun. Math. Sci., Tome 5 (2007) no. 1, p. 981-998 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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.
Publié le : 2007-12-15
Classification:  sub-linear time algorithms,  Fourier transforms,  compressive sensing,  65T50,  68W40,  68W25,  65T40 
@article{1199377561,
     author = {Iwen, M.A. and Gilbert, A. and Strauss, M.},
     title = {Empirical evaluation of a sub-linear time sparse DFT algorithm},
     journal = {Commun. Math. Sci.},
     volume = {5},
     number = {1},
     year = {2007},
     pages = { 981-998},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1199377561}
}

Iwen, M.A.; Gilbert, A.; Strauss, M. Empirical evaluation of a sub-linear time sparse DFT algorithm. Commun. Math. Sci., Tome 5 (2007) no. 1, pp.  981-998. http://gdmltest.u-ga.fr/item/1199377561/