News for hackers. Stuff that matters.
Re:Visually stunning math concepts which are easy to explain by zokier on Monday April 07, 2014 @11:44AM (#7547147)
I agree. I understand time and frequency domains reasonably well, but I still do not have a clue how Fourier transformation gets me from one to the another. How do the elements in the animation correspond to the terms in eg this equation http://www.texpaste.com/n/v6sjue00 (which is the Wikipedia definition for discrete Fourier transformation)? I don't even understand what the equation itself is supposed to represent, last time I checked a sum produced a single number, how does that represent a function in frequency domain? I guess the subscript k has some significance, but the animation does not help a single bit here
Re:Visually stunning math concepts which are easy to explain by 0x09 on Monday April 07, 2014 @01:32PM (#7547946)
k is the output index (the "bin" in the frequency domain), or the notch in the rotated space in that graphic. Every output frequency coefficient contains a full sum of the input function, hence a direct translation of that formula is O(n^2) -- which is why the FFT, with O(nlogn) complexity is so important.

The graphic doesn't really help show how the analysis itself happens, it just presents the result, which is a series of waves that add up to f. The actual process of obtaining a frequency coefficient from a time-domain function is easy to describe: multiply the function by a (co)sine wave with a particular frequency and sum together the result. But it's not very intuitive why that works until you consider that one period of a sine wave sums to zero. By multiplying the sine with the function, you perturb the shape of the sine with just the amount of energy that the function contains at that given frequency. So that instead of summing to zero, the sum measures "how much" of that particular wave is present. That's Fourier analysis.

Fourier synthesis is more easily visualized (I think anyway). Simply multiply a sine wave at each frequency by the corresponding coefficient derived above, and sum those weighted waveforms together elementwise to recover your function.

Re:Visually stunning math concepts which are easy to explain by zokier on Tuesday April 08, 2014 @05:55AM (#7552406)
> But it's not very intuitive why that works until you consider that one period of a sine wave sums to zero. By multiplying the sine with the function, you perturb the shape of the sine with just the amount of energy that the function contains at that given frequency. So that instead of summing to zero, the sum measures "how much" of that particular wave is present. That's Fourier analysis

Thank you. This really helped.

Based on that explanation, wouldn't the formula be more like: http://www.texpaste.com/n/nphm1fgp ? I suppose there is some further magic which allows for phase differences or something.

Re:Visually stunning math concepts which are easy to explain by 0x09 on Tuesday April 08, 2014 @07:29PM (#7556723)
Right, you need both sine and cosine parts, hence e^ix, in order to fully describe the function. Unless the function is completely odd (or even), in which case the transform really is equivalent to `x[n] * sin(2pik*x/N)` (or cos). To see why imagine analyzing a function W that is just a plain cosine wave (any frequency and amplitude). If we only use the sine part of the Fourier transform, F(W) is indistinguishable from F(-W). In fact both are zero everywhere.

Transforms that use only sines or cosines (like the DCT) provide a complete basis by increasing in frequency by only a half cycle (pi) rather than by integer cycles (2pi). Essentially trading half a transform of sines and half a transform of cosines for one transform of half-cosines (or sines).