Faster Fourier transform among world’s most important emerging technology

Paper at: <a href="http://arxiv.org/abs/1201.2501v1" rel="nofollow">http://arxiv.org/abs/1201.2501v1</a><p>O(k log n log(n/k)) complexity for the general case.

Discussion from the initial announcement in January:<p><a href="http://news.ycombinator.com/item?id=3480016" rel="nofollow">http://news.ycombinator.com/item?id=3480016</a>

Actual article <a href="http://www.technologyreview.com/article/40245/" rel="nofollow">http://www.technologyreview.com/article/40245/</a>

Does this mean real-time Dirac video encoding might be possible?

I just had a somewhat closer look at the MIT Technology review list of emerging technologies, and in particular the people behind them. I made a rather sad discovery. Please take a look at the following list:<p>- Jonathan Tilly (stem cell research)<p>- John A. Rogers, Ralph Nuzzo, George M. Whitesides, Etienne Menard (Semprius founders)<p>- Ren Ng (light field photography, Lytro founder)<p>- Nikhil Jaisinghani, Brian Shaad (solar-powered microgrids, Mera Gao Power founders)<p>- Mark Bohr (3D transistors, head of Intel's process technology)<p>- Piotr Indyk, Dina Katabi, Eric Price, Haitham Hassanieh (Sparse Fourier transform)<p>- Gordon Sanghera, Spike Willcocks, Hagan Bayley (DNA sequencing, Oxford Nanopore founders)<p>- Perry Chen, Yancey Strickler, Charles Adler (Kickstarter founders)<p>- Peter Schultz, Robert Downs, Donald Murphy (Wildcat Discovery Technologies founders)<p>- Mark Zuckerberg (Facebook founder)<p>This is the list of the people behind all of the ten emerging technologies, as listed on <a href="http://www.technologyreview.com/tr10/" rel="nofollow">http://www.technologyreview.com/tr10/</a><p><pre><code> Number of people on the list: 23 Number of women on the list: 1 </code></pre> At least for Intels 3D transistor team and Facebook's timeline, I was not able to dig up the list of people on the team who develop these technologies, so there is still some hope that there are a few more women on these teams at least. The same should hold for the research on egg stem cell research.

they make this seem like a huge deal, anyone know why? is this going to like put HD content on an iPhone? I don't expect that the signal processing hardware is the bottleneck here.

Maybe they can use this to reduce the latency for Rocksmith?

Awesome.<p>It'll sure be nifty when 2029 rolls around and the patent expires, so applications can actually use the algorithm. (No, I don't have any information that an sFFT patent has been filed, but this would be standard practice at MIT).<p>Tornado/fountain codes are a similar case. Pardon my bitterness, but it's an interesting question to wonder whether, by funding researchers to invent algorithms of this type and lock them away behind a patent-wall for two decades, USG is advancing the progress of technology or in fact retarding it.

This is not a "faster" FFT. It's not a FFT at all.<p>"Because the SFT algorithm isn't intended to work with all possible streams of data, it can take certain shortcuts not otherwise available. In theory, an algorithm that can handle only sparse signals is much more limited than the FFT."<p>It may well be a very useful algorithm that does FFT-like operations, but the title is marketing hype and it's impossible to judge the true range of applicability of this algorithm from the article alone.

Disagree. I think that natural scrolling gestures in Mac OS Lion is more revolutionary and more intuitive to use than this "faster Fourier transform". That technology sounds like it only used by nerds, and I'm sure it has a TERRIBLE user experience.