62 ms·

Demystifying Fourier analysis

279 points by dsego 4y ago

Phenomenit 4y ago
I get the math and the explanations and all that but what I don't get is how do you express a complex sound signal as a function of f? Is it a long array with t and the amplitude?
- sfpotter 4y ago
  Yes.
- sizzzzlerz 4y ago
  In reality, you can't. Since the fourier transform was designed for a continuous signal, it needs some modifications to tailor it to work in a digital world where, instead of a continuous signal, you periodically sample the waveform at regular intervals and use the discrete fourier transform (DFT) or its more efficient little brother, the fast fourier transform (FFT). Both these work off N samples of the waveform at a time.
- dsego 4y ago
  Afaik, in digital sound recordings it's basically an array of sampled amplitudes. And you need to know the sampling rate in advance, eg 44100 samples in a second. This is I think called PCM https://en.wikipedia.org/wiki/Pulse-code_modulation https://en.wikipedia.org/wiki/Pulse-code_modulation
wankle 4y ago
I did sound analysis in the submarine service and always appreciated how the FFT worked though I lacked/lack the math background to fully understand it. The article was great, got through the first part, bookmarked for later.
euroderf 4y ago
It's not for nothing that at college, the course in Fourier Series & Boundary Value Problems was better known as Mystery Math. There was a single key insight that made the entire course suddenly clear as a bell, and if you were lucky, that insight came _before_ the final exam.
- jqgatsby 4y ago
  so, uh, you gonna tell us the insight?
  - msla 4y ago
    Maybe that it's "just" a change of basis, onto a basis made of orthogonal periodic functions.
    - franknstein 4y ago
      Change of bases being done with orthogonal projection derived from defining scalar product of two functions via finite integral of product of two functions: f dot g = integral f(x)g(x)dx over some interval.
abstrakraft 4y ago
There are a couple of incorrect assertions near the beginning that should be addressed: 1. "That is, sound waves are not made out of sines as real-word phenomena." Sinusoids are the solutions to the harmonic oscillator differential equation (\ddot{x} = -w^2 x). The harmonic oscillator is an excellent model, or a component of excellent models, for many natural phenomena, including vibrating strings and columns of air, pressure waves in fluids, the list goes on. The utility of sinusoids is not due simply to their convenient mathematical properties, it's because many natural signals are sparse in the frequency domain, precisely because sinusoids do describe real world phenomena. 2. "A piston on a crankshaft produces "pure" sinusoidal up-and-down motion when operating at constant angular velocity." Uh, no. The motion of a piston is approximately sinusoidal as you decrease the radius of the crank, but in no case is it a "pure" sinusoid.
- abstrakraft 4y ago
  Another way to phrase my response to #1 above is that sinusoids are the natural modes of many systems. That is, you put a sinusoid in, and you get a sinusoid of the same frequency out. It may change in amplitude and/or phase, but it still has the same fundamental shape. This is again because these systems act like harmonic oscillators or systems of harmonic oscillators. So why harmonic oscillators? The same analysis shows up any time you have a restoring force proportional to, and in the opposite direction of, the displacement. This shows up in springy things (recall the old mechanical engineer's adage: everything's a spring until it breaks), and fields of all sorts (electric, gravitational, magnetic, pressure).
dinobones 4y ago
Really great explanation, but one thing is missing that plagues every other explanation of Fourier analysis: signals are not infinite. The time window you use for analysis matters just as much as the number of frequency bins, but everyone always ignores the time window for some reason.
- dsego 4y ago
  Is there something missing in the two sections near the end about the sinc function and limited time intervals? https://dsego.github.io/demystifying-fourier/#sinc-function-and-spectral-resolution https://dsego.github.io/demystifying-fourier/#sinc-function-...
kreelman 4y ago
Great that you've tried to learn by teaching this. I'm going to read it in depth later on. Thanks and well done so far (based on the bits I've read).
johndoe0815 4y ago
Nice! I used this website by Jack Schaedler as an intro in my signal processing course, also highly recommended: https://jackschaedler.github.io/circles-sines-signals/index.html https://jackschaedler.github.io/circles-sines-signals/index....
- marmetio 4y ago
  Nice. I used All Signal Processing to get an intuitive feel through visualization. There's a website, but the videos are more easily accessible through YouTube. Still worth checking out for the table of contents and quizzes. https://youtube.com/user/allsignalprocessing https://youtube.com/user/allsignalprocessing
raxxorraxor 4y ago
I only really understood it while looking at imaging. How the base frequencies overlap to form an image and how the phase information is much more important for signal reconstruction than the amplitude. While images have an additional dimension it still helped me to really figure out what was going on. Since it is so well documented I recommend looking at DCT that is employed in JPG. The principle is the same, just the frequency disection works a bit different.
deleted 4y ago
[deleted]
kevlened 4y ago
The 2-minute brute-force explanation of Fourier transforms in a recent Veritasium video was my "aha!" moment. https://www.youtube.com/watch?v=nmgFG7PUHfo&t=464s https://www.youtube.com/watch?v=nmgFG7PUHfo&t=464s
- photochemsyn 4y ago
  For an additional video exposition, I also like Eugene Khutoryansky's "Fourier Transform, Fourier Series, and frequency spectrum" https://www.youtube.com/watch?v=r18Gi8lSkfM https://www.youtube.com/watch?v=r18Gi8lSkfM In particular, the visualization of the addition of sine waves of different frequencies in three dimensions is pretty spectacular. It's similar to Mathologer's "Epicycles, complex Fourier series and Homer Simpson's orbit": https://www.youtube.com/watch?v=qS4H6PEcCCA https://www.youtube.com/watch?v=qS4H6PEcCCA
- SnooSux 4y ago
  I have a Bachelors and Master's in Electrical Engineering and do some signal and image processing as part of my job. I've been working with FFTs since undergrad and I thought a good understanding of what it does and how it works. But that Veritasium video helped me put all the pieces together in a way that made things click. The famous 3Blue1Brown video is also very strong and maybe explains why complex numbers are used better. Of course both videos leave stuff out in the interest of time but they should both be part of a signal processing curriculum.
- SJSque 4y ago
  I can also highly recommend 3Blue1Brown's treatment of the topic: https://www.youtube.com/watch?v=spUNpyF58BY https://www.youtube.com/watch?v=spUNpyF58BY (...which I see now is cited in the video that you link to!)
- djmips 4y ago
  You might also enjoy this Engineering Guy video playlist on how a mechanical harmonic analyzer works. https://youtube.com/playlist?list=PL0INsTTU1k2UYO9Mck-i5HNqGNW5AeEwq https://youtube.com/playlist?list=PL0INsTTU1k2UYO9Mck-i5HNqG...
femto 4y ago
A funky thing is that you can replace the 'N' sin/cos functions used in Fourier analysis with any set of 'N' orthogonal functions (aka basis functions). In this context, a Fourier transform is just a bunch of correlations of the function to be analysed with each basis function. Two functions are orthogonal if their correlation is zero. PCM is "Fourier analysis" with impulse functions in place of sin/cos. CDMA replaces sin/cos with a set of (almost) orthogonal functions with a wide bandwidth. From an information perspective, orthogonality of the basis functions means each component/coefficient is giving you new information about the signal. In real life you can only compute a finite number of coefficients, meaning you must have a finite amount of information, so there is an inherent uncertainty in the relationship between the signal being analysed and the output of Fourier analysis. (Physical quantities that have an uncertainty principle, such as position and momentum, are related to each other by a Fourier transform.)
- sfpotter 4y ago
  Need to be careful about the difference between the discrete Fourier transform and the Fourier series here. It sounds like you're talking about the discrete Fourier transform, but making some statements which apply to Fourier series. For the DFT, your N orthogonal "functions" are really just orthogonal vectors in C^N. In this case, if they're normalized appropriately, they certainly provide an orthonormal basis for C^N. But this is just linear algebra. The same is true of other orthogonal matrices which are discretized versions of systems of orthogonal functions. Like the discrete Wavelet transform, for example. On the other hand, with the Fourier series, to represent any 2pi-periodic square integrable function, you need an expansion over an infinite sequence of orthogonal basis functions. In this case, the complex exponentials with integer frequency. But you can't just take N arbitrary orthogonal functions and expect them to be meaningful when it comes to analyzing 2pi-periodic square integrable functions. Generating a system of orthogonal functions which truly spans L^2 for some set is more involved than what you do in linear algebra. You can read about Sturm-Liouville eigenvalue problems for one way. If you want a system of orthogonal polynomials, it's possible to use Gram-Schmidt, but notice that this doesn't make any sense for a periodic interval (and simply running Gram-Schmidt doesn't actually prove that the resulting sequence of polynomials actually spans L^2...). Also, note that the construction of the continuous wavelets is very different.
geokon 4y ago
I thought this was really well done without any misleading oversimplifications. I do think the author missed the central trick of the Fourier Transform though. He's right in pointing out the sounds aren't a bunch of sine waves (typically), but the trick is that Fourier frequencies are cleverly chosen so they're all orthogonal (ie. you can't represent any of them in terms of the other). The complex number form turns out to give you one of the simplest representations of this set of frequencies. I was wondering if anyone has a more rigorous explanation of the in-between frequencies part. I tried to follow this explanation from a great concise but rigorous book hosted online https://ccrma.stanford.edu/~jos//dft/Frequencies_Cracks.html https://ccrma.stanford.edu/~jos//dft/Frequencies_Cracks.html https://ccrma.stanford.edu/~jos//proj/Bessel_Functions.html https://ccrma.stanford.edu/~jos//proj/Bessel_Functions.html but unfortunately in this section it seems to gloss over the proof (or maybe I don't get it). It just sorta tells you "Bessel functions"! Which isn't very satisfying - especially when you have no idea what a Bessel function is.. I have a problem where my signal (which has a bit of noise) has maybe one (or several) strong non-multiple frequency (I likely know their approximately values a-priori). There may be other frequencies but they shouldn't be close in the frequency space. What I expect to see is a similar spectrogram with this same ringing. But what I'd like to do next is work backwards and estimate the original frequency and most importantly the phase! Everyone talks about the frequency ringing but everyone skips explaining what happens to the phase. And since I haven't been able to find a nice proof of the ringing, I haven't been able to work it out for myself either Does anyone happen to have any good pointers for me? Thank you :)
- HelloNurse 4y ago
  Citing from that page > In other words, $ J_k(\beta)$ is the amplitude of the $ k$ th harmonic in the Fourier-series expansion of the periodic signal $ x_m(t)$ . Or from the parent page about FM > It is well known that sinusoidal frequency-modulation of a sinusoid creates sinusoidal components that are uniformly spaced in frequency by multiples of the modulation frequency, with amplitudes given by the Bessel functions of the first kind [15]. As a special case, frequency-modulation of a sinusoid by itself generates a harmonic spectrum in which the $ k$ th harmonic amplitude is proportional to $ J_k(\beta)$ , where $ k$ is the order of the Bessel function and $ \beta $ is the FM index. In other words, Bessel functions come up in Fourier transforms of frequency modulation signals, because integrals. The calculations have been figured out centuries ago. Regarding phase and arbitrary frequencies, it's easier to understand in the discrete time case: a vector of N complex numbers (time domain samples) goes in, it's multiplied by a matrix, and a vector of N complex numbers (Fourier coefficients) comes out. Regardless of the input signal, such a transform can be inverted (up to rounding errors and the like) by multiplication with the inverse of the forward matrix: the difference between signals of different frequencies is that if periods are a whole fraction of N samples the projections fall on one Fourier coefficient instead of spreading around all of them. Aligning the signal's period with the window length M allows reproducing the whole infinite duration signal from a N coefficient slice because all slices are identical.
TuringTest 4y ago
To expand the insight, you may see this video about Wavelets which relates them to the Fourier transform. It explains wavelets as an intermediate point between pure waves (all time, no frequency representation) and the Fourier transform (all frequencies, no time representation), with wavelets having part of both. https://www.youtube.com/watch?v=jnxqHcObNK4 https://www.youtube.com/watch?v=jnxqHcObNK4
- lupire 4y ago
  "time" is present in both frequency and position. The difference is how time is sampled. Fourier Transform maps between global frequency space sampling and (repeating wave for all time) and local positional/point space sampling (perfect impulse). Wavelets map to an intermediate space,as you say, with smeared points/impulses and damped waves.
  - dsego 4y ago
    In this aspect, are wavelets similar to how stft is done with a hann window or the like?

279 points by dsego 4y ago

I get the math and the explanations and all that but what I don't get is how do you express a complex sound signal as a function of f? Is it a long array with t and the amplitude?

sfpotter 4y ago
Yes.
sizzzzlerz 4y ago
In reality, you can't. Since the fourier transform was designed for a continuous signal, it needs some modifications to tailor it to work in a digital world where, instead of a continuous signal, you periodically sample the waveform at regular intervals and use the discrete fourier transform (DFT) or its more efficient little brother, the fast fourier transform (FFT). Both these work off N samples of the waveform at a time.
dsego 4y ago
Afaik, in digital sound recordings it's basically an array of sampled amplitudes. And you need to know the sampling rate in advance, eg 44100 samples in a second. This is I think called PCM https://en.wikipedia.org/wiki/Pulse-code_modulation https://en.wikipedia.org/wiki/Pulse-code_modulation

wankle 4y ago

I did sound analysis in the submarine service and always appreciated how the FFT worked though I lacked/lack the math background to fully understand it. The article was great, got through the first part, bookmarked for later.

euroderf 4y ago

It's not for nothing that at college, the course in Fourier Series & Boundary Value Problems was better known as Mystery Math. There was a single key insight that made the entire course suddenly clear as a bell, and if you were lucky, that insight came _before_ the final exam.

jqgatsby 4y ago
so, uh, you gonna tell us the insight?
- msla 4y ago
  Maybe that it's "just" a change of basis, onto a basis made of orthogonal periodic functions.
  - franknstein 4y ago
    Change of bases being done with orthogonal projection derived from defining scalar product of two functions via finite integral of product of two functions: f dot g = integral f(x)g(x)dx over some interval.

abstrakraft 4y ago

There are a couple of incorrect assertions near the beginning that should be addressed: 1. "That is, sound waves are not made out of sines as real-word phenomena." Sinusoids are the solutions to the harmonic oscillator differential equation (\ddot{x} = -w^2 x). The harmonic oscillator is an excellent model, or a component of excellent models, for many natural phenomena, including vibrating strings and columns of air, pressure waves in fluids, the list goes on. The utility of sinusoids is not due simply to their convenient mathematical properties, it's because many natural signals are sparse in the frequency domain, precisely because sinusoids do describe real world phenomena. 2. "A piston on a crankshaft produces "pure" sinusoidal up-and-down motion when operating at constant angular velocity." Uh, no. The motion of a piston is approximately sinusoidal as you decrease the radius of the crank, but in no case is it a "pure" sinusoid.

abstrakraft 4y ago
Another way to phrase my response to #1 above is that sinusoids are the natural modes of many systems. That is, you put a sinusoid in, and you get a sinusoid of the same frequency out. It may change in amplitude and/or phase, but it still has the same fundamental shape. This is again because these systems act like harmonic oscillators or systems of harmonic oscillators. So why harmonic oscillators? The same analysis shows up any time you have a restoring force proportional to, and in the opposite direction of, the displacement. This shows up in springy things (recall the old mechanical engineer's adage: everything's a spring until it breaks), and fields of all sorts (electric, gravitational, magnetic, pressure).

dinobones 4y ago

Really great explanation, but one thing is missing that plagues every other explanation of Fourier analysis: signals are not infinite. The time window you use for analysis matters just as much as the number of frequency bins, but everyone always ignores the time window for some reason.

dsego 4y ago
Is there something missing in the two sections near the end about the sinc function and limited time intervals? https://dsego.github.io/demystifying-fourier/#sinc-function-and-spectral-resolution https://dsego.github.io/demystifying-fourier/#sinc-function-...

kreelman 4y ago

Great that you've tried to learn by teaching this. I'm going to read it in depth later on. Thanks and well done so far (based on the bits I've read).

johndoe0815 4y ago

Nice! I used this website by Jack Schaedler as an intro in my signal processing course, also highly recommended: https://jackschaedler.github.io/circles-sines-signals/index.html https://jackschaedler.github.io/circles-sines-signals/index....

marmetio 4y ago
Nice. I used All Signal Processing to get an intuitive feel through visualization. There's a website, but the videos are more easily accessible through YouTube. Still worth checking out for the table of contents and quizzes. https://youtube.com/user/allsignalprocessing https://youtube.com/user/allsignalprocessing

raxxorraxor 4y ago

I only really understood it while looking at imaging. How the base frequencies overlap to form an image and how the phase information is much more important for signal reconstruction than the amplitude. While images have an additional dimension it still helped me to really figure out what was going on. Since it is so well documented I recommend looking at DCT that is employed in JPG. The principle is the same, just the frequency disection works a bit different.

deleted 4y ago

[deleted]

kevlened 4y ago

The 2-minute brute-force explanation of Fourier transforms in a recent Veritasium video was my "aha!" moment. https://www.youtube.com/watch?v=nmgFG7PUHfo&t=464s https://www.youtube.com/watch?v=nmgFG7PUHfo&t=464s

photochemsyn 4y ago
For an additional video exposition, I also like Eugene Khutoryansky's "Fourier Transform, Fourier Series, and frequency spectrum" https://www.youtube.com/watch?v=r18Gi8lSkfM https://www.youtube.com/watch?v=r18Gi8lSkfM In particular, the visualization of the addition of sine waves of different frequencies in three dimensions is pretty spectacular. It's similar to Mathologer's "Epicycles, complex Fourier series and Homer Simpson's orbit": https://www.youtube.com/watch?v=qS4H6PEcCCA https://www.youtube.com/watch?v=qS4H6PEcCCA
SnooSux 4y ago
I have a Bachelors and Master's in Electrical Engineering and do some signal and image processing as part of my job. I've been working with FFTs since undergrad and I thought a good understanding of what it does and how it works. But that Veritasium video helped me put all the pieces together in a way that made things click. The famous 3Blue1Brown video is also very strong and maybe explains why complex numbers are used better. Of course both videos leave stuff out in the interest of time but they should both be part of a signal processing curriculum.
SJSque 4y ago
I can also highly recommend 3Blue1Brown's treatment of the topic: https://www.youtube.com/watch?v=spUNpyF58BY https://www.youtube.com/watch?v=spUNpyF58BY (...which I see now is cited in the video that you link to!)
djmips 4y ago
You might also enjoy this Engineering Guy video playlist on how a mechanical harmonic analyzer works. https://youtube.com/playlist?list=PL0INsTTU1k2UYO9Mck-i5HNqGNW5AeEwq https://youtube.com/playlist?list=PL0INsTTU1k2UYO9Mck-i5HNqG...

femto 4y ago

A funky thing is that you can replace the 'N' sin/cos functions used in Fourier analysis with any set of 'N' orthogonal functions (aka basis functions). In this context, a Fourier transform is just a bunch of correlations of the function to be analysed with each basis function. Two functions are orthogonal if their correlation is zero. PCM is "Fourier analysis" with impulse functions in place of sin/cos. CDMA replaces sin/cos with a set of (almost) orthogonal functions with a wide bandwidth. From an information perspective, orthogonality of the basis functions means each component/coefficient is giving you new information about the signal. In real life you can only compute a finite number of coefficients, meaning you must have a finite amount of information, so there is an inherent uncertainty in the relationship between the signal being analysed and the output of Fourier analysis. (Physical quantities that have an uncertainty principle, such as position and momentum, are related to each other by a Fourier transform.)

sfpotter 4y ago
Need to be careful about the difference between the discrete Fourier transform and the Fourier series here. It sounds like you're talking about the discrete Fourier transform, but making some statements which apply to Fourier series. For the DFT, your N orthogonal "functions" are really just orthogonal vectors in C^N. In this case, if they're normalized appropriately, they certainly provide an orthonormal basis for C^N. But this is just linear algebra. The same is true of other orthogonal matrices which are discretized versions of systems of orthogonal functions. Like the discrete Wavelet transform, for example. On the other hand, with the Fourier series, to represent any 2pi-periodic square integrable function, you need an expansion over an infinite sequence of orthogonal basis functions. In this case, the complex exponentials with integer frequency. But you can't just take N arbitrary orthogonal functions and expect them to be meaningful when it comes to analyzing 2pi-periodic square integrable functions. Generating a system of orthogonal functions which truly spans L^2 for some set is more involved than what you do in linear algebra. You can read about Sturm-Liouville eigenvalue problems for one way. If you want a system of orthogonal polynomials, it's possible to use Gram-Schmidt, but notice that this doesn't make any sense for a periodic interval (and simply running Gram-Schmidt doesn't actually prove that the resulting sequence of polynomials actually spans L^2...). Also, note that the construction of the continuous wavelets is very different.

geokon 4y ago

I thought this was really well done without any misleading oversimplifications. I do think the author missed the central trick of the Fourier Transform though. He's right in pointing out the sounds aren't a bunch of sine waves (typically), but the trick is that Fourier frequencies are cleverly chosen so they're all orthogonal (ie. you can't represent any of them in terms of the other). The complex number form turns out to give you one of the simplest representations of this set of frequencies. I was wondering if anyone has a more rigorous explanation of the in-between frequencies part. I tried to follow this explanation from a great concise but rigorous book hosted online https://ccrma.stanford.edu/~jos//dft/Frequencies_Cracks.html https://ccrma.stanford.edu/~jos//dft/Frequencies_Cracks.html https://ccrma.stanford.edu/~jos//proj/Bessel_Functions.html https://ccrma.stanford.edu/~jos//proj/Bessel_Functions.html but unfortunately in this section it seems to gloss over the proof (or maybe I don't get it). It just sorta tells you "Bessel functions"! Which isn't very satisfying - especially when you have no idea what a Bessel function is.. I have a problem where my signal (which has a bit of noise) has maybe one (or several) strong non-multiple frequency (I likely know their approximately values a-priori). There may be other frequencies but they shouldn't be close in the frequency space. What I expect to see is a similar spectrogram with this same ringing. But what I'd like to do next is work backwards and estimate the original frequency and most importantly the phase! Everyone talks about the frequency ringing but everyone skips explaining what happens to the phase. And since I haven't been able to find a nice proof of the ringing, I haven't been able to work it out for myself either Does anyone happen to have any good pointers for me? Thank you :)

HelloNurse 4y ago
Citing from that page > In other words, $ J_k(\beta)$ is the amplitude of the $ k$ th harmonic in the Fourier-series expansion of the periodic signal $ x_m(t)$ . Or from the parent page about FM > It is well known that sinusoidal frequency-modulation of a sinusoid creates sinusoidal components that are uniformly spaced in frequency by multiples of the modulation frequency, with amplitudes given by the Bessel functions of the first kind [15]. As a special case, frequency-modulation of a sinusoid by itself generates a harmonic spectrum in which the $ k$ th harmonic amplitude is proportional to $ J_k(\beta)$ , where $ k$ is the order of the Bessel function and $ \beta $ is the FM index. In other words, Bessel functions come up in Fourier transforms of frequency modulation signals, because integrals. The calculations have been figured out centuries ago. Regarding phase and arbitrary frequencies, it's easier to understand in the discrete time case: a vector of N complex numbers (time domain samples) goes in, it's multiplied by a matrix, and a vector of N complex numbers (Fourier coefficients) comes out. Regardless of the input signal, such a transform can be inverted (up to rounding errors and the like) by multiplication with the inverse of the forward matrix: the difference between signals of different frequencies is that if periods are a whole fraction of N samples the projections fall on one Fourier coefficient instead of spreading around all of them. Aligning the signal's period with the window length M allows reproducing the whole infinite duration signal from a N coefficient slice because all slices are identical.

TuringTest 4y ago

To expand the insight, you may see this video about Wavelets which relates them to the Fourier transform. It explains wavelets as an intermediate point between pure waves (all time, no frequency representation) and the Fourier transform (all frequencies, no time representation), with wavelets having part of both. https://www.youtube.com/watch?v=jnxqHcObNK4 https://www.youtube.com/watch?v=jnxqHcObNK4

lupire 4y ago
"time" is present in both frequency and position. The difference is how time is sampled. Fourier Transform maps between global frequency space sampling and (repeating wave for all time) and local positional/point space sampling (perfect impulse). Wavelets map to an intermediate space,as you say, with smeared points/impulses and damped waves.
- dsego 4y ago
  In this aspect, are wavelets similar to how stft is done with a hann window or the like?