6 ms·

Faster Fourier transform among world’s most important emerging technology

121 points by __Rahul 14y ago

ihodes 14y ago
Paper at: http://arxiv.org/abs/1201.2501v1 http://arxiv.org/abs/1201.2501v1 O(k log n log(n/k)) complexity for the general case.
- mturmon 14y ago
  ...where k is the number of FFT coefficients computed, and n is the time series length. Has anyone else been turned off by the sensationalism of MIT TR articles?
  - trentmb 14y ago
    But it's MIT so anything and everything they do has to be awesome.
  - ihodes 14y ago
    Thanks :) left that important bit out. This is opposed to O(n log n) for what's been around.
  - joshma 14y ago
    With all due respect, this is anything but sensationalism. It might help to understand that the number of FFT coefficients computed is not necessarily the number of data points processed. Theoretically, if we have a perfect cosine, for example, we'd get TWO non-zero coefficients (k=2) even if n was a huge number. Compare O(k logn log(n/k)) to O(nlogn) in those cases! Granted, this doesn't apply to every single situation. However, citing the article in the case of video signals, you have on average 7 "non-negligible" coefficients (k~7). So there are certainly applications that will benefit dramatically from this.
    - mturmon 14y ago
      We disagree. The big-O results of the paper are interesting and with more work could prove a starting point for improvements in very long FFTs. Why long? Because, for big-O asymptotics to kick in, you'll need large n. But, the domain of applicability seems to be a niche. The "7 non-negligible coefficients" result you refer to is for 8x8 DCT's (as in JPEG). That's n = 8. There are optimized implementations for the small-n cases that will utterly dominate a big-O optimal algorithm like this. Compare Strassen's algorithm for matrix *. Have you looked at the code complexity of the algorithm in the paper? There are several interlocking components (hash functions, rebinning) that have their own big-O optimality claims and, in some cases, randomization. Getting it all to work together efficiently, given cache issues, even for large n (say, 10^6) would be a serious engineering challenge. People have been working on optimizing data flow for FFT for decades now, and the state of the art is very advanced. I agree, that the result is interesting in principle. Runtime is actually sub-linear in n, the sequence length.
- Peaker 14y ago
  I thought normally k=n, and the ordinary complexity is O(n log(n)). So this sounds worse for the normal case. I guess if you use a smaller k it is useful.
  - thwest 14y ago
    Most signals you get by sampling real world objects will be fairly sparse. You can expect anywhere between 50% and 95% of the coefficients in a wavelet or fourier domain to be near zero depending on the class of signal. However, be wary of algorithms that expect K as input, as they are asking you to classify your signal before analysis.
moldbug 14y ago
Awesome. 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). 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.
- guelo 14y ago
  Algorithms and mathematical methods are not supposed to be patentable in the US.
  - gliese1337 14y ago
    The key phrase is "supposed to be"; "are not supposed to be patentable" does not imply "are not patented" in a system where patent examiners usually have very little idea what they're actually warding patents for and legal fees for challenging invalid patents are prohibitively high.
  - Natsu 14y ago
    That's why they patent the idea of having a general purpose computer do the math. And no, they don't care if the novel part isn't patentable subject matter and the patentable subject matter has already been invented. That's a pretty well-established dodge, except insofar as the recent Supreme Court decisions impact it.
  - zalambar 14y ago
    No problem, just find a way to implement the algorithm which doesn't violate at least one of at least 121 "fast fourier transform" pattents and you're all set (http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=0&f=S&l=50&TERM1=fast+fourier+transform&FIELD1=TI&co1=AND&TERM2=&FIELD2=&d=PTXT http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sec...). Just repeat that process for every algorithm you might want to implement and you'll have no problem writing software.
0x09 14y ago
Discussion from the initial announcement in January: http://news.ycombinator.com/item?id=3480016 http://news.ycombinator.com/item?id=3480016
dustingetz 14y ago
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.
- maaku 14y ago
  > I don't expect that the signal processing hardware is the bottleneck here. Computational resources is always the bottleneck in bioinformatics, quantum chemistry, or any sort of high data volume analysis or simulation, and the FFT is a fundamental and commonly used transform in all fields. At least for people who still use computers to, well, compute things, a faster FFT is a huge deal.
  - javajosh 14y ago
    >At least for people who still use computers to, well, compute things, a faster FFT is a huge deal. This is a useless post except that I wanted to highlight that wonderful little bon mot. Well done.
  - moultano 14y ago
    How many domains still use FFT specifically though as opposed to some other transform? Most of the signal processing papers of the last decade that I've read or read about have used either wavelets, FFT on a small window such that this isn't really applicable, or some arbitrary non-orthogonal basis.
    - KingMob 14y ago
      When I was doing EEG signal analysis in grad school, I used the FFT all the time. While there's some cool stuff involving wavelets and using interesting basis sets (matching pursuit looks cool), if you're primarily looking at power and frequency over time, the FFT is sufficient, and usually faster than the other algorithms. (And if you're looking at power/phase, the common Morlet wavelet choice is mathematically equivalent to an FT with a Gaussian taper.) I'm not sure what you mean by "on a small window such that this isn't really applicable"; can you give an example? As long as you accept the inherent time-frequency resolution trade-offs, there's no obstacle to using FFT on a small window. It's called the short-time Fourier transform (STFT), and it's used everywhere; it's probably used more than analyzing an entire signal, since we frequently want to know how power and phase change over time in a signal, and a full-signal FT can't tell you that.
laconian 14y ago
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.
- cstavish 14y ago
  I'd recommended giving the article another read.
kleiba 14y ago
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: - Jonathan Tilly (stem cell research) - John A. Rogers, Ralph Nuzzo, George M. Whitesides, Etienne Menard (Semprius founders) - Ren Ng (light field photography, Lytro founder) - Nikhil Jaisinghani, Brian Shaad (solar-powered microgrids, Mera Gao Power founders) - Mark Bohr (3D transistors, head of Intel's process technology) - Piotr Indyk, Dina Katabi, Eric Price, Haitham Hassanieh (Sparse Fourier transform) - Gordon Sanghera, Spike Willcocks, Hagan Bayley (DNA sequencing, Oxford Nanopore founders) - Perry Chen, Yancey Strickler, Charles Adler (Kickstarter founders) - Peter Schultz, Robert Downs, Donald Murphy (Wildcat Discovery Technologies founders) - Mark Zuckerberg (Facebook founder) This is the list of the people behind all of the ten emerging technologies, as listed on http://www.technologyreview.com/tr10/ http://www.technologyreview.com/tr10/ Number of people on the list: 23 Number of women on the list: 1 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.
- jpeg_hero 14y ago
  Are you disappointed because women are not contributing to "breakthrough technologies" or do you think there were worthwhile women that were overlooked?
  - rhino42 14y ago
    Highly relevant question. As someone with a signal processing background, the SFT is so huge that without doubt it should be on this list. Knowing MIT's meritocracy, they would have given the award to more women if it were appropriate
  - kleiba 14y ago
    I'm basically just stating the fact, leaving an interpretation open for everyone who's interested. A while ago, there were a few front page posts about the role of women in IT, and about how they find themselves in their work environments. The MIT list is not restricted to computer science, but perhaps it can be interpolated to the relevant fields here, too? I think it stands out that women are heavily under-represented on this list, and although explanations for that fact might be manifold, I personally just find it a bit sad to look at that outcome.
wissler 14y ago
This is not a "faster" FFT. It's not a FFT at all. "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." 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.
__Rahul 14y ago
Actual article http://www.technologyreview.com/article/40245/ http://www.technologyreview.com/article/40245/
sp332 14y ago
Does this mean real-time Dirac video encoding might be possible?
- geoffhill 14y ago
  No, Dirac is based on wavelet transforms, which have different math behind them, not using Fourier transforms. This Sparse Fourier Transform (which the authors are now calling the sFFT) would be more useful for traditional FFT/DCT compression algorithms. Though for the most part, the hardware for even very complicated real-time Fourier-based compression (H.264, HD) already exists.
  - sp332 14y ago
    Oh, for some reason I thought Dirac used DCT somehow. Here's a good overview of how it actually works for compression: http://x264dev.multimedia.cx/archives/317 http://x264dev.multimedia.cx/archives/317
  - DarkShikari 14y ago
    The sparse Fourier transform is also probably not useful for any of that stuff, because accurate results are needed (not just getting one or two of the main tones). Transforms are not the bottleneck at all in video encoding, and even in audio encoding, split-radix FFTs and the like are very fast. High-res Dirac video encoding is definitely possible in real-time, you just need a very optimized encoder, which doesn't really exist. Dirac's main speed cost comes from the overlapped-block motion compensation, not the transform.
  - highfreq 14y ago
    Assuming these are suitable for H.264, then developing H.264 hardware decoders using sFFT could reduce the power consumption. Even though the problem of hardware FFT is "solved" there is still room for improvement.
  - femto 14y ago
    The other observation I make is that apart from their computational complexity, FFTs work well in hardware because they have reasonably efficient implementations. Implementation of an FFT on a chip has two components: the logic/computing elements ( governed by O(n.log(n)) ) and the routing of signals between those elements. It turns out the size and speed of the FFT is mainly determined by the routing, not by the logic, and there is a tractable routing solution to a reasonable number of points [1]. The computation complexity becomes secondary if the complexity of the implementation is determined by the non-computational aspects. [1] Based on experience in 1995.
alainbryden 14y ago
Maybe they can use this to reduce the latency for Rocksmith?

121 points by __Rahul 14y ago

Paper at: http://arxiv.org/abs/1201.2501v1 http://arxiv.org/abs/1201.2501v1 O(k log n log(n/k)) complexity for the general case.

mturmon 14y ago
...where k is the number of FFT coefficients computed, and n is the time series length. Has anyone else been turned off by the sensationalism of MIT TR articles?
- trentmb 14y ago
  But it's MIT so anything and everything they do has to be awesome.
- ihodes 14y ago
  Thanks :) left that important bit out. This is opposed to O(n log n) for what's been around.
- joshma 14y ago
  With all due respect, this is anything but sensationalism. It might help to understand that the number of FFT coefficients computed is not necessarily the number of data points processed. Theoretically, if we have a perfect cosine, for example, we'd get TWO non-zero coefficients (k=2) even if n was a huge number. Compare O(k logn log(n/k)) to O(nlogn) in those cases! Granted, this doesn't apply to every single situation. However, citing the article in the case of video signals, you have on average 7 "non-negligible" coefficients (k~7). So there are certainly applications that will benefit dramatically from this.
  - mturmon 14y ago
    We disagree. The big-O results of the paper are interesting and with more work could prove a starting point for improvements in very long FFTs. Why long? Because, for big-O asymptotics to kick in, you'll need large n. But, the domain of applicability seems to be a niche. The "7 non-negligible coefficients" result you refer to is for 8x8 DCT's (as in JPEG). That's n = 8. There are optimized implementations for the small-n cases that will utterly dominate a big-O optimal algorithm like this. Compare Strassen's algorithm for matrix *. Have you looked at the code complexity of the algorithm in the paper? There are several interlocking components (hash functions, rebinning) that have their own big-O optimality claims and, in some cases, randomization. Getting it all to work together efficiently, given cache issues, even for large n (say, 10^6) would be a serious engineering challenge. People have been working on optimizing data flow for FFT for decades now, and the state of the art is very advanced. I agree, that the result is interesting in principle. Runtime is actually sub-linear in n, the sequence length.
Peaker 14y ago
I thought normally k=n, and the ordinary complexity is O(n log(n)). So this sounds worse for the normal case. I guess if you use a smaller k it is useful.
- thwest 14y ago
  Most signals you get by sampling real world objects will be fairly sparse. You can expect anywhere between 50% and 95% of the coefficients in a wavelet or fourier domain to be near zero depending on the class of signal. However, be wary of algorithms that expect K as input, as they are asking you to classify your signal before analysis.

moldbug 14y ago

Awesome. 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). 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.

guelo 14y ago
Algorithms and mathematical methods are not supposed to be patentable in the US.
- gliese1337 14y ago
  The key phrase is "supposed to be"; "are not supposed to be patentable" does not imply "are not patented" in a system where patent examiners usually have very little idea what they're actually warding patents for and legal fees for challenging invalid patents are prohibitively high.
- Natsu 14y ago
  That's why they patent the idea of having a general purpose computer do the math. And no, they don't care if the novel part isn't patentable subject matter and the patentable subject matter has already been invented. That's a pretty well-established dodge, except insofar as the recent Supreme Court decisions impact it.
- zalambar 14y ago
  No problem, just find a way to implement the algorithm which doesn't violate at least one of at least 121 "fast fourier transform" pattents and you're all set (http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=0&f=S&l=50&TERM1=fast+fourier+transform&FIELD1=TI&co1=AND&TERM2=&FIELD2=&d=PTXT http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sec...). Just repeat that process for every algorithm you might want to implement and you'll have no problem writing software.

0x09 14y ago

Discussion from the initial announcement in January: http://news.ycombinator.com/item?id=3480016 http://news.ycombinator.com/item?id=3480016

dustingetz 14y ago

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.

maaku 14y ago
> I don't expect that the signal processing hardware is the bottleneck here. Computational resources is always the bottleneck in bioinformatics, quantum chemistry, or any sort of high data volume analysis or simulation, and the FFT is a fundamental and commonly used transform in all fields. At least for people who still use computers to, well, compute things, a faster FFT is a huge deal.
- javajosh 14y ago
  >At least for people who still use computers to, well, compute things, a faster FFT is a huge deal. This is a useless post except that I wanted to highlight that wonderful little bon mot. Well done.
- moultano 14y ago
  How many domains still use FFT specifically though as opposed to some other transform? Most of the signal processing papers of the last decade that I've read or read about have used either wavelets, FFT on a small window such that this isn't really applicable, or some arbitrary non-orthogonal basis.
  - KingMob 14y ago
    When I was doing EEG signal analysis in grad school, I used the FFT all the time. While there's some cool stuff involving wavelets and using interesting basis sets (matching pursuit looks cool), if you're primarily looking at power and frequency over time, the FFT is sufficient, and usually faster than the other algorithms. (And if you're looking at power/phase, the common Morlet wavelet choice is mathematically equivalent to an FT with a Gaussian taper.) I'm not sure what you mean by "on a small window such that this isn't really applicable"; can you give an example? As long as you accept the inherent time-frequency resolution trade-offs, there's no obstacle to using FFT on a small window. It's called the short-time Fourier transform (STFT), and it's used everywhere; it's probably used more than analyzing an entire signal, since we frequently want to know how power and phase change over time in a signal, and a full-signal FT can't tell you that.

laconian 14y ago

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.

cstavish 14y ago
I'd recommended giving the article another read.

kleiba 14y ago

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: - Jonathan Tilly (stem cell research) - John A. Rogers, Ralph Nuzzo, George M. Whitesides, Etienne Menard (Semprius founders) - Ren Ng (light field photography, Lytro founder) - Nikhil Jaisinghani, Brian Shaad (solar-powered microgrids, Mera Gao Power founders) - Mark Bohr (3D transistors, head of Intel's process technology) - Piotr Indyk, Dina Katabi, Eric Price, Haitham Hassanieh (Sparse Fourier transform) - Gordon Sanghera, Spike Willcocks, Hagan Bayley (DNA sequencing, Oxford Nanopore founders) - Perry Chen, Yancey Strickler, Charles Adler (Kickstarter founders) - Peter Schultz, Robert Downs, Donald Murphy (Wildcat Discovery Technologies founders) - Mark Zuckerberg (Facebook founder) This is the list of the people behind all of the ten emerging technologies, as listed on http://www.technologyreview.com/tr10/ http://www.technologyreview.com/tr10/ Number of people on the list: 23 Number of women on the list: 1 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.

jpeg_hero 14y ago
Are you disappointed because women are not contributing to "breakthrough technologies" or do you think there were worthwhile women that were overlooked?
- rhino42 14y ago
  Highly relevant question. As someone with a signal processing background, the SFT is so huge that without doubt it should be on this list. Knowing MIT's meritocracy, they would have given the award to more women if it were appropriate
- kleiba 14y ago
  I'm basically just stating the fact, leaving an interpretation open for everyone who's interested. A while ago, there were a few front page posts about the role of women in IT, and about how they find themselves in their work environments. The MIT list is not restricted to computer science, but perhaps it can be interpolated to the relevant fields here, too? I think it stands out that women are heavily under-represented on this list, and although explanations for that fact might be manifold, I personally just find it a bit sad to look at that outcome.

wissler 14y ago

This is not a "faster" FFT. It's not a FFT at all. "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." 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.

__Rahul 14y ago

Actual article http://www.technologyreview.com/article/40245/ http://www.technologyreview.com/article/40245/

sp332 14y ago

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

geoffhill 14y ago
No, Dirac is based on wavelet transforms, which have different math behind them, not using Fourier transforms. This Sparse Fourier Transform (which the authors are now calling the sFFT) would be more useful for traditional FFT/DCT compression algorithms. Though for the most part, the hardware for even very complicated real-time Fourier-based compression (H.264, HD) already exists.
- sp332 14y ago
  Oh, for some reason I thought Dirac used DCT somehow. Here's a good overview of how it actually works for compression: http://x264dev.multimedia.cx/archives/317 http://x264dev.multimedia.cx/archives/317
- DarkShikari 14y ago
  The sparse Fourier transform is also probably not useful for any of that stuff, because accurate results are needed (not just getting one or two of the main tones). Transforms are not the bottleneck at all in video encoding, and even in audio encoding, split-radix FFTs and the like are very fast. High-res Dirac video encoding is definitely possible in real-time, you just need a very optimized encoder, which doesn't really exist. Dirac's main speed cost comes from the overlapped-block motion compensation, not the transform.
- highfreq 14y ago
  Assuming these are suitable for H.264, then developing H.264 hardware decoders using sFFT could reduce the power consumption. Even though the problem of hardware FFT is "solved" there is still room for improvement.
- femto 14y ago
  The other observation I make is that apart from their computational complexity, FFTs work well in hardware because they have reasonably efficient implementations. Implementation of an FFT on a chip has two components: the logic/computing elements ( governed by O(n.log(n)) ) and the routing of signals between those elements. It turns out the size and speed of the FFT is mainly determined by the routing, not by the logic, and there is a tractable routing solution to a reasonable number of points [1]. The computation complexity becomes secondary if the complexity of the implementation is determined by the non-computational aspects. [1] Based on experience in 1995.

alainbryden 14y ago

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