MIT-FFT: Please think of the marketers, they are people too !

Nuit Blanche has been scooped by TechCrunch! My excuse? I was too busy asking questions at MIA 2012 ( more on that later). So let us provide some context, ever since Empirical Evaluation of a Sub-Linear Time Sparse DFT Algorithm by Mark Iwen, Anna Gilbert and Martin Strauss, I had not seen much activity on one of the cornerstone algorithm of the 20th century seen through the eyes of sparsity, a subject of central interest in compressive sensing. After talking to him, Mark eventually put an implementation of the Ann Arbor FFT (AAFFT) on Sourceforge and according to the site it got about 10,000 downloads. It is a large success in our community but it definitely is not a blockbuster outside of it. The idea is to perform an FFT on a signal known to be sparse (irrespective to where it is sparse) and be computationally more efficient than the current FFT count. A week ago, a different algorithm from MIT appeared on the interwebs. that is an improvement over the AAFFT and is the subject of the TechCrunch story. Without further due here is: Nearly Optimal Sparse Fourier Transform by Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price. The abstract reads:

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show:

* An O(k log n)-time algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and

* An O(k log n log(n/k))-time algorithm for general input signals.

Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k = o(n). Further, they are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = n^{\Omega(1)} . We complement our algorithmic results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least \Omega(k log(n/k)/ log log n) signal samples, even if it is allowed to perform adaptive sampling.

Folks, you need a name for this algorithm, I know you did the hard work, but please think of the marketers, they are people too! Since we already have the Fastest Fourier Transform in the West. (FFTW), I wonder if FFTE, Faster Fourier Transform in the East, would work since MIT is on the East coast...you know the usual East coast - West coast thingy ... oh well...

Call me a snob but what's interesting to me is that while this new algorithm is certainly a game changer, I am much more interested in this paper who Piotr Indyk also co-wrote which in my mind is certainly more of a 21st century problem: Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality by Sariel Har-Peled, Piotr Indyk, Rajeev Motwani. The abstract reads:

We present two algorithms for the approximate nearest neighbor problem in high dimensional spaces. For data sets of size n living in IRd , the algorithms require space that is only polynomial in n and d, while achieving query times that are sub-linear in n and polynomial in d. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree.

 Credit Photo: NASA, Mars from Opportunity's Camera, Sol 2820

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.