Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

One of my favorite questions to Math Candidates, that are potential employees:

In Fourier transform, what is being transformed to what? What is wrong with how it is that it needs to be transformed?

I am amused at the variety of answers this produces.



OK, I'll take a stab:

The Fourier transform is basically taking a signal, and correlating it against sinusoids of increasing frequency and unity amplitude. Each point along the x axis of the new signal is the result of the correlation for that frequency (x being frequency in this coordinate system).

The transform is used when you want to analyse the frequency content of a signal - useful when trying to determine frequency filters or bandwidth needs to transmit the signal, for example.

Edit: (because I hit send too soon) I've always found the purely mathematical explanation to be easier to understand than explanations involving rotating circles or whatever. As a bonus, you can directly derive the formula from the description, and things like Fourier series are a logical extension.


What's awesome is that there are so many valid ways to interpret the math. My favorite way to understand fourier transforms is the linear algebra approach. You start with the fact that the best approximation for a vector in some subspace is the projection of that vector onto the subspace. This makes total sense visually. https://upload.wikimedia.org/wikipedia/commons/thumb/9/98/Pr... So if you want to approximate something, it's really nice if you can make it look like a vector and just do a projection.

After that you just do what mathematicians do, you generalize. It turns out that if you define addition of functions in a logical way, and if you define dot product (or inner norm) of 2 functions in a somewhat clever way, you get a vector space that you can do projections with.

The next thing you do once you have a vector space is figure out a natural set of basis vectors. For normal 2d space, we pick <1,0> and <0,1>. It turns out that you get really nice properties if the vectors have a length of one and if they are at right angles to each other. The concept of right angles can be generalized by saying their inner product is zero. At that point there's no more 90 degree angle, but the vectors are still independent in some useful sense.

It turns out that if you define "multiplication" as multiplying 2 functions together and looking at the area under them, then basically all the sin and cos waves are orthogonal. If you multiply by the right factor, you can some up with a sin wave where the area under the curve is one. So now you have a whole bunch of "vectors" that are orthogonal and have a "length" of one. So now all you have to do is measure the component of your target function along each "axis" of your set of basis vectors and you have an approximation. That projection is pretty easy. In 2d world if you wanted to "project" <5,6> onto <1,0> you'd just drop the 6 and get <5,0>. "projecting" x*x along sin(x) is conceptually pretty similar. It's just defined in terms of the inner norm from before.

One thing I've left out because they aren't intuitively obvious to me. Sin and Cos waves form a basis for continuous functions on an interval. That means that if you can use "all" the sin and cos waves in your approximation, you'll get the original function back. If they weren't a basis, then your approximation could only get so good.

So that's my POV. Every time I think of fourier transforms, I think of a little flashlight shining above a 3d vector that's casting a shadow onto a 2d plane.


Another really useful/practical thing from looking at things this (inner product) way.

You have a function expressed as a weighted sum of basis vectors in your space: e.g.

f = Sigma_n x_n e_n = Sigma_n <f,e_n> e_n

(for simplicity lets say it is self dual)

then take any approximation g = Sigma_n <g,e_n> e_n

now consider the residual:

f - g = Sigma_n w_n e_n , clearly, for some set of weights {w_n}

So this demonstrates that when you produce an error in approximation, that error itself is composed of the same building blocks (I know, this is obvious, but a lot of people miss it!).

This explains why in signal processing the Gibbs ringing effect looks sinusoidal, and why errors in approximation in Haar look "blocky", etc.

Aside: also, this generalizes nicely to Frame theory where you give up orthonormality (and hence energy conservation) but gain other things.


Isn't that essentially a glossary question? But I'm sure the inventive answers are priceless.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: