The FFT algorithm was rediscovered 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.
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.
[1] http://www.springerlink.com/content/j30x8k122v828w87
[2] http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1162...
http://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf
As a Gauss fanboy let me just say wow. Especially note that from 1828 to 1965 there a various versions of the FFT presented for special cases but Gauss had the complete version in 1805.
It starts by dividing the spectrum into frequency bins, and assumes that there is usually 0 or 1 non-zero coefficients in each bin. It wasn't clear to me what happens when a large number of non-zero coefficients are clustered together in one bin. Can O(k log n) still be achieved when most frequencies are clustered?
Sadly I haven't had a chance to look into it in any great detail yet, although it's "in the queue" of things to poke at. I thought it worth pointing out in case anyone else might find it useful.
Still, very cool stuff.
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.
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?)
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
Hopefully this new algorithm can be added to their toolbox in the future.
Any other HNers at SODA?
Of course that as such gives you somewhere to hang your patent application if you can afford the patent lawyers fees to protect the monopoly.
