Fourier Transforms – The Math Trick Behind MP3s, JPEGs, and Homer Simpson’s Face

These rotating circles that are referenced by the article will forever remain a cautionary tale for me: http://blog.matthen.com/post/42112703604/the-smooth-motion-o...

In pre-Copernican astronomy, where the Earth was considered the center of the cosmos, the erratic orbits of the other planets relative to us were explained away as epicycles within perfect circles. Later, closer examination of the orbits required modeling the orbits as epicycles within epicycles, exactly as depicted in the rotating circles above. In the end, it turned out that there aren't epicycles in the orbits, they were just creating a Fourier transform to explain the orbital paths. We now know that you can create a Fourier transform to generate any arbitrary path.

I sometimes wonder how many of our modern physics models, such as the standard model, differential geometry, and M-theory, are just highly sophisticated versions of the Fourier transform.

They don't? At University of Sydney every engineering degree does 2 years of maths and that includes Fourier Series.

Some math geek nitpicks to a generally good post:

The things we are calling countable and uncountable are actually dimensionalities of vector spaces...

The dimensionality of L^2(R) is still countable. Proof: f(k,j,x) = e^{2 pi i k x}, x in [j,j+1], k and j both integers forms a basis. So does H_n(x) exp(-x^2/2), for H_n the Hermite polynomials.

The Fourier transform merely does not map L^2(R) -> l^2(Z) in this case - it maps L^2(R) -> L^2(R).

That is, there is always a reproducible curve that has zero L2 difference from an arbitrary input curve.

This isn't what density means. Density means that for any epsilon, there is a reproducible curve with L2 distance Linf norm: d(f,g)=max(f(x)-g(x)) over the interval (a,b)

By most standard definitions, this is only true almost everywhere. A typical definition is ||f(x)||_{\infty}= Lim_{p -> infty} ||f(x)||_p, and this allows two functions to differ on a set of measure zero.

As an example, consider f(x)=1 and g(x)={0 on rational numbers, 1 on irrational numbers}. These two functions are equal in any L^p space, and are hence equal in L^infty as well.

There is also an extremely important property that would be worth an article of it's own. Namely the fact that pointwise multiplication of 2 fourier transformed functions is the same as convolution of the functions themselves.

What does this mean in practice? Let's take a simple gaussian blur for images. A single output pixel is formed by overlapping the gaussian kernel on top of the image, multiplying then pointwise, then summing the result. Repeat for every pixels. What you can also do is take FFT of the gaussian kernel and multiply it with the FFT of the image and inverse transform and you will get the same result as actually calculating it for every point separately. Is this faster than doing it point by point? Depends on the blur radius.

You can do awesome things with this blazingly fast. As an example a simple water wave simulation can be made by simply taking a fourier transform, multiplying it with the dispersion relation of the water waves and then doing an inverse transformation. http://www.youtube.com/watch?v=MTUztfD2pg0 Just like what is done here. Normally this convolution would take O(N^2) amount of operations where N is amount of vertices but with FFT it's O(N log N).

FFT is for convolution what quicksort is for sorting. Imagine how limited would you be if all your sorts would take O(N^2) time. The examples I gave are quite limited in scope, going trough all the applications of convolution would take textbooks. It's probably one of the most important concepts in electrical engineering.

Oh yeah, convolution is just like cross correlation except in another case the function is reversed. So you can imagine the applications in data mining etc.

All in all Fourier Transform, and related ones, is an extremely huge and massively important concept, it's hard to overstate it's usefulness.

Personally I can say that I've used filter design tools to make a really smooth accelerometer data processing function. It does not jump around like a raw signal does nor does it lag a lot just like the standard exponential smoothing does.

Don't know off the top of my head. I suspect it does have countable dimension but I don't know how to prove it.

The space of continuous functions with the sup norm is actually a much smaller space than the space of L^\infty - the former is not even dense in the latter.

I suspect actual functions on R with the max norm probably is uncountable, but that's also a very weird space. The overwhelming majority of functions in there are unmeasurable.