What’s a Fourier transform?

A Fourier transform is a generic method to decompose generic functions into a superposition of symmetric functions.

Let’s take an example. Let us have a signal S1.

S1: x-axis is time and the y-axis is amplitude

If we want to measure the strength of this signal at some specific time. We measure it by its amplitude. So, the amplitude of the signal S1 is 1.

If we do the same for another signal and select the same moment in time and we measure its amplitude. Let we have another signal S2 like this

S2: x-axis is time and the y-axis is amplitude

Also, the amplitude of the signal S2 is 2

So, when we emit these two signals at the same moment of time, we get a new signal which is the sum of the amplitude of these two signals. This is so because these two signals are being added together.

S3=S1+S2: x-axis is time and the y-axis is amplitude

So, the amplitude of S3 = amplitude of S1 + amplitude of S2 = 1 + 2 = 3
So, the amplitude of signal S3 is 3

If we are given signal S3 only (which is the sum of signals S1 and S2).Can we recover the original signals S1 and S2?

Yes. That’s what a Fourier transform does. It takes up a signal and decomposes it to the frequencies that made it up.

Signal Generation and Phase Shift

If we want to describe a signal, we need three things :

  1. The frequency of the signal which shows, how many occurrences in the period we have.
  2. Amplitude which shows the height of the signal or in other terms the strength of the signal.
  3. Phase shift as to where does the signal starts.

The very first example that we took was very simple, every signal had the same frequency and phase difference and only different amplitudes.

We will now look at a slightly complex example and we will look at the individual signal from the above example because in order to understand Fourier transform better we need to look at the individual signals closely.

Below is the original signals that we were looking above.

Signal 1
Signal 2
Signal 3

Frequency: If we look closely at the three signals, we will notice that the frequency of all the three signals is different.

If for the same period of time, in signal 1 there is n number of waves then there are 2n number of waves in signal 2 and vice versa.

Phase: Also, when we look closely as to where actually the signal starts. We will find that While signal 1 starts at (0,0), signal 2 starts at (-0.5,0) if we trace the wave to meet the y-axis at 0. So, at 0 we already have the maximum amplitude of the signal. This is what we call Phase shift.

Amplitude: All the three signals have different amplitudes, Signal 1 has an amplitude of 1 while signal 2 and signal 3 has an amplitude of 2 and 3 respectively.

This is all captured in an elegant and super simple mathematical formula. So, In the above examples if the x-axis is termed as x and y-axis is termed as y. We can generate y as a function of t such that :

Using this formula, we can generate any type of signal that we want and then we can merge them together and play with them. For example, If we merge signals 1, 2 and 3. we will get a signal like this :

Signal 1 + Signal2 + Signal3

How Fourier Transform Works?

The main idea behind Fourier transform is that :

Any continuous signal in the time domain can be represented uniquely and unambiguously by an infinite series of sinusoids.

It means that, If we have a signal and this signal is generated by some function x(t) then we can come up with another function f(t) such that :

Now, the question that arises now is, How do we find the coefficients here in the above equation because these are the values that would determine the shape of the output and thus the signal.

Discrete Fourier Transform

Any sampled signal of length N in the time domain can be represented uniquely and unambiguously by a finite series of sinusoids.

So, We don’t have to deal with infinity anymore in our new definition.

In standard Fourier Transform, we used a function of time x(t) to generate a continuous signal. Now In the discrete case, we don't have a function, we have a dataset, a set of points which we get by sampling the continuous signal. So, I will use {x} to donate a dataset such that it contains the reading from the sampling such that :

and what Discrete Fourier Transform will do for us is that it will transform the dataset of {x} into another dataset {X} which will contain the Fourier coefficients such that :

If we look at the definition of Fourier Transform, each X in {X} is a complex number and it contains the a and b components for the frequencies.

If we think about, what drives the length of {x} dataset is the sampling rate because, over a period of time, the number of data points I read is exactly the sampling rate right? If we think about the other dataset {X} , we said that frequency is the number of occurrences per unit of time. So If I am sampling with a certain frequency, I cannot recognize signals that have larger frequency then the sampling frequency just because we don't get enough data points.

So, If we have signals with very high frequencies on a very low sampling rate, we won’t be able to recognize these signals at all. So, the number of frequencies that we can recognize by applying the Fourier Transform is actually driven by sampling rate as well.

So, now that we have our dataset {x} we will get {Xk} such that it is an element in {X} which are my Fourier coefficients such that :

So, this is essentially the Discrete Fourier Transform. We can do this computation and it will produce a complex number in the form of a + ib where we have two coefficients for the Fourier series.

Now, we know how to sample signals and how to apply a Discrete Fourier Transform. The last thing we would like to do is, we would like to get rid of the complex number i because it's not supported in mllib or systemML by using something known as Euler's formula which states :

So, If we plug Euler’s formula in Fourier Transform equation, we get

we also know that cos(-θ) = cos(θ) and sin(-θ) = -sin(θ) and if we use this in the above equation, the equation could be simplified as :

and we can actually break the above equation in two sums, such that :

Now, If we compare the above equation with the equation of a complex number which is a + ib then we get the corresponding value as :

So, now we can put these values in the equation of f(t) and get the result.

Data Science Diary