4 ms·

This article has several nice plots, but IMO the wikipedia does a better job describing Fourier transforms than this article. A few things that article alludes

by ptero 10y ago

This article has several nice plots, but IMO the wikipedia does a better job describing Fourier transforms than this article. A few things that article alludes to, but not clearly states is FT ability to convert between time and frequency representation of a wave. Another question worth at least cursory mention: what is so great about sine waves (or complex exponents)? Why are they better than, say, step functions for decomposition of many physical phenomena? Even a couple of quick examples would be helpful (drop a stone into a lake; what shape are the waves? extra credit -- why?). Above may sound harsh, which was not my intent; I just think expanding a little can give a much better view of the algorithm and its applications.

reitanqild 10y ago
Above may sound harsh, which was not my intent; I belive you and the word harsh wouldn't even have crossed my mind if you hadn't mentioned it.
catnaroek 10y ago
> Why are [sine waves] better than, say, step functions (...) Sine and cosine waves whose frequencies are multiples of a fundamental frequency, form an orthonormal basis w.r.t. the inner product given by integrating f(x)ĝ(x)dx over one period of the sine (or cosine) wave whose frequency is the fundamental frequency. In practical signal processing, this means that we can separately consider the contribution of each frequency to the total energy of a signal. Technically, the above only explains Fourier series, but the Fourier transform is just the limit case when the fundamental frequency is made arbitrarily small (re-scaled by a factor of the size of Dirac's delta at 0, of course).
- alok-g 10y ago
  Won't the same apply to square waves also, i.e., they can also form an orthonormal basis?
  - sdenton4 10y ago
    Totally of the cuff: I believe you can recast the Sims in the discrete Fourier transform as integrals of step functions. So it should work. However the width of the steps in the discrete dirtier transform is fixed for each n. So you'll need to be a bit clever to make sure your steps line up right of you want to build up a single infinite basis. And I would be a bit afraid that the need for things to line up would end up losing some needed span... So at least the are done things which need to be checked. The sin and cos basis is very convenient. Even more convenient is the e^(i.n.t) basis...
  - _-__--- 10y ago
    They can[0]; however, this requires some further construction. One major benefit of the sin/cos basis is that each basis function maps uniquely to a dirac delta in frequency space. This allows for power/energy symmetries between time and frequency domain representations of a signal and allows for more tenable frequency filtering, e.g. removing 60/50Hz noise or isolating a particular frequency band. A haar wavelet or modified square wave basis may provide you with a simple orthonormal signal basis, but each wavelet has a frequency representation with infinite support in frequency space. This is (a) untenable and (b) eliminates the possibility of frequency-specific filtering. Wavelet analysis is more useful in specific cases. [0] https://en.wikipedia.org/wiki/Haar_wavelet https://en.wikipedia.org/wiki/Haar_wavelet
    - alok-g 10y ago
      When you use the term "frequency space", you are already thinking in terms of the frequency of sin/cos functions. If you actually think in terms of frequency in a different orthonormal basis, you'll find that the dirac delta characteristic you mention is not specific to sin/cos, thereby invalidating your argument.
  - hchenji 10y ago
    Yes. See Haar Basis on page 4 of http://www.fourierandwavelets.org/FSP_v1.1_2014.pdf http://www.fourierandwavelets.org/FSP_v1.1_2014.pdf
- tomrod 10y ago
  As someone with a strong linalg background, I love this explanation! Thank you!
- joshuamorton 10y ago
  >Sine and cosine waves whose frequencies are multiples of a fundamental frequency, form an orthonormal basis w.r.t. the inner product given by integrating f(x)ĝ(x)dx over one period of the sine This, by the way, was perhaps the most mindblowing thing I learned in my advanced linear algebra course. I had already learned about applied Fourier Transforms and the FFT, but seeing the same tools we had used to prove things about Cartesian bases could be applied to something so unexpected, with such powerful results, was incredible.
  - blt 10y ago
    The "magic" of the Fourier transform and DFT is entirely contained in this proof, IMO. I think a lot of people find the Fourier transform extra-amazing because it is their first encounter with basis change and infinite dimensional vector spaces. The FFT is still magic though :)
- mturmon 10y ago
  About "why sine waves," the mantra I learned is: "Complex exponentials are the eigenfunctions of linear systems." This means that, if you put a complex exponential in, you get the same complex exponential out, scaled by some constant, whose magnitude we call the "frequency response". No other functional form has this property. They are eigenfunctions, so they are orthogonal. We can represent any function in L2 using a weighted sum of them.
  - blt 10y ago
    By L2 you mean the set of square-integrable functions, right?
    - michalskop 10y ago
      Should be, see https://en.wikipedia.org/wiki/Lp_space https://en.wikipedia.org/wiki/Lp_space
    - mturmon 10y ago
      Yes, and by "represent", I mean represent with respect to the L2 norm.
wyager 10y ago
My explanation for why we use complex exponentials in waves analysis, in two common cases: In the first case, when you're solving a differential equation like f(t) = - C^2 * d^2/dt^2 f(t) you have several different ways of representing the entire family of solutions, all valid. Here are some: A*cos(Cx+phi) A*cos(Cx) + B*sin(Cx) A*e^(±iCx) So at least two of these solutions only involve real numbers. However, it turns out from experience that this is actually harder to work with; it's more annoying to keep track of phase or FOIL cross-terms than it is to work with complex numbers. Your equations end up with fewer terms when you use complex exponentials. Then, because we're working with linear systems, you can simply add up your complex solutions in such a way that the complex numbers cancel out and you're left with a real-valued solution that works for physical waves. In the second case, we use complex numbers to keep track of something. Like when you're doing a Fourier transform, you break down a signal into its different frequency components. However, a signal made up of a 500hz sine wave is going to be shaped differently from a signal made of a 500hz cosine wave, so we have to keep track of those separately. Conveniently, e^(ix) = cos(x) + i sin(x), so we use a complex number to represent the presence of a 500hz cosine wave (real part) and a 500hz sine wave (complex part) while keeping our equations simple. That's sort of a practical overview; a deeper understanding can come from learning linear and abstract algebra.

by ptero 10y ago

reitanqild 10y ago

Above may sound harsh, which was not my intent; I belive you and the word harsh wouldn't even have crossed my mind if you hadn't mentioned it.

catnaroek 10y ago

> Why are [sine waves] better than, say, step functions (...) Sine and cosine waves whose frequencies are multiples of a fundamental frequency, form an orthonormal basis w.r.t. the inner product given by integrating f(x)ĝ(x)dx over one period of the sine (or cosine) wave whose frequency is the fundamental frequency. In practical signal processing, this means that we can separately consider the contribution of each frequency to the total energy of a signal. Technically, the above only explains Fourier series, but the Fourier transform is just the limit case when the fundamental frequency is made arbitrarily small (re-scaled by a factor of the size of Dirac's delta at 0, of course).

alok-g 10y ago
Won't the same apply to square waves also, i.e., they can also form an orthonormal basis?
- sdenton4 10y ago
  Totally of the cuff: I believe you can recast the Sims in the discrete Fourier transform as integrals of step functions. So it should work. However the width of the steps in the discrete dirtier transform is fixed for each n. So you'll need to be a bit clever to make sure your steps line up right of you want to build up a single infinite basis. And I would be a bit afraid that the need for things to line up would end up losing some needed span... So at least the are done things which need to be checked. The sin and cos basis is very convenient. Even more convenient is the e^(i.n.t) basis...
- _-__--- 10y ago
  They can[0]; however, this requires some further construction. One major benefit of the sin/cos basis is that each basis function maps uniquely to a dirac delta in frequency space. This allows for power/energy symmetries between time and frequency domain representations of a signal and allows for more tenable frequency filtering, e.g. removing 60/50Hz noise or isolating a particular frequency band. A haar wavelet or modified square wave basis may provide you with a simple orthonormal signal basis, but each wavelet has a frequency representation with infinite support in frequency space. This is (a) untenable and (b) eliminates the possibility of frequency-specific filtering. Wavelet analysis is more useful in specific cases. [0] https://en.wikipedia.org/wiki/Haar_wavelet https://en.wikipedia.org/wiki/Haar_wavelet
  - alok-g 10y ago
    When you use the term "frequency space", you are already thinking in terms of the frequency of sin/cos functions. If you actually think in terms of frequency in a different orthonormal basis, you'll find that the dirac delta characteristic you mention is not specific to sin/cos, thereby invalidating your argument.
- hchenji 10y ago
  Yes. See Haar Basis on page 4 of http://www.fourierandwavelets.org/FSP_v1.1_2014.pdf http://www.fourierandwavelets.org/FSP_v1.1_2014.pdf
tomrod 10y ago
As someone with a strong linalg background, I love this explanation! Thank you!
joshuamorton 10y ago
>Sine and cosine waves whose frequencies are multiples of a fundamental frequency, form an orthonormal basis w.r.t. the inner product given by integrating f(x)ĝ(x)dx over one period of the sine This, by the way, was perhaps the most mindblowing thing I learned in my advanced linear algebra course. I had already learned about applied Fourier Transforms and the FFT, but seeing the same tools we had used to prove things about Cartesian bases could be applied to something so unexpected, with such powerful results, was incredible.
- blt 10y ago
  The "magic" of the Fourier transform and DFT is entirely contained in this proof, IMO. I think a lot of people find the Fourier transform extra-amazing because it is their first encounter with basis change and infinite dimensional vector spaces. The FFT is still magic though :)
mturmon 10y ago
About "why sine waves," the mantra I learned is: "Complex exponentials are the eigenfunctions of linear systems." This means that, if you put a complex exponential in, you get the same complex exponential out, scaled by some constant, whose magnitude we call the "frequency response". No other functional form has this property. They are eigenfunctions, so they are orthogonal. We can represent any function in L2 using a weighted sum of them.
- blt 10y ago
  By L2 you mean the set of square-integrable functions, right?
  - michalskop 10y ago
    Should be, see https://en.wikipedia.org/wiki/Lp_space https://en.wikipedia.org/wiki/Lp_space
  - mturmon 10y ago
    Yes, and by "represent", I mean represent with respect to the L2 norm.

wyager 10y ago

My explanation for why we use complex exponentials in waves analysis, in two common cases: In the first case, when you're solving a differential equation like f(t) = - C^2 * d^2/dt^2 f(t) you have several different ways of representing the entire family of solutions, all valid. Here are some: A*cos(Cx+phi) A*cos(Cx) + B*sin(Cx) A*e^(±iCx) So at least two of these solutions only involve real numbers. However, it turns out from experience that this is actually harder to work with; it's more annoying to keep track of phase or FOIL cross-terms than it is to work with complex numbers. Your equations end up with fewer terms when you use complex exponentials. Then, because we're working with linear systems, you can simply add up your complex solutions in such a way that the complex numbers cancel out and you're left with a real-valued solution that works for physical waves. In the second case, we use complex numbers to keep track of something. Like when you're doing a Fourier transform, you break down a signal into its different frequency components. However, a signal made up of a 500hz sine wave is going to be shaped differently from a signal made of a 500hz cosine wave, so we have to keep track of those separately. Conveniently, e^(ix) = cos(x) + i sin(x), so we use a complex number to represent the presence of a 500hz cosine wave (real part) and a 500hz sine wave (complex part) while keeping our equations simple. That's sort of a practical overview; a deeper understanding can come from learning linear and abstract algebra.