Understanding The Fourier Transform

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).<p>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.<p>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.<p>And as we know, the amount of basis vector u needed in the representation of a vector v is v.u, the dot product.<p>Thinking of it this way starts to make connections between all sorts of ideas.<p><i>Added in edit:</i> I see the same sort of point made by dropdownmenu in <a href="http://news.ycombinator.com/item?id=4862228" rel="nofollow">http://news.ycombinator.com/item?id=4862228</a>

I really liked where he color coded the equation and the sentence describing how it worked. I've seen tables in the past explaining what each variable represented, but this was much clearer.<p><a href="http://altdevblogaday.com/wp-content/uploads/2011/05/DerivedDFT.png" rel="nofollow">http://altdevblogaday.com/wp-content/uploads/2011/05/Derived...</a>

This is an interesting way to visualize it, but I think the only way to really grok the Fourier transform is to use it in several different applications, and understand its role in each.<p>A particularly helpful tangent is to play with convolution and see the many different applications that is useful for (did you know that the shadow cast by an object is its cross section convolved with the cross section of the light source?). Once you really <i>get</i> convolution, and really <i>get</i> its relationship to the Fourier transform, you will be well along the path to enlightenment.

You can also think of the Fourier Transform as a projection (dot product) of a signal onto the space of all sinusoids. That's the explanation that made everything click for me.

If someone (like me) is having trouble visualizing, <a href="http://dave.whipp.name/tutorial/fourier.html" rel="nofollow">http://dave.whipp.name/tutorial/fourier.html</a>

You might be interested in the discussion from one of the previous submissions of this:<p><a href="http://news.ycombinator.com/item?id=2555562" rel="nofollow">http://news.ycombinator.com/item?id=2555562</a><p>Here are some other items about the Fourier transform:<p><a href="http://www.hnsearch.com/search#request/all&#38;q=title%3Afourier" rel="nofollow">http://www.hnsearch.com/search#request/all&#38;q=title%3Afou...</a>

You can also think about the Fourier Transform in terms of its physical properties.<p>For example, the Fourier transform is behind quantum uncertainty (dp.dx&#62;h). Think of it this way: the inverse Fourier transform of a frequency impulse (zero extent) is a sine wave of infinite duration. Truncate the infinite sine wave and its spectrum ceases being an impulse, broadening into the shape of the windowing function used to truncate the sine wave. That is, an attempt to constrain/define time leads to a broadening in frequency, and vice versa. The uncertainty principle naturally arises from using the Fourier Transform in an environment where "you can't have infinities".<p>This is true of any two variables which are related by a Fourier Transform. Yes, position and momentum are related by a Fourier transform (as are energy and time).<p>The thinking also works for the other extreme: if you consider how a time impulse (zero extent) related to its Fourier transform, a flat spectrum of infinite extent on the frequency axis.

My preferred way to think about it is in linear algebra terms: your signal of length n is an n-dimensional vector. Now you just need to change the coordinate system into fourier basis, which is made up of vectors of length n who's entries are sin/cos waves of different frequencies. The way you change basis in linear alebra is by doing a dot product with the basis vectors you want to transform to, and it's no different here... it's just a projection of your single point into fourier basis and that's all the formula says.<p>The fancy e^i stuff is just for mathematical beauty and compactness and should be avoided when explaining the fourier transform, imo. There's absolutely no need for it as far as the idea goes, just do the sins and coses separately.

If you want to solve his original problem, detecting treble and bass energy in an audio signal, you might want to read up on the Goertzel algorithm. <a href="http://en.wikipedia.org/wiki/Goertzel_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Goertzel_algorithm</a><p>For limited numbers of bands it will use less battery power and be faster.

This is a nice way to see how the DFT is computed, however I find the view of the FT as a change of basis as even more important - generalizes easily to other bases and and one can understand easily wavelets and their advantages. Basically, the sinusoids form a basis of the vector space of functions (every 'non-pathological' function can be written as a possibly infinite sum of them) and the numbers computed by the FT are coefficients for the respective basis vectors - the magnitude of these coefficients is interpreted as the strength of the corresponding wave in the original signal.<p>Another way to see the FT is as the basis where the convolution operators are diagonal - this is used in image processing, where computing the FFT of a filter + entry-wise multiplication can be much faster than running the convolution at each pixel of the input image.

This is a pretty good intro to DFTs. I was excited to see that others were also motivated by the connection to music and math! I looked into this quite in linear algebra in college and found Benson[1] and Smith[2] to be really thorough and interesting resources on the topic. Hope they help others!<p>1. <a href="http://homepages.abdn.ac.uk/mth192/pages/html/maths-music.html" rel="nofollow">http://homepages.abdn.ac.uk/mth192/pages/html/maths-music.ht...</a> (free pdf)<p>2. <a href="https://ccrma.stanford.edu/~jos/mdft/" rel="nofollow">https://ccrma.stanford.edu/~jos/mdft/</a> (skip down to applications and the digital audio number systems for a preview)

Here is an attempt at an easy-going, matrix-oriented discussion of the FFT, together with quite a bit of motivation:<p><a href="http://home.gregfjohnson.com/fft" rel="nofollow">http://home.gregfjohnson.com/fft</a><p>Here is a really terse "just the essence" ruby implementation of the FFT:<p><a href="http://home.gregfjohnson.com/fftruby" rel="nofollow">http://home.gregfjohnson.com/fftruby</a>

When I first came across Fourier transforms I just thought of it as a bunch of sine and cosine waves destructively/constructively interfering. Could be because we derived FT in class starting by matching sine/cosines to intersect various points.

I got an idea how and why dft works from prof.Wilf(RIP) <a href="http://www.math.upenn.edu/~wilf/AlgoComp.pdf" rel="nofollow">http://www.math.upenn.edu/~wilf/AlgoComp.pdf</a> see from page 50 on. He approaches it from the algebraical side

I found this amazing lecture on youtube.<p><a href="http://www.youtube.com/watch?v=M0Sa8fLOajA" rel="nofollow">http://www.youtube.com/watch?v=M0Sa8fLOajA</a><p>(Gilbert Strang - my first time watching him teach. Such a great paced lecturer)

That's so conceptually simple I hate myself for not getting it before.

I would like to see more of these articles cover the phase portion.