Here's the SODA paper:
The faster-than-fast Fourier transform
21–30 of 33 posts
Re: The faster-than-fast Fourier transform
#22The talk at SODA is in 1.5 hours, I'm going to attend it.
Any other HNers at SODA?
Re: The faster-than-fast Fourier transform
#23Spare transforms like this are very interesting, and these seem like some very good performance results. It's worth noting, though, that FFTW ( http://www.fftw.org/ ) is still much faster on the sizes of transforms that many (most?) applications do - less than 2^15 or so entries. Also, as the number of non-zero frequencies climbs, sparse algorithms very quickly get overtaken by good implementations of more standard F…
They actually point out a specific comparison to FFTW in the paper: their "preliminary implementation" is faster than FFTW for n=2^22 and k I don't know how to estimate what values of n would be relevant for today's applications, but n=2^22≈4M doesn't seem like such a big number for images or video (if signal length roughly corresponds to number of pixels). Any thoughts?
> I don't know how to estimate what values of n would be relevant for today's applications, but n=2^22≈4M doesn't seem like such a big number for images or video (if signal length roughly corresponds to number of pixels). Any thoughts?
Transform codecs for video typically don't transform an entire frame at a time, but rather blocks of the frame. This is for three reasons. The first is efficiency - most of these codecs date back to a time when huge transforms (FFT, DCT, etc) were very expensive. Possibly the most important is the local artifacts are less noticable than global artifacts in video, and using blocks is a nice way to bound that. Finally, the point of using a transform is to be able to extract some 'structure' from the data that can be used to encode it in a more efficient way. Small blocks make this easier to do in a perceptually acceptable or transparent way.
There are absolutely applications for large transforms, but video encoding typically isn't one. Incidentally, many modern approaches are based on other transforms, like the discrete wavelet transform, or approximations to transforms like the DCT.
Re: The faster-than-fast Fourier transform
#24Spare transforms like this are very interesting, and these seem like some very good performance results. It's worth noting, though, that FFTW ( http://www.fftw.org/ ) is still much faster on the sizes of transforms that many (most?) applications do - less than 2^15 or so entries. Also, as the number of non-zero frequencies climbs, sparse algorithms very quickly get overtaken by good implementations of more standard F…
If FFTW were invented today, it would stand for Fourier For The Win
Re: The faster-than-fast Fourier transform
#25As usual the article misrepresents video compression. Almost l useful coding tools are spatial and not frequency based; the only famous one (DCT) was replaced with a rough approximation in H.264 and it works just as well. This is because lots of realistic images don't really have meaningful frequency-based content. (imagine sampling every 8 or 16 pixels - would their values be in any way related to each other?)
Don't think of them in terms the full function. You can approximate a strait line by a small part of a long sine wave. http://www.wolframalpha.com/input/?i=Sin%28x%29++from+.01+to...
But, for a real world example look at jpeg.
Next, each 8×8 block of each component (Y, Cb, Cr) is converted to a frequency-domain representation, using a normalized, two-dimensional type-II discrete cosine transform (DCT). http://en.wikipedia.org/wiki/JPEG
Re: The faster-than-fast Fourier transform
#26The talk at SODA is in 1.5 hours, I'm going to attend it. Any other HNers at SODA?
How was the talk?
Re: The faster-than-fast Fourier transform
#27Today's pedantic minute is sponsored by Carl Friedrich Gauss. The FFT algorithm was re discovered in the 60's. Gauss discovered it in the early 19th century while studying the phase of the moon, before Fourier described his transform. He published it in latin, and the text was lost until 1984.
Not to detract from Gauss' remarkable discovery but there is no relation between Gauss' FFT algorithm and the continuous Fourier transform that Fourier discovered. It is also worth mentioning that credit for the discrete Fourier transform goes to Vandermode and pre-dates Gauss' FFT algorithm by about 30 years.
I didn't know about Vandermonde, its always nice to learn something.
I'm no mathematician, and my understanding of the subject is limited. How is the discrete Fourier transform unrelated to its continuous counterpart? Their definitions are extremely similar...
From a semantic point of view, it is nice that all these transform bear the same name, but historically, it is a bit unfair to attribute Fourier analysis to Fourier, who didn't discover it (even though he greatly developed the subject).
I know there's an eponymous law that describes this phenomenon, and it is of course not named after its inventor, but I can't remember its name.
Re: The faster-than-fast Fourier transform
#28Earlier quoted context omitted.
Not to detract from Gauss' remarkable discovery but there is no relation between Gauss' FFT algorithm and the continuous Fourier transform that Fourier discovered. It is also worth mentioning that credit for the discrete Fourier transform goes to Vandermode and pre-dates Gauss' FFT algorithm by about 30 years.
I didn't know about Vandermonde, its always nice to learn something. I'm no mathematician, and my understanding of the subject is limited. How is the discrete Fourier transform unrelated to its continuous counterpart? Their definitions are extremely similar... From a semantic point of view, it is nice that all these transform bear the same name, but historically, it is a bit unfair to attribute Fourier analysis to Fo…
Re: The faster-than-fast Fourier transform
#29Earlier quoted context omitted.
I didn't know about Vandermonde, its always nice to learn something. I'm no mathematician, and my understanding of the subject is limited. How is the discrete Fourier transform unrelated to its continuous counterpart? Their definitions are extremely similar... From a semantic point of view, it is nice that all these transform bear the same name, but historically, it is a bit unfair to attribute Fourier analysis to Fo…
http://en.wikipedia.org/wiki/Stiglers_law_of_eponymy
Thanks :-)
Re: The faster-than-fast Fourier transform
#30For the plain ol' FFT, I've found the "Fastest Fourier in the West": http://www.fftw.org/ to be an excellent library, which implements a whole bunch of different solvers, and picks the appropriate ones to use for your data. Hopefully this new algorithm can be added to their toolbox in the future.
In the paper, they state that they compared their implementation to FFTW and beat it handily.