29 ms·

Understanding The Fourier Transform

272 points by mannjani 14y ago

ColinWright 14y ago
You might be interested in the discussion from one of the previous submissions of this: http://news.ycombinator.com/item?id=2555562 http://news.ycombinator.com/item?id=2555562 Here are some other items about the Fourier transform: http://www.hnsearch.com/search#request/all&q=title%3Afourier http://www.hnsearch.com/search#request/all&q=title%3Afou...
dropdownmenu 14y ago
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.
- flatline 14y ago
  It is both the least squares approximation using periodic functions of this sort (i.e. the projection you mentioned), and an interpolant - a very nice combination of properties.
- NickPollard 14y ago
  That's a really great way of thinking about it, actually - particularly if you're used to vector mathematics.
- noahl 14y ago
  I like this way of thinking about it, but I think it is not quite accurate for discrete Fourier Transforms. In this case, we're not projecting onto the space of all sinusoids, only the space of sinusoids whose period is a multiple of (1/N). We could probably prove (if we wanted to try) that those form a basis for the vector space of N-long complex vectors, so using any more sinusoids would be redundant. However, I believe the continuous Fourier Transform works exactly like that.
  - dropdownmenu 14y ago
    Very true, and if you want to be more specific my definition only works for finite duration continuous time signals with finite second moment. I use this definition as it also works well for understanding other transforms such as the Laplace transform.
- revelation 14y ago
  As is explained, you don't even need to project. What you do is a change of basis, which is to say no information is lost.
frozenport 14y ago
I would like to see more of these articles cover the phase portion.
- alecst 14y ago
  What do you mean?
  - frozenport 14y ago
    The imaginary part of the transform.
    - nphrk 14y ago
      The article uses the magnitude of the coefficients, which is computed using both the real and the imaginary part.
      - dbaupp 14y ago
        The phase portion isn't actually just the imaginary part, it's just the piece of information lost when one goes from real+imag -> magnitude, i.e. it's the argument of the complex number.
- jjoonathan 14y ago
  Perhaps this was left as an exercise for the reader? It seems to follow quite closely from the same intuition: after you have averaged the points on the imaginary plane you get a point that you can can represent as (r,theta). Theta is the phase portion. It's just the direction of the constructively interfering peak.
bmease 14y ago
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. http://altdevblogaday.com/wp-content/uploads/2011/05/DerivedDFT.png http://altdevblogaday.com/wp-content/uploads/2011/05/Derived...
- erjiang 14y ago
  I nearly got the light blue and green confused, and I have normal color vision. I think there are reasons to prefer tables, or perhaps something animated or interactive would work as well. (e.g. mouseover a term to get its description.)
  - pbhjpbhj 14y ago
    >I nearly got the light blue and green confused, and I have normal color vision. // Define normal. I have some difficulty differentiating blues and greens sometimes but I found those shades to be quite distinct even on a low quality screen. Perhaps your colour differentiation is worse than you think? It could be down to monitor settings though, for example. There's an Ishihara test here - http://colorvisiontesting.com/ishihara.htm http://colorvisiontesting.com/ishihara.htm FWIW but I'd imagine you'd need to see an optician to do it correctly.
mistercow 14y ago
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. 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 get convolution, and really get its relationship to the Fourier transform, you will be well along the path to enlightenment.
pbhjpbhj 14y ago
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.
olh 14y ago
That's so conceptually simple I hate myself for not getting it before.
nphrk 14y ago
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. 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.
ColinWright 14y ago
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 http://news.ycombinator.com/item?id=4862228
- sdsantos 14y ago
  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 14y ago
    > 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.
- 14y ago
smonte 14y ago
If someone (like me) is having trouble visualizing, http://dave.whipp.name/tutorial/fourier.html http://dave.whipp.name/tutorial/fourier.html
sidupadhyay 14y ago
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! 1. http://homepages.abdn.ac.uk/mth192/pages/html/maths-music.html http://homepages.abdn.ac.uk/mth192/pages/html/maths-music.ht... (free pdf) 2. https://ccrma.stanford.edu/~jos/mdft/ https://ccrma.stanford.edu/~jos/mdft/ (skip down to applications and the digital audio number systems for a preview)
karpathy 14y ago
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. 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.
- shmageggy 14y ago
  If, however, one wanted a similarly intuitive explanation of the e^i part of the story, I recommend these two articles in order. They explain the hand wavy part about complex numbers and rotation: http://betterexplained.com/articles/a-visual-intuitive-guide-to-imaginary-numbers/ http://betterexplained.com/articles/a-visual-intuitive-guide... http://betterexplained.com/articles/intuitive-understanding-of-eulers-formula/ http://betterexplained.com/articles/intuitive-understanding-...
femto 14y ago
You can also think about the Fourier Transform in terms of its physical properties. For example, the Fourier transform is behind quantum uncertainty (dp.dx>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". 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). 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.
- jjoonathan 14y ago
  http://www.youtube.com/watch?v=Znby3t3AS5s http://www.youtube.com/watch?v=Znby3t3AS5s ♫♫♫ Uncertainty is not so odd as long as we're aware position and momentum are a Fourier transform pair So anything that tightens our precision on the one means certainty about the other value gets undone ♫♫♫ Still, I'm not sure I approve of your suggestion to use this physical property of the universe as a basis for intuition. The reasons why quantum mechanics "works" are far, far more difficult to understand, internalize, and accept than the concepts behind the DFT which only really requires an understanding of first-semester linear algebra. In other words, I expect that the set of people who understand QM at this level but do not understand the DFT is nearly empty. If you actually meant to go the other way (use the properties of the FT/DFT to gain an understanding of QM) then I completely agree with everything you said, of course.
- VLM 14y ago
  "That is, an attempt to constrain/define time leads to a broadening in frequency, and vice versa." That is also a really well phrased one line point of commonality to talk to a telecom / RF / EE type person about communications bandwidth theory. If you just wedge in signal to noise ratio / bit error rate, and look at what you phrase "time definition" and "frequency broadening" in the right way, then you pretty much have Shannons famous paper. The FT shows up all over the place in science and anywhere you find it, you can analogize it into a totally different field of study. One "design pattern" hundreds of "implementations".
jws 14y ago
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. http://en.wikipedia.org/wiki/Goertzel_algorithm http://en.wikipedia.org/wiki/Goertzel_algorithm For limited numbers of bands it will use less battery power and be faster.
gregfjohnson 14y ago
Here is an attempt at an easy-going, matrix-oriented discussion of the FFT, together with quite a bit of motivation: http://home.gregfjohnson.com/fft http://home.gregfjohnson.com/fft Here is a really terse "just the essence" ruby implementation of the FFT: http://home.gregfjohnson.com/fftruby http://home.gregfjohnson.com/fftruby
yread 14y ago
I got an idea how and why dft works from prof.Wilf(RIP) http://www.math.upenn.edu/~wilf/AlgoComp.pdf http://www.math.upenn.edu/~wilf/AlgoComp.pdf see from page 50 on. He approaches it from the algebraical side
minikomi 14y ago
I found this amazing lecture on youtube. http://www.youtube.com/watch?v=M0Sa8fLOajA http://www.youtube.com/watch?v=M0Sa8fLOajA (Gilbert Strang - my first time watching him teach. Such a great paced lecturer)

272 points by mannjani 14y ago

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

dropdownmenu 14y ago

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.

flatline 14y ago
It is both the least squares approximation using periodic functions of this sort (i.e. the projection you mentioned), and an interpolant - a very nice combination of properties.
NickPollard 14y ago
That's a really great way of thinking about it, actually - particularly if you're used to vector mathematics.
noahl 14y ago
I like this way of thinking about it, but I think it is not quite accurate for discrete Fourier Transforms. In this case, we're not projecting onto the space of all sinusoids, only the space of sinusoids whose period is a multiple of (1/N). We could probably prove (if we wanted to try) that those form a basis for the vector space of N-long complex vectors, so using any more sinusoids would be redundant. However, I believe the continuous Fourier Transform works exactly like that.
- dropdownmenu 14y ago
  Very true, and if you want to be more specific my definition only works for finite duration continuous time signals with finite second moment. I use this definition as it also works well for understanding other transforms such as the Laplace transform.
revelation 14y ago
As is explained, you don't even need to project. What you do is a change of basis, which is to say no information is lost.

frozenport 14y ago

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

alecst 14y ago
What do you mean?
- frozenport 14y ago
  The imaginary part of the transform.
  - nphrk 14y ago
    The article uses the magnitude of the coefficients, which is computed using both the real and the imaginary part.
    - dbaupp 14y ago
      The phase portion isn't actually just the imaginary part, it's just the piece of information lost when one goes from real+imag -> magnitude, i.e. it's the argument of the complex number.
jjoonathan 14y ago
Perhaps this was left as an exercise for the reader? It seems to follow quite closely from the same intuition: after you have averaged the points on the imaginary plane you get a point that you can can represent as (r,theta). Theta is the phase portion. It's just the direction of the constructively interfering peak.

bmease 14y ago

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. http://altdevblogaday.com/wp-content/uploads/2011/05/DerivedDFT.png http://altdevblogaday.com/wp-content/uploads/2011/05/Derived...

erjiang 14y ago
I nearly got the light blue and green confused, and I have normal color vision. I think there are reasons to prefer tables, or perhaps something animated or interactive would work as well. (e.g. mouseover a term to get its description.)
- pbhjpbhj 14y ago
  >I nearly got the light blue and green confused, and I have normal color vision. // Define normal. I have some difficulty differentiating blues and greens sometimes but I found those shades to be quite distinct even on a low quality screen. Perhaps your colour differentiation is worse than you think? It could be down to monitor settings though, for example. There's an Ishihara test here - http://colorvisiontesting.com/ishihara.htm http://colorvisiontesting.com/ishihara.htm FWIW but I'd imagine you'd need to see an optician to do it correctly.

mistercow 14y ago

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. 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 get convolution, and really get its relationship to the Fourier transform, you will be well along the path to enlightenment.

pbhjpbhj 14y ago

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.

olh 14y ago

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

nphrk 14y ago

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. 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.

ColinWright 14y ago

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 http://news.ycombinator.com/item?id=4862228

sdsantos 14y ago
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 14y ago
  > 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.
14y ago

smonte 14y ago

If someone (like me) is having trouble visualizing, http://dave.whipp.name/tutorial/fourier.html http://dave.whipp.name/tutorial/fourier.html

sidupadhyay 14y ago

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! 1. http://homepages.abdn.ac.uk/mth192/pages/html/maths-music.html http://homepages.abdn.ac.uk/mth192/pages/html/maths-music.ht... (free pdf) 2. https://ccrma.stanford.edu/~jos/mdft/ https://ccrma.stanford.edu/~jos/mdft/ (skip down to applications and the digital audio number systems for a preview)

karpathy 14y ago

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. 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.

shmageggy 14y ago
If, however, one wanted a similarly intuitive explanation of the e^i part of the story, I recommend these two articles in order. They explain the hand wavy part about complex numbers and rotation: http://betterexplained.com/articles/a-visual-intuitive-guide-to-imaginary-numbers/ http://betterexplained.com/articles/a-visual-intuitive-guide... http://betterexplained.com/articles/intuitive-understanding-of-eulers-formula/ http://betterexplained.com/articles/intuitive-understanding-...

femto 14y ago

You can also think about the Fourier Transform in terms of its physical properties. For example, the Fourier transform is behind quantum uncertainty (dp.dx>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". 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). 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.

jjoonathan 14y ago
http://www.youtube.com/watch?v=Znby3t3AS5s http://www.youtube.com/watch?v=Znby3t3AS5s ♫♫♫ Uncertainty is not so odd as long as we're aware position and momentum are a Fourier transform pair So anything that tightens our precision on the one means certainty about the other value gets undone ♫♫♫ Still, I'm not sure I approve of your suggestion to use this physical property of the universe as a basis for intuition. The reasons why quantum mechanics "works" are far, far more difficult to understand, internalize, and accept than the concepts behind the DFT which only really requires an understanding of first-semester linear algebra. In other words, I expect that the set of people who understand QM at this level but do not understand the DFT is nearly empty. If you actually meant to go the other way (use the properties of the FT/DFT to gain an understanding of QM) then I completely agree with everything you said, of course.
VLM 14y ago
"That is, an attempt to constrain/define time leads to a broadening in frequency, and vice versa." That is also a really well phrased one line point of commonality to talk to a telecom / RF / EE type person about communications bandwidth theory. If you just wedge in signal to noise ratio / bit error rate, and look at what you phrase "time definition" and "frequency broadening" in the right way, then you pretty much have Shannons famous paper. The FT shows up all over the place in science and anywhere you find it, you can analogize it into a totally different field of study. One "design pattern" hundreds of "implementations".

jws 14y ago

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. http://en.wikipedia.org/wiki/Goertzel_algorithm http://en.wikipedia.org/wiki/Goertzel_algorithm For limited numbers of bands it will use less battery power and be faster.

gregfjohnson 14y ago

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

yread 14y ago

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

minikomi 14y ago

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