Friday, May 17, 2013

Sparse FFT implementations

Dmitry Savostyanov pointed me to the location of an implementation of the other super Fast FFT we mentioned last September. It is on GitHub here as part of the very promising TT-Toolbox

Let us note that the sparse FFT "looks" slower than MIT's sFFT and that the MIT sFFT has currently only version 1 and 2 while Piotr mentioned results for version 3 and 4 on Wednsday at the "Big data: theoretical and practical challenges" workshop.

We are waiting for the Berkeley implementation mentioned previously for the end of the summer. The Ann Arbor FFT (AAFFT) is here.  

With regards to the comparison between sFFT [2] and the TT_toolbox version [1]


It looks like sFFT version 3.0 scales better for K sparse signals than the TT_toolvox one which scales as K^3. But I wouldn't mind seeing comparison for compressible signals (I think it is version 4.0 for sFFT) and the TT_toolbox one. An interesting comparison should eventually entail not integer frequencies and higher dimensions as well. 




[1] Superfast Fourier Transform Using QTT Approximation by Sergey Dolgov, Boris Khoromskij and Dmitry Savostyanov.
[2] http://groups.csail.mit.edu/netmit/sFFT/results.html

No comments:

Printfriendly