6 ms·

Fourier Transform became trivial to me when I noticed that it's just a basis transform, as you would do with ANY other basis. Except this basis happens to be si

Fourier Transform became trivial to me when I noticed that it's just a basis transform, as you would do with ANY other basis. Except this basis happens to be sine and cos waves of different frequencies. i.e. you view the entire signal in the original domain as a single point in space of dimensionality equal to number of measurements, and then you project it onto the new (fourier) basis. For example, one of the new basis vectors could be sine signal of some frequency k. You find the component of the original signal along this new basis just as you would do for any other basis vector, with a dot product. The only slight complication is that to get the phase information you have to actually dot with a cosine at that frequency as well. The confusing e^ix complex number multiply "hides" the fact that we are actually doing two simultaneous dot products (since e^ix = sinx + icosx): one with the sine and the other with the cos, to get both the frequency and phase. this is the intuition for DFT but for FT you just have infinite-dimensional vector space, done. This is much more intuitive to me than "spinning a signal in circle", which I personally find very to be a very confusing statement. EDIT: granted, basic linear algebra concepts (vectors, basis transform) needed.

eridius 12y ago
The isolated phrase "spinning a signal in a circle" is confusing, but the accompanying visualization of tracking a point on a spinning speaker cone is something that can be visualized. More generally, your explanation may make sense to you, but it makes no sense to a layperson (i.e. me). But the linked short description, along with the speaker cone visualization, does make a reasonable amount of sense. I've also seen a similar description in the past with accompanying animated GIFs illustrating the point, instead of the prose about a spinning speaker cone. I thought the animated GIFs made it even easier to understand. Sadly, I don't remember where I saw that.
- jesuslop 12y ago
  Agreed a layperson could benefit, but karpathy insight is also very nice, it allows to leapfrog from elementary linear methods to a good intuition of the real thing.
  - eridius 12y ago
    Oh sure, I bet karpathy's explanation is great for the people it makes sense to. It just assumes a lot more specialized knowledge on the part of the reader, knowledge that I personally don't have.
    - chestervonwinch 12y ago
      Let me try a (hopefully unspecialized) basis view explanation. I think this is more of an explanation of Fourier Series, but hopefully it gets the idea across: Consider the space around you. Pick some frame of reference with a fixed origin point in space. To specify an object, you must specify the distance along each independent direction (x, y, and z in 3d space) to arrive at the object from the fixed origin. These independent directions are referred to as a basis for the space. Often these independent bases are perpendicular (or orthogonal). For higher dimensional spaces its the same idea. It turns out we can even have infinite dimensional spaces whose bases are functions that can be perpendicular in a certain sense. It also turns out that complex exponentials (waves) are an orthogonal basis for a certain space of functions. This is really cool! It means we can refer to any function in this space using the complex exponential basis functions just like we referred to objects in 3d space using three independent directions. Why is this useful? The magnitude in a particular independent direction in this space tells us about frequency content of that function. So instead of the first coordinate telling you how much x distance there is, it says how much of a certain frequency there is.
      - eridius 12y ago
        That helps, thanks. But while that's an explanation that may make a certain amount of intellectual sense, it still doesn't make any intuitive sense. Perhaps if I'd worked with basis views a lot more, then it would become intuitive, but I haven't. The nice thing about the spinning signal idea is I can visualize the speaker, and it makes some intuitive sense that if I spin it at a given frequency, and the speaker cone's average movement is zero, then the signal has no content at that frequency.
        12y ago
- ggonweb 12y ago
  Is it this https://upload.wikimedia.org/wikipedia/commons/1/1a/Fourier_series_square_wave_circles_animation.gif https://upload.wikimedia.org/wikipedia/commons/1/1a/Fourier_...
  - eridius 12y ago
    I've seen that before, and it's neat, but I don't think that's what I'm remembering.
  - deleted 12y ago
    [deleted]
- AnonJ 12y ago
  I think it's this one, which was also posted on HN: http://nautil.us/blog/the-math-trick-behind-mp3s-jpegs-and-homer-simpsons-face http://nautil.us/blog/the-math-trick-behind-mp3s-jpegs-and-h...
Xcelerate 12y ago
This is the kind of explanation I was looking to post on here, but couldn't quite formulate it right in my head. Yours is very clear. Interestingly, it was actually learning quantum mechanics that made me understand the Fourier Transforms much more easily. You're always projecting the wavefunction into some basis, so the cosines and sines are just one particular basis.
blt 12y ago
I agree, the "magic" part is the proof that the sine and cos signal vectors in the Fourier basis are orthogonal. But it's actually a very simple proof.
cperciva 12y ago
My preferred way of looking at the Fourier Transform is that it is evaluating a polynomial at the roots of unity. This is why it is useful for large-integer arithmetic.
ska 12y ago
This approach is much more clear when you use inner product notation. Another benefit is you can see exactly how it is similar to other basis like (orthonormal) wavelets, and dis-similar to so-called "over-complete" basis (complex wavelets, various frames). It also becomes easier to see what the projections onto basis vectors are doing, how/why energy is "concentrated" under a wavelet transform of natural signals, etc.
GrantS 12y ago
If anyone wants to visualize how a variety of basis transforms (including Fourier/DFT, Eigenvectors/PCA, Haar Wavelets, Random basis, and Identity basis) can be applied to images, I created this a few years ago which seems to have become the #2 google result for "basis transform": http://www.cc.gatech.edu/~phlosoft/transforms/ http://www.cc.gatech.edu/~phlosoft/transforms/ It's a bit dated by being a Java applet, but source code is all there, written in Processing. (I should probably update it now that processing.js is a thing. Years pass quickly.)
Tarrosion 12y ago
Agreed, I've taken classes in linear algebra, analysis, and harmonic analysis...and I can't grok what "spinning a signal around a circle" is or why we would do that, but the change of basis realization was also my lightbulb moment.
conistonwater 12y ago
> Fourier Transform became trivial to me when I noticed that it's just a basis transform I always thought this was the definition of Fourier transform, and all the stuff with integrals was just to express the change of basis in an explicit form. What else would the word "transform" mean? How is it even possible for someone to learn about the Fourier transform without it being very explicitly said that it is a change of basis to a different set of orthogonal functions? Did they just introduce the integral expression for it and hope people would memorize it? I don't understand.
- j2kun 12y ago
  > Did they just introduce the integral expression for it and hope people would memorize it? Unfortunately, yes. The linked article even avoids this language at all costs. And that's just how people work in physics and engineering. They want to talk about spinning functions and all this nonsense instead of just doing some basic linear algebra.
  - conistonwater 12y ago
    That's sad. It reminds me of "maths phobia", which is apparently a thing people can have. Also "maths anxiety".
    - j2kun 12y ago
      I think part of it is also that physicists and engineers are the ones primarily teaching the subject. So it might not be that they can't handle the mathematics, but that they simply prefer to think entirely in intuition land where they can spin functions around without anyone protesting.
  - SamReidHughe2 12y ago
    That's because it's important that people understand the meaning of the Fourier Transform and what it actually calculates. It's not just some random basis you throw in an equation without understanding what you're doing.
javajosh 12y ago
Sure, but the hard thing to accept intuitively, for me, is the existence of an alternative representation of a function, particularly for functions with require intricate, data-heavy descriptions to express. It's kinda crazy that you can combine sinusoids such that they look like an arbitrary function; it's only slightly more crazy that there is a way to calculate what those sinusoids are. My intuition is also violated by the fact that you can go back and forth between these representations losslessly. It would seem to me that some functions, even simple ones like a line, would require a great explosion of information to represent as sinusoids. A function requiring two numbers to describe now requires infinite numbers to describe, in the linear case!
sriku 12y ago
While the "spin it around" explanation is useful at a certain level, this "basis understanding" is useful in a different domain - quantum physics. Position and momentum are two such dual bases, as are energy and time. In other words, time and energy (for example) are perspectives. If you try to narrow a signal from one perspective, it will look spread out from the other perspective.
learnenglish 12y ago
I think you mean e^(ix) = cos(x) + sin(x) i What I find useful about Laplace and Fourier transform is there is that applied to differential equations there produce algebraic equations, so is a very useful tool when you are working in problems that are modelled via differential equations. My introduction for someone totally new to this field is to consider y = cos(x) and y= sin(x) as functions whose second derivative satisfie y'' = -y, and the exponential y = e^(ax) as the solution of y'=ay then you can think of solving this kind of equations trying a solution of the form y=e^(kx) then you realize that the constant k is the solution of a first or second order algebraic equation that you know how to solve. Then if your equation has imaginary solutions you need to know what is the exponential of an imaginary number, exp(ik) = cos(k) + i sin(k), then you say ok but that is not a real function, answer the real part and the imaginary part of that are also solutions. Going this way you find that a complex number z=a+bi is the solution of a differential equation that often constitute a model a physical system. z=a+bi is the solution of the second order equation (z-a)^2+b^2 = 0 and this algebraic equation goes to a differential equation just by replacing z^2 with y'' (second derivative) z with y' (first derivative) and finally you have the solutions y=e^(ax)cos(bx) and y=e^(ax)sin(bx) in which the amplitude of the signal is controlled by the exponential so that if a is negative you have a signal that goes to zero and otherwise a signal that explode.
SpaceManNabs 12y ago
I completely agree with you. Especially after my work with numerical techniques to partial differential equations, I honestly cannot see why Fourier transforms keep getting people confused. Hell, even Laplace transforms trip people up...

eridius 12y ago

The isolated phrase "spinning a signal in a circle" is confusing, but the accompanying visualization of tracking a point on a spinning speaker cone is something that can be visualized. More generally, your explanation may make sense to you, but it makes no sense to a layperson (i.e. me). But the linked short description, along with the speaker cone visualization, does make a reasonable amount of sense. I've also seen a similar description in the past with accompanying animated GIFs illustrating the point, instead of the prose about a spinning speaker cone. I thought the animated GIFs made it even easier to understand. Sadly, I don't remember where I saw that.

jesuslop 12y ago
Agreed a layperson could benefit, but karpathy insight is also very nice, it allows to leapfrog from elementary linear methods to a good intuition of the real thing.
- eridius 12y ago
  Oh sure, I bet karpathy's explanation is great for the people it makes sense to. It just assumes a lot more specialized knowledge on the part of the reader, knowledge that I personally don't have.
  - chestervonwinch 12y ago
    Let me try a (hopefully unspecialized) basis view explanation. I think this is more of an explanation of Fourier Series, but hopefully it gets the idea across: Consider the space around you. Pick some frame of reference with a fixed origin point in space. To specify an object, you must specify the distance along each independent direction (x, y, and z in 3d space) to arrive at the object from the fixed origin. These independent directions are referred to as a basis for the space. Often these independent bases are perpendicular (or orthogonal). For higher dimensional spaces its the same idea. It turns out we can even have infinite dimensional spaces whose bases are functions that can be perpendicular in a certain sense. It also turns out that complex exponentials (waves) are an orthogonal basis for a certain space of functions. This is really cool! It means we can refer to any function in this space using the complex exponential basis functions just like we referred to objects in 3d space using three independent directions. Why is this useful? The magnitude in a particular independent direction in this space tells us about frequency content of that function. So instead of the first coordinate telling you how much x distance there is, it says how much of a certain frequency there is.
    - eridius 12y ago
      That helps, thanks. But while that's an explanation that may make a certain amount of intellectual sense, it still doesn't make any intuitive sense. Perhaps if I'd worked with basis views a lot more, then it would become intuitive, but I haven't. The nice thing about the spinning signal idea is I can visualize the speaker, and it makes some intuitive sense that if I spin it at a given frequency, and the speaker cone's average movement is zero, then the signal has no content at that frequency.
      - 12y ago
ggonweb 12y ago
Is it this https://upload.wikimedia.org/wikipedia/commons/1/1a/Fourier_series_square_wave_circles_animation.gif https://upload.wikimedia.org/wikipedia/commons/1/1a/Fourier_...
- eridius 12y ago
  I've seen that before, and it's neat, but I don't think that's what I'm remembering.
- deleted 12y ago
  [deleted]
AnonJ 12y ago
I think it's this one, which was also posted on HN: http://nautil.us/blog/the-math-trick-behind-mp3s-jpegs-and-homer-simpsons-face http://nautil.us/blog/the-math-trick-behind-mp3s-jpegs-and-h...

Xcelerate 12y ago

This is the kind of explanation I was looking to post on here, but couldn't quite formulate it right in my head. Yours is very clear. Interestingly, it was actually learning quantum mechanics that made me understand the Fourier Transforms much more easily. You're always projecting the wavefunction into some basis, so the cosines and sines are just one particular basis.

blt 12y ago

I agree, the "magic" part is the proof that the sine and cos signal vectors in the Fourier basis are orthogonal. But it's actually a very simple proof.

cperciva 12y ago

My preferred way of looking at the Fourier Transform is that it is evaluating a polynomial at the roots of unity. This is why it is useful for large-integer arithmetic.

ska 12y ago

This approach is much more clear when you use inner product notation. Another benefit is you can see exactly how it is similar to other basis like (orthonormal) wavelets, and dis-similar to so-called "over-complete" basis (complex wavelets, various frames). It also becomes easier to see what the projections onto basis vectors are doing, how/why energy is "concentrated" under a wavelet transform of natural signals, etc.

GrantS 12y ago

If anyone wants to visualize how a variety of basis transforms (including Fourier/DFT, Eigenvectors/PCA, Haar Wavelets, Random basis, and Identity basis) can be applied to images, I created this a few years ago which seems to have become the #2 google result for "basis transform": http://www.cc.gatech.edu/~phlosoft/transforms/ http://www.cc.gatech.edu/~phlosoft/transforms/ It's a bit dated by being a Java applet, but source code is all there, written in Processing. (I should probably update it now that processing.js is a thing. Years pass quickly.)

Tarrosion 12y ago

Agreed, I've taken classes in linear algebra, analysis, and harmonic analysis...and I can't grok what "spinning a signal around a circle" is or why we would do that, but the change of basis realization was also my lightbulb moment.

conistonwater 12y ago

> Fourier Transform became trivial to me when I noticed that it's just a basis transform I always thought this was the definition of Fourier transform, and all the stuff with integrals was just to express the change of basis in an explicit form. What else would the word "transform" mean? How is it even possible for someone to learn about the Fourier transform without it being very explicitly said that it is a change of basis to a different set of orthogonal functions? Did they just introduce the integral expression for it and hope people would memorize it? I don't understand.

j2kun 12y ago
> Did they just introduce the integral expression for it and hope people would memorize it? Unfortunately, yes. The linked article even avoids this language at all costs. And that's just how people work in physics and engineering. They want to talk about spinning functions and all this nonsense instead of just doing some basic linear algebra.
- conistonwater 12y ago
  That's sad. It reminds me of "maths phobia", which is apparently a thing people can have. Also "maths anxiety".
  - j2kun 12y ago
    I think part of it is also that physicists and engineers are the ones primarily teaching the subject. So it might not be that they can't handle the mathematics, but that they simply prefer to think entirely in intuition land where they can spin functions around without anyone protesting.
- SamReidHughe2 12y ago
  That's because it's important that people understand the meaning of the Fourier Transform and what it actually calculates. It's not just some random basis you throw in an equation without understanding what you're doing.

javajosh 12y ago

Sure, but the hard thing to accept intuitively, for me, is the existence of an alternative representation of a function, particularly for functions with require intricate, data-heavy descriptions to express. It's kinda crazy that you can combine sinusoids such that they look like an arbitrary function; it's only slightly more crazy that there is a way to calculate what those sinusoids are. My intuition is also violated by the fact that you can go back and forth between these representations losslessly. It would seem to me that some functions, even simple ones like a line, would require a great explosion of information to represent as sinusoids. A function requiring two numbers to describe now requires infinite numbers to describe, in the linear case!

sriku 12y ago

While the "spin it around" explanation is useful at a certain level, this "basis understanding" is useful in a different domain - quantum physics. Position and momentum are two such dual bases, as are energy and time. In other words, time and energy (for example) are perspectives. If you try to narrow a signal from one perspective, it will look spread out from the other perspective.

learnenglish 12y ago

I think you mean e^(ix) = cos(x) + sin(x) i What I find useful about Laplace and Fourier transform is there is that applied to differential equations there produce algebraic equations, so is a very useful tool when you are working in problems that are modelled via differential equations. My introduction for someone totally new to this field is to consider y = cos(x) and y= sin(x) as functions whose second derivative satisfie y'' = -y, and the exponential y = e^(ax) as the solution of y'=ay then you can think of solving this kind of equations trying a solution of the form y=e^(kx) then you realize that the constant k is the solution of a first or second order algebraic equation that you know how to solve. Then if your equation has imaginary solutions you need to know what is the exponential of an imaginary number, exp(ik) = cos(k) + i sin(k), then you say ok but that is not a real function, answer the real part and the imaginary part of that are also solutions. Going this way you find that a complex number z=a+bi is the solution of a differential equation that often constitute a model a physical system. z=a+bi is the solution of the second order equation (z-a)^2+b^2 = 0 and this algebraic equation goes to a differential equation just by replacing z^2 with y'' (second derivative) z with y' (first derivative) and finally you have the solutions y=e^(ax)cos(bx) and y=e^(ax)sin(bx) in which the amplitude of the signal is controlled by the exponential so that if a is negative you have a signal that goes to zero and otherwise a signal that explode.

SpaceManNabs 12y ago

I completely agree with you. Especially after my work with numerical techniques to partial differential equations, I honestly cannot see why Fourier transforms keep getting people confused. Hell, even Laplace transforms trip people up...