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. 

Of relevance to all this, all the Slides of the recent Workshop on Sparse Fourier Transform organized by Piotr are here. 

[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

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.