[ColinWright]

The Fourier Transform can also be thought of as part of Linear Algebra, because it's actually funding a representation of a given function in the basis consisting of sin and cos functions (or complex exponentials).

See, the collection of non-pathological functions is a vector space. We add elements by adding the functions pointwise, we multiply by a constant in the obvious way, and the other requirements can be checked. Functions form a vector space.

And vector spaces have bases. One basis for the vector space of functions is the collection of sin and cos functions. Thus we can see that finding the Fourier Transform is just finding how much of each basis vector we need to make the function.

And as we know, the amount of basis vector u needed in the representation of a vector v is v.u, the dot product.

Thinking of it this way starts to make connections between all sorts of ideas.

Added in edit: I see the same sort of point made by dropdownmenu in http://news.ycombinator.com/item?id=4862228

[sdsantos]

Yup, that's how I usually picture it, change the values to a collection of sin and cos functions.

When I started explaining it to some computer science students, it helped by giving a particular example of its usefulness:

Sound is composed of waves so, when you want to send a music to a friend it's all a bunch of values like [0, 1, 2, 1, 0, -1 , -2, -1, 0, ...]. If you know they're going to look like waves (sinusoidal functions) why not just send your friend how much they look like sin or cos? The values back there were just a 2sin(x) so why not just send them the value [2]?

You could save a lot of bandwidth. You just need to "correlate" sounds with a bunch of sin or cos functions everybody agrees on :)

Bonus: you can add the phase values, 2 sin(x + phase), to get the beats just right.

[JadeNB]

> Bonus: you can add the phase values, 2 sin(x + phase), to get the beats just right.

Fortunately, you don't need to do so; if the complex number z = A + iB has magnitude r and argument theta, then Acos(t) + Bsin(t) is the same as r*cos(t - theta). That is, combining cosines and sines of the same frequency already accounts for the phase shift.

[JadeNB]

> And vector spaces have bases. One basis for the vector space of functions is the collection of sin and cos functions. Thus we can see that finding the Fourier Transform is just finding how much of each basis vector we need to make the function.

You have indicated quite explicitly that you're being informal (by using non-technical terms like 'non-pathological functions'), but I think it's worth making the small observation here that sine and cosine functions do not form a basis (implicitly: "a Hamel basis") for, say, the space of continuous functions on R/Z in the usual sense of linear algebra, since not every function can be written as a finite linear combination of them.

Rather, they are a topological basis, in the sense that every function can be written as an infinite linear combination of them. Why is it worth making this point, which probably seemed too obvious to say? The reason is that, unlike finite sums, which are unambiguous algebraic constructs, infinite sums require topology to compute; and being a topological basis in, say, the L^2 topology is quite different to being a topological basis in, say, the topology of pointwise convergence. The study of the different kinds of summability of Fourier series is the subject of some very, very deep work.

[ColinWright]

All true - the explanation should be littered with "here be dragons ..." - but for the sake of grasping the concepts without drowning in detail, I thought it was worth leaving out such tricky (but important!) Issues.

But you're right, there is interesting and deep material here.

[Patient0]

This is a great explanation.

The only thing that I still can't get my head around or visualize is how it is that we know that the set of all cos and sin functions is sufficient to span this set of "non-pathological" functions.

So assuming some vector v is reachable by a linear combination of vectors u1,u2,u3... we know that each component should be v.u1, v.u2 etc. But how do you know that v is in fact "reachable" by some combination of vectors in the basis u?

That is, suppose I describe some (infinite) set of a functions. How do I determine the set of functions that it spans? Is there an intuitive way to picture why the set of sin and cos functions forms a suitable basis?

[ColinWright]

This was Fourier's big theorem, that every periodic, non-pathological function is "simply" the sum of phase-shifted sine waves of all necessary frequencies. You can remove the "periodic" if you allow infinitely many frequencies, and so on. The phase-shifting is taken care of by having a sine and a cosine at the same frequency, but (possibly) different amplitudes.

So start with a periodic wave and look at how much sin(x) is in it. Do this by integrating:

    Integral from 0 to 2.pi of f(x)*sin(x) dx

That's a dot product of your function f(x) with the sine wave, and that tells you how much of the first frequency you need. Subtract off the result, and then go again with sin(2x). You find the residuals get less and less. More, for something nice like a square wave or triangular wave the coefficients you get form a predictable sequence.

Interesting note:

    integral sin(k.x)*sin(m.x)

is 0 if k != m, and 1 otherwise, so the basis elements have dot-product 0, and hence are thought of as being at right angles. They also have "length" 1, since the dot-product with themselves is 1. So they are an ortho-normal basis.

So the question is: what functions can be reached by adding and subtracting multiples of sine (and cosine) functions of different frequencies? In Linear Algebra terms, what is the space of functions spanned by these basis functions?

That's harder, but it turns out to be "everything non-pathological".

http://en.wikipedia.org/wiki/Fourier_series#Hilbert_space_in...

http://en.wikipedia.org/wiki/Hilbert_space#Fourier_analysis

Edited for typos

[Patient0]

ah thanks for answering the other questions I hadn't gotten around to asking (the reason why it's an orthonormal basis).

I think I need to go home and have a play with this now!

[JadeNB]

For an orthonormal set, one also gets another answer to your question: how can you see how much such a set spans?

Theorem: If S is an orthonormal (or even orthogonal) set in a Hilbert space V (here, L^2 functions on R/Z), then put S^\perp = {v in V : v is orthogonal to every s in S}. Then the span of S is (S^\perp)^\perp. (The containment of the span in the double-orthocomplement is formal; the other direction requires a supplemental theorem on the geometry of Hilbert spaces.)

With this in mind, we see that S is a topological basis (spans everything) when S^\perp = 0; so, to show that the sine and cosine functions span, it suffices to show that nothing (non-0) is orthogonal to all of them. This still requires computation, but at least it's easier to imagine doing this than somehow finding a Fourier series for any L^2 function.

[VLM]

"That is, suppose I describe some (infinite) set of a functions.... Is there an intuitive way to picture why the set of sin and cos functions forms a suitable basis?"

There are infinite expansions of trig functions to solve the finite vs infinite apparent mismatch, so don't worry about that.

An intuitive way to look at it, is on a 2-d graph there's no spot on the graph that can't be hit by a point of a triangle aka trig function collection, so it doesn't particularly matter how you pick any one spot, a triangle can always hit that one spot because it can hit all spots.

Comp sci analogy would be something like x=x+1 starting at x=0 will hit all the positive integers eventually...

[ColinWright]

That doesn't really work, because you have to be able to hit them all simultaneously, and in fact, you can't. The theorem says that for any given epsilon you can choose enough to ensure that you are within epsilon everywhere except in a very small section of the real line, and you can make the parts where it's not within epsilon very small.

The problem with your comment is that yes, for any given point you can get as close as you like, but the hard part is getting close nearly everywhere all at once. More, you then have to show that there's some sort of convergence, and that where you are close now is a superset of where you are close when you demand to be closer.

It's not straight forward.

[mnl]

http://en.wikipedia.org/wiki/Riesz%E2%80%93Fischer_theorem