Fourier transform for dummies
math.stackexchange.com
math.stackexchange.com
Ever since I found Better Explained I have recommended it to anyone wanting to get actual intuition for high school / undergraduate level math concepts.
I found another page that I felt like offers an nice overview of the Fourier transform and various practical uses, without getting into the actual implementation details - http://nautil.us/blog/the-math-trick-behind-mp3s-jpegs-and-h...
The example that worked best for me is with audio sampling. A demonstration of how you can build up a 'wiggly line' to match an audio sample by adding together multiple waves of different frequencies. This then leads into talking about a real world example - mp3 encoding.
Sure, if you just want a "for dummies" understanding, a hand-wavy example like the second highest voted answer suffices. But if you want to learn it properly (prove theorems, etc), you need to know concepts like complex numbers and integration.
By the Stone-Weierstrass theorem (http://en.wikipedia.org/wiki/Stone–Weierstrass_theorem) we know that lots (really, lots!) of sets of functions would work, not just complex exponentials.
The story I tell myself about that is, "complex exponentials are the (unique) eigenfunctions of linear time-invariant systems".
Simply put, this means that if S(.) is a system that has derivatives and integrals, and scaling and shifting in time, then
S(exp(i omega t)) = const * exp(i omega t)
This property is (under some not too restrictive conditions) basically a defining property of the complex exponential. (Basically, notice that d/dt [exp (a t)] = a exp(a t) -- which turns out to have a converse as well.)
Then, because S is linear, a linear combo of complex exponentials (on the input of S) transforms into a weighted combo of the same exponentials on the output.
To me, that's the deeper reason that Fourier analysis is important. Those sines and cosines are mathematically inevitable, right from the moment in high school when you learned d/dx e^x = e^x.
Noted on that SE page (the OP) is a related, but subsidiary property, that the Fourier bases are also the eigenfunctions of the wave equation. But the wave equation is linear, so this follows from the above reasoning.
I imagine, but I don't know, that the usefulness of the Fourier basis for quantum-mechanical analysis also follows from linearity.
Understanding that the square wave (and any other wave) can be represented as a superposition of sine waves at various frequencies seems like a better place to start because it illustrates the most common use case of FTs (alternating between time and frequency domain for a signal).
cos(t) = x
sin(t) = y
But, I agree, its not as intuitive because the extra dimensions get in the way of understanding the basic transform.
The thing that bothers me about the epicycle example in particular is that it's not clear (from the example) what the domain of the function we're trying to approximate is, and what, if any, restrictions need to be placed on the function. For example, is it OK for the function cross itself? Can I represent an arbitrary shape in 2D with this method? What happens if the line has to jump? Is that OK or not? Is it accidental, or on purpose, that the line comes back to meet itself at the end? Why is the function we're representing (in the epicycle example) in 2D but we usually take the Fourier transform of 1D functions? Where did complex numbers come in? What is complex exponentiation? What's an integral?
The square wave example does better. You can just use pure sines or cosines, so you don't have to introduce complex numbers. You don't have the 2D vs. 1D issue. You don't need an integral. So with less folderol, you get to about the same level of understanding as in the given example.
On the other hand, I really like the epicycle example as a machine learning or sparse basis example. That is, explaining that you can fit anything if you have enough degrees of freedom. After the Fourier transform is already understood by other means.
<p>$$z(t) = \int_{-\infty}^{\infty}R(\omega) e^{i\omega t} \mathrm{d}\omega$$</p> -> https://i.imgur.com/fLFlv7f.png
I can do this when I create a page on my site (I also have MathJax installed), but none of the discussion groups I post to supports Latex rendering. I keep thinking this will eventually become universal, but IMHO "eventually" is taking too long.
Anyway: http://www.mathjax.org/ (it's free)
If our ears could hear radio frequencies - like AM1070 - then each station by itself would sound like a dull drone or a tuning fork. It's dull because it's repetitive - it sounds the same this second as it sounded the previous one. To make the drone interesting we multiply it with a person's voice signal (say from a microphone or rolling tape) - then the drone kind of goes wah-wuh-wuh-wah, and this 'modulated' signal is a lot more interesting.
That's basically the Fourier transform - a sum of Speech.Station signals, where Speech is interesting and Station is repetitive.
---
We can play this same game with the speech itself - or music. Think of each note do-re-mi-... as radio stations, and the pressure applied to each key of the piano as the speech. So, music can be represented by a combination of the form KeyPressure.MusicalNote. The KeyPressure sequence can be recorded in a music sheet. The notes themselves are boring (as the kids say in The Sound of Music, the notes don't mean anything), it's the "multiplication and sum" with the KeyPressure sequence that makes music.
Again, note the summation overy x.y terms, where x is interesting and y is repetitive - that's the Fourier transform.
Historical sidelight: The simplest sheet music is Morse code, dah-dit. When telegraph became a booming business there was a shortage of wires to handle the volume of messages. People wanted a way to send more Morse per wire. Alexander Graham Bell had a bright idea - this was a few decades before radio - he took several Morse streams & put each dit-dah-dah-dit-dah sequence onto separate notes (like do-re-mi), and then sent the lot down a single wire. As he played with his system he had the deep insight that if the Morse code was replaced by sheet notation, then he could transmit music down a wire - and that became the telephone!
It was pretty crude, but is was a nice way to see how a piece of music looked in the frequency domain. I kept that mental model in my head all the way through engineering.
You can also take a periodic function and break it into its 'component' sines and cosines. This is called the fourier series.
Fourier transform is essentially similar to the fourier series except you're allowed to have non-integer frequency multiples.
You can see how FT and FS are useful for analyzing all sorts of things that are periodic. MP3s, for example use a similar system to encode music (it's called the discrete cosine transform) and compression is enabled by deleting information that your ear will fill in - but this information is most easily selected and deleted by looking at the MP3 in terms of frequency and amplitude over time.
> Fourier transform is essentially similar to the fourier series except you're allowed to have non-integer frequency multiples.
Not really. Taylor series are "optimal" in a completely different way from Fourier series. Since the "decomposition strategy" used by Fourier series is completely general (there are polynomial equivalents of the Fourier Series) it's worth drawing the distinction.
The Taylor Series gets all of its information from the neighborhood of a single point. Thought experiment: consider the curve e^x. Now set it to 0 everywhere outside of the interval (-e,e) where e is arbitrarily small. Now take the taylor series of the curve at the point x=0. You get back the original curve e^x -- the Taylor Series completely ignores the fact that your curve no longer looks anything like e^x! You can do even worse than that: paste a tiny, almost-linear segment of 1+sin(x) into e^x around the origin. You couldn't tell the difference looking at the curve (they both look like e^x) but the Taylor series would converge to the sin, not to the e^x curve you "transplanted" the patch into. Taylor series are good for answering the question "How does f(x) change if I nudge x a bit?" but they are very bad at answering the question "what polynomial best approximates f(x) over its domain?".
If you want to answer the latter question, you should use linear algebra and change of basis / orthogonal filter banks / whatever you want to call it. This is the trick used by the Fourier Series and the Discrete/Fast Fourier Transform. It works for polynomials too: google "Legendre polynomials" or "Hermite polynomials" for more information on polynomial analogs of the Fourier Series (if you haven't had linear algebra, I highly recommend Axler's book, which will teach you how to use generalized inner products to perform this trick). There's a second type of polynomial approximation called "Lagrange interpolation" which approximates a function using polynomials by evaluating it at certain points rather than by integrating it. Lagrange interpolations are only distantly related to Legendre/Hermite/etc polynomials but both strategies answer the question of "what polynomial best approximates f(x) over its domain?" much better than Taylor series.
Also, if you ever want to learn how MP3/JPG compression actually works, you'll want the DCT, which is another relative of the FFT. If you know the relevant linear algebra, the distinction is trivial (DCT has implied "mirror" symmetry at the endpoints rather than "wrap" symmetry so you don't get ringing if the color changes from one edge of a block to the other). DCT, FFT, Legendre polynomial approximation, Hermite polynomial approximation, etc all use the same simple trick (cue "one weird trick" ad). If you don't know the relevant linear algebra, it's a bunch of black magic. But the relevant math is accessible enough that I highly recommend looking into it. I've already mentioned Axler's book (Linear Algebra Done Right) -- it's accessible to anyone with a semester or two of calculus under their belt and it'll get you to the point of understanding how all of these transforms are basically just rotation matrices for high-dimensional spaces (one dimension for every point you evaluate the function at) within a few chapters.
The key is to understand the distinction between vectors/operators as understood by mathematicians and the blocks of numbers called vectors/matrices by engineers. The latter are like a shadow cast by the former. Learn about the former and you'll see that the DCT, FFT, etc are shadows of the exact same concept as the familiar triplets of real numbers, just cast at a different angle, if that makes sense.
Actually ... take an nth degree polynomial from your favorite orthogonal set. For each of its n+1 zeros, construct by Lagrange interpolation the polynomial which is 1 at that zero and 0 at the others. Then that set of n+1 interpolating polynomials has the same relation to the orthogonal polynomials of degree 0 through n that (periodized) sincs have to sinusoids, i.e. you can decompose an n degree or lower polynomial in either basis, and the two representations are related by something like a Fourier transform.
And notice that time is a component in each of these.
If I was going to teach Fourier concepts, I would have no problem talking about signals initially, at the stage when I wanted the students to acquire an intuitive grasp of the topic before discussing the technical aspects.
But I think that way about most mathematical topics -- I think creating a visual analogue of, as well as some enthusiasm for, a topic is a very desirable first step as we move toward the formal and disciplined part.
But then again I have trained myself to go into new situations devoid of intuition so I don't confuse myself.
This is why string theory is in such a mess -- too much focus on the mathematical, too little on the physical. At the moment, string theory can explain anything, including any number of imaginary universes.
It's worth remembering that Einstein (in a manner of speaking) pictured his theories before turning them into mathematics, and made frequent uses of the gedankenexperiment (thought experiment) approach, in which he would imagine a physical embodiment for an idea to see how it held up.
Obviously in modern times, the mathematical form of a theory is the bottom line and cannot be dismissed. But to have significance in reality it should be partnered with a very clear physical analogue.
Honestly, for me, the sine curve + sine curve + sine curve + ... explanation was perfectly good even on an intuitive level. Perhaps that's because I've spent some of my adolescence in front of a computer doing tons of visualizations and graph plots, and because at the same time I was doing quite a bit of electronics (radio frequency and so on) and audio synthesis. At some point, you just go "yeah, I see it".
Fun anecdote: A square wave is made entirely of odd harmonics (3, 5, 7, ...). There are no even harmonics in it. When you can see why intuitively, you've understood Fourier.