Intuitive explication of Fourier Transformation(altdevblogaday.org)
altdevblogaday.org
Intuitive explication of Fourier Transformation
http://altdevblogaday.org/2011/05/17/understanding-the-fourier-transform/
34 comments
Obviously the author was exaggerating for effect and humor. Rather than characterizing his description as "avoiding" linear algebra, I say the author admirably confronted his confusion head on and developed his own intuition. Even more admirable is that he shared it.
Good points.
To add to this: if you want an intermediate path that'll give a bit more insight than just basic linear algebra, reading a bit about Hilbert spaces might be worthwhile too. Depending which space(s) you choose to work in, it doesn't necessarily have to bog you down in coping with pathological cases. You probably will need to grok things like countability, limits and converge though.
The benefit: you get to pin down exactly what it means to talk about things like 'basis' and in particular 'orthogonal basis' in a meaningful way when it comes to infinite-dimensional spaces of functions like the ones the Fourier transform works on. Turns out you need some extra tools to do this; intuitions based only on experience with finite-dimensional linear algebra will likely have some handwavy gaps. (Not that that necessarily matters :)
About the article though: I really liked it. It wouldn't teach me from scratch how the transform works, but every extra bit of intuition one can get from looking at a concept from a different point of view helps, and this adds some extra physical intuition in a really nice way.
To add to this: if you want an intermediate path that'll give a bit more insight than just basic linear algebra, reading a bit about Hilbert spaces might be worthwhile too. Depending which space(s) you choose to work in, it doesn't necessarily have to bog you down in coping with pathological cases. You probably will need to grok things like countability, limits and converge though.
The benefit: you get to pin down exactly what it means to talk about things like 'basis' and in particular 'orthogonal basis' in a meaningful way when it comes to infinite-dimensional spaces of functions like the ones the Fourier transform works on. Turns out you need some extra tools to do this; intuitions based only on experience with finite-dimensional linear algebra will likely have some handwavy gaps. (Not that that necessarily matters :)
About the article though: I really liked it. It wouldn't teach me from scratch how the transform works, but every extra bit of intuition one can get from looking at a concept from a different point of view helps, and this adds some extra physical intuition in a really nice way.
Linear algebra alone isn't enough, you also need complex geometry for Euler's formula - I can't just look at exp(0+xi) and go "hey, that's cos x+sin x i". And even then, you need to go a little way into linear algebra to encounter basis functions. Finally, you pretty much need someone to assert orthogonality to even consider it.
And if you aren't working with wavefunctions regularly, like physicists and engineers might be, that gets obtuse fast (I'm referring to the use of the FT in econometrics and image processing). Then it's not at all clear that you should even want a sinusoidal basis with integer frequencies.
And if you aren't working with wavefunctions regularly, like physicists and engineers might be, that gets obtuse fast (I'm referring to the use of the FT in econometrics and image processing). Then it's not at all clear that you should even want a sinusoidal basis with integer frequencies.
To illustrate your point, here is a java applet plus source code visually explaining not only the discrete cosine transform but also principal components analysis and Haar wavelets as all being the same exact operation with a different orthogonal basis:
http://www.cc.gatech.edu/~phlosoft/transforms/
http://www.cc.gatech.edu/~phlosoft/transforms/
I agree, this is the best way of looking at the issue. However, this approach requires one to learn a more advanced material first. It’s probably inevitable, but it may be a good idea to start with something more elementary. I’d suggest to start with a loose analogy with Taylor series (calc2).
The quickest "explanation" of the FT I ever heard was in a casual aside from a professor once -- he referred to the Fourier domain as the "reciprocal domain". It took me a while to work out what he meant.
It was just that frequency = 1 / time. In this (barbarically reductive) conception, taking the FT is just a change of variable.
This relationship is one way to "derive" many of the standard Fourier facts.
For example, the scaling property, that if x(t) has transform X(f), then x(at) has transform (1/a) * X(f/a). It also "explains" why time signals concentrated around t=0 tend to have lots of high-frequency content (f = 1/t = 1/0 = infinity), and vice versa.
It also "explains" why the inverse FT formula looks just like the forward FT formula (since if f = 1/t, then t = 1/f). And, for the same reason, most of the duality relationships between the two domains.
All with just arithmetic! You can dispense with linear algebra, not to mention complex arithmetic, groups, or measure theory.
It was just that frequency = 1 / time. In this (barbarically reductive) conception, taking the FT is just a change of variable.
This relationship is one way to "derive" many of the standard Fourier facts.
For example, the scaling property, that if x(t) has transform X(f), then x(at) has transform (1/a) * X(f/a). It also "explains" why time signals concentrated around t=0 tend to have lots of high-frequency content (f = 1/t = 1/0 = infinity), and vice versa.
It also "explains" why the inverse FT formula looks just like the forward FT formula (since if f = 1/t, then t = 1/f). And, for the same reason, most of the duality relationships between the two domains.
All with just arithmetic! You can dispense with linear algebra, not to mention complex arithmetic, groups, or measure theory.
Now generalize. ;-)
http://en.wikipedia.org/wiki/Fourier-Mukai_transform
http://en.wikipedia.org/wiki/Fourier-Mukai_transform
Actually I think he was referring to this: http://en.wikipedia.org/wiki/Dual_basis
[deleted]
Maybe I'm naive, but I personally find it much simpler just to see how you can construct an arbitrary waveform using the summation of a series of sinusoids - and then a Fourier transform is just the inverse operation...
I think the point of the explanation was to provide some intuition as to where the Exp[- 2 pi i k n / N] in the formula comes from. If it's easier to think of that as a sinusoid then your way of thinking about it is better. If it's easier for you to think of that as spinning your signal around like a phasor then the OP's explanation is useful.
I think that rather than explaining what a Fourier transform does the linked page attempts to explain how it works.
I agree with you. I know the Fourier transfom well from a discrete signals class but that explanation didn't make any sense to me. What is the motivation to spin the signal at 3k?
Because that's the frequency component you want to measure. Repeat at all the other frequencies you're interested in to get the whole spectrum.
To really understand the discrete fourier transform properly you need to understand the mathematical concept of a group. Fortunately, you only need to understand one particular group G, namely the integers mod n. Once one thinks of the input to the Discrete Fourier Transform (DFT) as a function on G (i.e. the input to the function is an element of G and the output is a complex number), then it is possible to frame the DFT in terms of a map between functions on G to functions on the dual of G (using something called Pontryagin duality). The thing is, functions on the dual of G multiply pointwise whereas functions on G itself multiply like polynomials mod x^n - 1.
Therefore to multiply polynomials, one thinks of them as functions on G, uses the DFT to take you to functions on the dual of G, multiplies pointwise, then does an inverse transform to get you back to functions on G again. I'm skimming over lots of details and oversimplifying a bit, but what I just described is the process of using a convolution to multiply polynomials.
The really great thing is if n is a power of 2. Then you have this cool Cooley-Tukey algorithm called the Fast Fourier Transform to do the DFT (and IFFT) really fast (in time O(n log n) instead of O(n^2)). It works by recognising that computing an FFT is precisely the same thing as evaluating a polynomial at the n-th roots of unity. This can be done by repeatedly breaking the problem into halves and recognising that the same pattern of roots of unity occurs in the first half as in the second. By factoring that out, you can (recursively) save yourself half the work.
Again, oversimplified, but that's the nub of it.
Therefore to multiply polynomials, one thinks of them as functions on G, uses the DFT to take you to functions on the dual of G, multiplies pointwise, then does an inverse transform to get you back to functions on G again. I'm skimming over lots of details and oversimplifying a bit, but what I just described is the process of using a convolution to multiply polynomials.
The really great thing is if n is a power of 2. Then you have this cool Cooley-Tukey algorithm called the Fast Fourier Transform to do the DFT (and IFFT) really fast (in time O(n log n) instead of O(n^2)). It works by recognising that computing an FFT is precisely the same thing as evaluating a polynomial at the n-th roots of unity. This can be done by repeatedly breaking the problem into halves and recognising that the same pattern of roots of unity occurs in the first half as in the second. By factoring that out, you can (recursively) save yourself half the work.
Again, oversimplified, but that's the nub of it.
The article, and quite a few posts here, describe the way they understand the Fourier Transform as the way to understand the Fourier Transform. For it to be intuitive depends on who is trying to understand it. Getting that out of the way, this is how I find the Fourier Transform intuitive (using pseudo-code instead of math notation to make it a bit verbose and emphasize the steps):
If the input signal sig(t) has no relation to the frequency of the sinusoid, then integrating mult(t) over infinity will give zero.
If the signal has a component with the required frequency, it will kind of resonate with the sinusoid and give a non-zero value. The value then depends on the magnitude of the signal and to how much it "resonates" with the sinusoid.
When you do this for a range of different frequencies freq, but using the same signal sig(t), you can plot how much the signal sig(t) resonates with all frequencies, and that plot is the plot of the Fourier Transform.
fourier_trasform(signal sig(t), frequency freq):
let sinu(t) = sinusoid with frequency freq
let mult(t) = sig(t) * sinu(t)
value = integral of mult(t) from -infinity to infinity
If the input signal sig(t) has no relation to the frequency of the sinusoid, then integrating mult(t) over infinity will give zero.
If the signal has a component with the required frequency, it will kind of resonate with the sinusoid and give a non-zero value. The value then depends on the magnitude of the signal and to how much it "resonates" with the sinusoid.
When you do this for a range of different frequencies freq, but using the same signal sig(t), you can plot how much the signal sig(t) resonates with all frequencies, and that plot is the plot of the Fourier Transform.
By the by, one of the things that always tripped me up about the DFT was understanding that for signals that are already sums of sinusoids, the discrete sum gives exactly the same answer as the integral would. Remember the trapezoidal rule for integration? It turns out it's exact for trigonometric polynomials sampled at or above the Nyquist frequency.
Now, to find a life sciences journal to publish that in...
Now, to find a life sciences journal to publish that in...
I think these concepts became clear to me when I learned about the complex plane, Euler's formula, and demodulation of an FM signal.
Particularly enlightening was the demodulation of a frequency modulated sine wave when the tuner was imperfectly matched to the carrier frequency. Looking at it on an oscilloscope was similar to watching an old TV with the Vertical Hold improperly set.
That made me start thinking in terms of a signal (sine wave) that was a cycle rather than a sinusoidal shape. Seeing that you can graph the amplitude and phase of any signal on the complex plane and that the frequency was the change in phase from one moment to the next was the aha! moment.
Then if you think about sampling and how if you sample a sinusoid exactly at its peaks how that would graph as a constant point on the complex plane, but if you sampled at any other mismatched frequently, the point would rotate and change amplitude with respect to either axis. The further away from the actual frequency you'd go the the points would look more random, and they'd average out to zero with fewer samples.
This would be a fun animation or java applet to make; I'm sure someone has done it.
Particularly enlightening was the demodulation of a frequency modulated sine wave when the tuner was imperfectly matched to the carrier frequency. Looking at it on an oscilloscope was similar to watching an old TV with the Vertical Hold improperly set.
That made me start thinking in terms of a signal (sine wave) that was a cycle rather than a sinusoidal shape. Seeing that you can graph the amplitude and phase of any signal on the complex plane and that the frequency was the change in phase from one moment to the next was the aha! moment.
Then if you think about sampling and how if you sample a sinusoid exactly at its peaks how that would graph as a constant point on the complex plane, but if you sampled at any other mismatched frequently, the point would rotate and change amplitude with respect to either axis. The further away from the actual frequency you'd go the the points would look more random, and they'd average out to zero with fewer samples.
This would be a fun animation or java applet to make; I'm sure someone has done it.
That was a great explanation, particularly the summary at the end with the color-coded words corresponding to terms in the formula.
I came to the comments expecting to see nods of approbation at how cool this explanation was (I stopped taking math at about Calc 3, so no linear algebra for me) but instead I see people geeking out saying things like "to really understand you need to grasp the complex plane, and groups and DPTs and so forth."
Well, just so you know, for me the OP's intutitive explanation was enough.
I came to the comments expecting to see nods of approbation at how cool this explanation was (I stopped taking math at about Calc 3, so no linear algebra for me) but instead I see people geeking out saying things like "to really understand you need to grasp the complex plane, and groups and DPTs and so forth."
Well, just so you know, for me the OP's intutitive explanation was enough.
That's possibly the most intuitive explanation for what the maths is actually doing that I've ever come across.
A great resource to read about Fourier transformation and Wavelets
http://users.rowan.edu/~polikar/WAVELETS/WTpart1.html
http://users.rowan.edu/~polikar/WAVELETS/WTpart1.html
I visualize it as projecting the function (as a vector) onto spirals of different twisting rates.
Only 3 dimensions required, which is nice.
Only 3 dimensions required, which is nice.
Yeah, thinking of the exp() part as a spirals in three dimensional space (the imaginary plane + the time/space line) finally helped me to understand what's really going on with the Fourier transform.
I like the explanation, but there's no reason to skip over the complex exponents and Euler's formula like that. They're not really that hard to understand intuitively: think of all multiplication as a continuous process. Then f = e^x is simply the function that transforms the multiplicative identity (1) into ln(x).
Substitute "-1" into the left side of that equation, and see that no real value of x will suffice. This is related to the fact that the imaginary constant (i) wasn't discovered, it was simply declared as an unknown quantity that squares to -1.
The real magical part is that i still works in more complicated situations: multiplying any real number by e^(ix) as x increases gradually transforms it into an imaginary number, and then into its own negative, behaving like a counter-clockwise rotation when visualized in the complex plane.
Substitute "-1" into the left side of that equation, and see that no real value of x will suffice. This is related to the fact that the imaginary constant (i) wasn't discovered, it was simply declared as an unknown quantity that squares to -1.
The real magical part is that i still works in more complicated situations: multiplying any real number by e^(ix) as x increases gradually transforms it into an imaginary number, and then into its own negative, behaving like a counter-clockwise rotation when visualized in the complex plane.
I love the idea that a man can sit down behind his desk, think for days, weeks, months, years or even decades and come up with something which is so abstract and beautiful explaining natural phenomenons with simple mathematical formulas.
It takes some serious entrepreneurial skills and mindset to embark on a problem which is seemingly impossible, and never giving up until the solution has been derived.
Inspirational, to say the least!
It takes some serious entrepreneurial skills and mindset to embark on a problem which is seemingly impossible, and never giving up until the solution has been derived.
Inspirational, to say the least!
> It takes some serious entrepreneurial skills and mindset
> to embark on a problem which is seemingly impossible, and
> never giving up until the solution has been derived.
Entrepreneurial, like agile, has become a synonym for "generically good".
In the context of PHB-speak I guess.
Lets utilize our synergy to create some entrepreneurial verticals!
Lets utilize our synergy to create some entrepreneurial verticals!
Only here.
Same means, potentially same ends, but entirely different intents.
well, it requires some independence
I wish all maths books would have their formulas illustrated like this: http://altdevblogaday.org/wp-content/uploads/2011/05/Derived...
That is beautiful.
That is beautiful.
Yes. Yes! Thanks for pointing that out - I hadn't noticed how brilliant the use of color is. I just understood ...
And that's the hallmark of good teaching.
And that's the hallmark of good teaching.
Then you just need to understand that the sines and cosines are a complete basis. So think about the sines and cosines for a while until you can say "yeah, they're orthogonal, and I can believe they're a complete basis for the kind of functions under consideration." Then to promote this from "I can believe" to "obviously," for the discrete FT (the orthogonality and) counting/dimensionality arguments suffice, and for the continuous FT you can look at Gaussians, say "obviously Gaussians are a complete basis for the kinds of functions under consideration" and then do the easy integrals to show that any Gaussian can be expressed as a linear combination of sines and cosines.
(This assumes you're interested in transforming reasonably smooth things like wavefunctions in chemistry, as opposed to trying to see how far you can push Fourier analysis into the netherworld of bizarre jagged twisted functions shown to exist by invoking the Axiom of Choice. If you want to do that, feel free to take a course from Terence Tao studying theorems whose prerequisites involve concepts like "countable.")