In the beginning...
I first heard about the Fourier Transform in a stuffy lecture theater. I was fighting off sleep at the time and thought the whole thing was just too abstract and so did my fellow students judging by their nodding heads. Still, I was good at math and I learned what I needed to get through the exam. It's only years later that I realized how fundamental and important the Fourier Transform is in the real world. The professor could have made his lectures come alive if only he'd only given us a taste of why it's so consequential in so many areas.
In this blog post, I'm going to make up for my professor's shortcomings and explain why it's so important. I'm also going to share some of the math because that shows where it all comes from and how it can be used. But first, let's have a really high-level explanation of what a Fourier Transform is.
The ELI5 version of Fourier Transforms
The Fourier Transform converts data measured in one domain to data in the inverse domain. For example, it can convert music in the time domain to its constituent frequencies in the frequency domain.
It works by decomposing a signal into a series of overlapping sine waves. Even a square pulse can be decomposed into sine waves, in this case yielding an infinite number of them. Once you have the sine waves, you can work out their frequencies and so do the conversion from the time to to frequency domain. Understanding that any signal is a sum of sine waves opens the door to understanding natural phenomena like analog circuit behavior or heat flow.
There are two types of Fourier Transform: a version which works on discrete data (like sampled music) and a version which works on continuous data (for example, an equation describing the orbit of a planet).
What use is it?
The easiest example to explain is processing audio data like music. Digitized music is in the time domain and applying the Fourier Transform puts the data in the frequency domain. Once it's in the frequency domain we can do things like filtering out frequencies we don't want. For example, by removing frequencies humans can't hear, we can compress the data (which is partly how MP3 works).
It's not just music signals; the Fourier Transform is used extensively in signal processing, including processing radar, sonar, radio signals, images (including medical images), and seismology data. It's the same idea in each field: by transforming the data into the inverse domain some types of processing become a lot easier.
It turns out it's fundamental to quantum mechanics too. The Heisenberg Uncertainty Principle states that you can't know a particle's position and momentum both with 100% accuracy; the more you know about one, the less you know about the other. In quantum theory, position and momentum are Fourier Transform pairs, which means one is the Fourier Transform of the other. This relationship directly leads to the Heisenberg Uncertainty Principle as I'll show later.
Back in the 19th century, the transform was originally developed to model the flow of heat. Legend has it, Napoleon wanted more efficient cannons, so he engaged Jean-Baptiste Joseph Fourier to study the limiting factor for cannons, which was heat flow. In solving this problem, one of Fourier's key insights was that any complex signal or wave could be decomposed into a series of overlapping sine waves. At the time, this idea was very controversial and it took some time for the scientific community to accept it.
These uses cases should have been enough to wake up sleepy students, but there's more.
It turns out, Fourier Transforms play a key role in probability theory, which is why they're used to model risk in insurance companies. I'll come back to this in a later blog post.
Given what we already know, it's probably not a surprise that they're used to solve some differential equations; an intractable problem in one domain might be very solvable in the inverse domain. Perhaps more surprisingly, they also creep into number theory.
I haven't covered all of its uses, but let's move on to defining some quantities and the Fourier Transform itself.
WTF - too many fs and notation issues
There's a really dumb problem with the Fourier Transform, there are two many things beginning with f. We have f for frequency, function, and Fourier. Capital letters only take us so far so we're going to have to make some choices about what characters we use for what. I'm following the herd with my choice of notation.
- \(f\) is for function
- \(\mathcal{F}\) is for the Fourier Transform
- \(\mathcal{F}^{-1}\) is for the inverse Fourier Transform
- \(\nu\) is for frequency - don't confuse this symbol with \(v\) for velocity
- \(\omega\) is for angular frequency
Angular frequency is the number of radians per second and there are \(2 \pi\) radians in a complete oscillation. Here's how frequency and angular frequency are related:
Why do we care about angular frequency? Because \(2 \pi \nu\) crops up a lot in Fourier math and using \(\omega\) just simplifies things.
Discrete Fourier Transforms
Let's imagine we have a signal we've sampled in the time domain, say we sample some live music at a rate of 96 kHz (or one sample every 10 micro-seconds). We'll represent our signal like this:
\[\{x_n\} = \{x_0, x_1, x_2, ..., x_{N-1}\}\]
The Fourier Transform of \(x_n\) is:
\[ X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i2\pi \frac{k}{N} n} \]
which gives us the transformed data set:
\[\{X_k\} = \{X_0, X_1, X_2, ..., X_{N-1}\}\]
This is all very abstract, so let me show you what this means in reality. Let's imagine that our music is a simple sine wave that looks like this:
\[x_n = \sin(2\pi \cdot 9000 \cdot t)\]
Of course, we're dealing with discrete data in this section, so we're going to sample the data at 48 kHz. If we plot it out, it looks like this (the light blue line is just to guide the eye, the dots are the measured data):
Now, let's Fourier Transform the data. After the transform, we get data in the frequency domain that looks like this:
See the peak in Fourier Transform plot? That tells us the frequencies present in the data. In this case, we know there's only one frequency and we know what it is, but that's not always the case. We can use this technique to find out the "active frequencies" in a piece of music or speech. The chart below is the Fourier Transform of some sampled music, you can see the frequencies present and you can see this is much, much more complex than a simple sine wave.
(BTW - do you think you can identify the piece of music? It's a 10 second burst from the start of a very famous song.)
Once we know all the frequencies present, we can remove some of them and transform the signal back to the time domain, which takes us to the inverse Fourier Transform.
Let's say we've done what we want to do with the frequency domain data \({X_k}\), how do we bring the data back to the time domain? With an inverse Fourier Transform defined like this:
\[ x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot e^{i2\pi \frac{k}{N} n} \]
I'll do one more example to give you a flavor of what you can do with this method. Let's say we have a more complicated time domain signal with two frequencies, like this:
\[x(t) = 0.5\sin(2\pi \cdot 9000 \cdot t) + 1.0\sin(2\pi \cdot 12000 \cdot t)\]
Here's what this looks like on a chart:
How might we get rid of one of the two frequencies? Let's start by doing a Fourier Transform and looking at the data. We can see the two peaks corresponding to the two frequencies.
Let's cut the higher frequency out so the data looks like this.
Now, let's transform the data back to the time domain. Here's what we get (chart below).
We've filtered out the higher frequency.
In reality, digital filtering is much more sophisticated than this, but this simple example gives you a taste of what's possible.
Before I move on to talk about continuous data, it's worth noting that the discrete Fourier Transform only works on data that's been sampled at regular intervals. This sounds like it's trivial, but it has important consequences for real-world analysis.
Continuous Fourier Transform
To put it simply, continuous data is data that has values at all points, it has no gaps, meaning it isn't sampled. In the continuous case, we have the equations that govern the data. Good examples of continuous data include the equations governing the motion of planets, probability distributions, and electrical voltage.
We'll start with a continuous function, \(f(x)\), it's Fourier Transform is:
\[F(\omega) = \int_{-\infty}^{\infty} f(t)\, e^{-i\omega t} \, dt\]
To go back, there's the inverse Fourier Transform, defined like this:
\[ f(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} F(\omega)\, e^{i\omega t} \, d\omega \]
For a continuous signal defined like this:
\[ x(t) = 0.5\sin(2\pi \cdot 9000 \cdot t) + 1.0\sin(2\pi \cdot 12000 \cdot t) \]
It's looks like this in the time domain:
Its Fourier Transform looks like this:
Just as in the discrete case, the transform of the signal lets you clearly see the frequencies present in the data and their relative importance. The frequency at 12 kHz is "louder" and we can see that from the equation and the Fourier Transform.
It's often useful to know how much power is present at different frequencies. We can do this by something called the power spectral density. The Fourier Transform often gives complex data (in the sense of complex numbers, meaning having a real and imaginary component). The power spectral density is the magnitude squared of the real component.
Proof by assertion
I've just quoted the Fourier Transform equations without having derived them. That's deliberate because I want to focus on their use and properties rather than spending too much time on the math (it's also a pain to write so much LaTex). Years ago, my professor focused on their derivation and we spent lecture after lecture on derivations, which for me missed the point. I want to focus on their use.
The dirac delta function and quantum theory
This is a little abstract, but it does help explain how the Heisenberg Uncertainty Principle comes from the Fourier Transform. It's also a nice example of it's use.
The dirac delta function is a weird mathematical function. It's not really a function, it's something else, but it is useful. The function is zero everywhere except at zero where it has the value infinity. Mathematically, this is:
\[ \delta(x) = \begin{cases} +\infty, & x = 0 \\ 0, & x \neq 0 \end{cases}, \quad \int_{-\infty}^{\infty}\delta(x)\,dx = 1 \]Here's a chart showing the same idea.
Let's say we know the position of a subatomic particle with 100% certainty. That means the uncertainty in /(x/) is 0, so we can model the position using a dirac delta function.
Momentum is the Fourier Transform of position, and here's the Fourier Transform of the dirac delta function.
This chart shows the Fourier Transform has the same value everywhere. In other words, all possible momentum values are equally likely. Which means if we know the position with 100% certainty we know the momentum with 0% certainty.
The properties of Fourier Transforms
In professional use of the Fourier Transform, we're often combining multiple functions and transforming them, so it's useful to know how the transform behaves. Let's go through some of its properties.
Scaling
If we have a function \(f(at)\), where \(a\) is a constant, then:
\[ \mathcal{F}\{f(at)\}(\nu) = \frac{1}{|a|}\mathcal{F}\{f\}\left(\frac{\nu}{a}\right) \] \[ \mathcal{F}^{-1}\left\{\frac{1}{|a|}\mathcal{F}\{f\}\left(\frac{\nu}{a}\right)\right\}(t) = f(at) \]Linearity
If \(f(t)\) and \(g(t)\) are functions with Fourier Transforms \(F(\nu)\) and \(G(\nu)\), and \(a\) and \(b\) are constants, then:
\[ \mathcal{F}\{af(t)+bg(t)\}(\nu) = a\mathcal{F}\{f\}(\nu) + b\mathcal{F}\{g\}(\nu) \]Time reversal
\[ \mathcal{F}\{f(-t)\}(\nu) = \mathcal{F}\{f\}(-\nu) \] \[ \mathcal{F}^{-1}\{\mathcal{F}\{f\}(-\nu)\}(t) = f(-t) \]Time shifting
This property says that shifting a signal in time (e.g., delaying it) adds a phase shift to the Fourier Transform of the signal. That's a little to complex (pardon the pun) for me to explain here.
\[ \mathcal{F}\{f(t-t_0)\}(\nu) = e^{-i2\pi\nu t_0}\mathcal{F}\{f\}(\nu) \] \[ \mathcal{F}^{-1}\{e^{-i2\pi\nu t_0}\mathcal{F}\{f\}(\nu)\}(t) = f(t-t_0) \]Frequency shifting
This is another property I'm not going to explain too much, other than saying it's similar in concept to the time shifting property.
\[ \mathcal{F}\{f(t)e^{i2\pi\nu_0 t}\}(\nu) = \mathcal{F}\{f\}(\nu-\nu_0) \] \[ \mathcal{F}^{-1}\{\mathcal{F}\{f\}(\nu-\nu_0)\}(t) = f(t)e^{i2\pi\nu_0 t} \]Conjugation
I've shied away talking about the fact that the Fourier Transform relies on complex numbers underneath. My Professor zoomed in on that area and we spent a long time slogging through complex algebra to get to results. Yes, the fact that they're complex underneath is important, but for me it misses the wood for the trees. Anyway, here's the complex properties.
\[ \mathcal{F}\{f^*(t)\}(\nu) = \mathcal{F}\{f\}^*(-\nu) \] \[ \mathcal{F}^{-1}\{\mathcal{F}\{f\}^*(-\nu)\}(t) = f^*(t) \]Differentiation
Differentiation in the time domain corresponds to multiplying by frequency in the frequency domain. This is a very powerful property and can massively simplify some calculations.
\[ \mathcal{F}\{f'(t)\}(\nu) = i2\pi\nu\,\mathcal{F}\{f\}(\nu) \] \[ \mathcal{F}\{f'(t)\}(\omega) = i\omega\,\mathcal{F}\{f\}(\omega) \] \[ \mathcal{F}\{f^{(n)}(t)\}(\nu) = (i2\pi\nu)^n\mathcal{F}\{f\}(\nu) \] \[ \mathcal{F}^{-1}\{i2\pi\nu\,\mathcal{F}\{f\}(\nu)\}(t) = f'(t) \]Integration
This is another very powerful relationship. It relates integration to division and so may very well simplify calculations.
\[ \mathcal{F}\left\{\int_{-\infty}^{t}f(\tau)\,d\tau\right\}(\nu) = \frac{1}{i2\pi\nu}\mathcal{F}\{f\}(\nu) + \frac{1}{2}\mathcal{F}\{f\}(0)\,\delta(\nu) \] \[ \mathcal{F}\left\{\int_{-\infty}^{t}f(\tau)\,d\tau\right\}(\omega) = \frac{1}{i\omega}\mathcal{F}\{f\}(\omega) + \pi\,\mathcal{F}\{f\}(0)\,\delta(\omega) \] \[ \mathcal{F}^{-1}\left\{\frac{1}{i2\pi\nu}\mathcal{F}\{f\}(\nu)\right\}(t) = \int_{-\infty}^{t}f(\tau)\,d\tau \quad \text{(when } \mathcal{F}\{f\}(0)=0\text{)} \]Parseval's theorem
Mathematically, this looks difficult, but the meaning is simple: the energy of a signal is the same in the time domain and the frequency domain. This can be very helpful when you're dealing with some complicated systems.
\[ \int_{-\infty}^{\infty}|f(t)|^2\,dt = \int_{-\infty}^{\infty}|\mathcal{F}\{f\}(\nu)|^2\,d\nu \] \[ \int_{-\infty}^{\infty}|f(t)|^2\,dt = \frac{1}{2\pi}\int_{-\infty}^{\infty}|\mathcal{F}\{f\}(\omega)|^2\,d\omega \] \[ \int_{-\infty}^{\infty}f(t)g^*(t)\,dt = \int_{-\infty}^{\infty}\mathcal{F}\{f\}(\nu)\mathcal{F}\{g\}^*(\nu)\,d\nu \]What do the properties mean?
Let's say you're doing some signal processing, maybe trying to process a weak signal in the presence of noise and other signals. You need to do math on the data you receive to filter it, amplify it, and so on. The key signal processing operations all rely on the properties I've just outlined.
Of course, it's not just signal processing. These properties also come into play when you're combining probability distributions to calculate risk. Even something like Parseval's theorem turns out to be important in insurance.
Convolution
One of the most astonishing uses of the Fourier Transform is in convolution. That's such a big topic, I'm going to write my next blog post on it.
The Fast Fourier Transform
The Fourier Transform is important, but it would have remained a theoretical nicety if it weren't for the Fast Fourier Transform.
As I said in the beginning, the key insight Fourier had was that an arbitrary signal can be decomposed into a series of overlapping sine waves. That's great, but to do this kind of decomposition in the real world is computationally very expensive, especially in the digital domain. If it had remained this expensive, frankly we wouldn't be using it much.
The game changer was the discovery of the Fast Fourier Transform (or FFT) algorithm. This slashed the number of computations for digital transformations bringing it well within the reach of computers, even computers in the early days of computing.
The FFT story is an interesting one. It seems to have been discovered several times and the ground work was laid years before it was developed. The math is interesting, but tedious to write out and draw.
Because it's a whole big topic of itself, I'm going to gloss over it for now. I might return to it later in another post. For now, you should know it a very big deal.
Closing thoughts (for now)
I'm going to be bold here. The Fourier Transform (particularly in it's FFT form), has changed the world. It's one of the hidden engines of the modern world, driving areas as diverse as music processing and insurance risk calculation.
It does neatly illustrate one of the problems we face as a society. It's a crucial core technology to our lives, but it takes serious math to understand it. Which means that the majority of the population don't understand it and aren't in any position to make judgements or decisions about it. If the population doesn't understand key areas, how can a government allocate research funding to those areas and retain public support? Trust is the answer, but that's a whole different blog post.
I would advise that anyone working in math-heavy areas understand the what and why of the Fourier Transform. It's fundamental in many areas. Don't get lost in the derivations, but focus instead on how to use it for your benefit.
Oh, and pay attention to your physics professor when they're lecturing about Fourier Transforms.
AI statement
I (a human being) wrote all of this. I did not use AI for any of the writing. I used AI to generate code to show charts and I used AI to correctly format equations.