Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster Fourier transform among world’s most important emerging technology

web.mit.edu

Post reply on HN
Print view View original

11–20 of 49 posts

Re: Faster Fourier transform among world’s most important emerging technology

#11

Post by DarkShikari »

geoffhill wrote: post #6
sp332 wrote: post #3

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

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.

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.

Re: Faster Fourier transform among world’s most important emerging technology

#12

Post by highfreq »

geoffhill wrote: post #6
sp332 wrote: post #3

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

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.

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.

Re: Faster Fourier transform among world’s most important emerging technology

#13

Post by trentmb »

mturmon wrote: post #7
ihodes wrote: post #5

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

...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?

But it's MIT so anything and everything they do has to be awesome.

Re: Faster Fourier transform among world’s most important emerging technology

#15

Post by guelo »

moldbug wrote: post #8

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 loc…

Algorithms and mathematical methods are not supposed to be patentable in the US.

Re: Faster Fourier transform among world’s most important emerging technology

#16

Post by ihodes »

mturmon wrote: post #7
ihodes wrote: post #5

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

...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?

Thanks :) left that important bit out. This is opposed to O(n log n) for what's been around.

Re: Faster Fourier transform among world’s most important emerging technology

#17

Post by maaku »

dustingetz wrote: post #14

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.

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

Re: Faster Fourier transform among world’s most important emerging technology

#18

Post by gliese1337 »

guelo wrote: post #15
moldbug wrote: post #8

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 loc…

Algorithms and mathematical methods are not supposed to be patentable in the US.

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.

Re: Faster Fourier transform among world’s most important emerging technology

#19

Post by cwp »

dustingetz wrote: post #14

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.

Even if it's not the bottleneck, making it faster will have the effect of making it use less power. We all want longer battery life, right?

Re: Faster Fourier transform among world’s most important emerging technology

#20

Post by Natsu »

guelo wrote: post #15
moldbug wrote: post #8

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 loc…

Algorithms and mathematical methods are not supposed to be patentable in the US.

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.
Post reply on HN