Now that we know how to sample signal, it's time to look at modification of the algorithm known as discrete Fourier transform. And as you can guess by it's name, it's tailored to work with discrete signals. So first the definition, well, it says that any sampled signal of length N can be represented uniquely by a finite series of sinusoids. And I already like this because it says finite. So I don't have to deal with infinity anymore. What is the difference? Well, in the standard Fourier transform, we used function of time x of t to generate a continuous signal. Now with the discrete case, we don't have this function, we have a data set. A set of points which we get by sampling the continuous signal. So I will use lowercase x to denote this data set, I will enclose it here. And I will say that it contains, well, the readings from my sampling, x0 x1, and so on until let's say xN-1. So the length of my data set x = N. And what discrete Fourier transform will do for me is it will transform this data set of lowercase x into another data set of lets say upper case X, which contains the Fourier coefficients, right? So I will have things like X0, X1, And so on until XN-1. And each X here, If we look at the definition of Fourier transform is a complex number with two components. So it contains the a and b coefficients for the frequency. Now one question that you may ask is how come that these two data set have the same length, N-1? And that's an excellent question. If you think about it, what drives the length of this data set is the sampling grade, because over a period of time, the number of data points that I read is exactly the sampling grade, right? And then if you think about the other data set, we said that the frequency is the number of occurrences per unit of time. So if I am sampling with certain frequency, I can not recognize signals that have larger frequency than the sampling frequency, just because I don't get enough data points. What will happen is, like the example I showed you, when I have too few data points, I lose the signal. It kind of turns into flat line. Because the resolution is low, the representation of the sampled signals doesn't actually follow the actual signals. So if I have signals with very high frequencies on a very low sampling grade, I won't be able to recognize these signals at all. So the number of frequencies that I can recognize by applying the Fourirer transform is actually driven by the sampling rate as well. And I have prepared the script to show you this. So if I go back here, okay? I have a script that generates a signal. In this case I'm doing a frequency of 3 Hz, amplitude of 2, period of 1, sampling grade is 50, and then I also apply Fourier transform. And again, I'm treating it as a black box because that's discreet Fourier transform. We haven't talked about how to actually apply it. But let me run the script now and see what we get. So this is my signal, amplitude of two, and I have three waves over the time period. And here on my spectrogram, I have one bin with a height of two because it reflects the amplitude of the signal. And it's at position three, which is the frequency of the signal, right? Nothing new here. This is what we expect. If I change this to, I don't know, if I change this to frequency of five, what will happen is that my bin will move to five, right? And this is expected. I will go back to three and what I will do maybe just as an extra practice to show you what happens if I add more signals into the mix. So maybe I will generate second signal with a frequency of 5. Let's say same amplitude, same period, and I'll add this to the original signal. So now I have my signal with frequency of 3, amplitude of 2 added to signal with frequency of 5 and amplitude of 2. And I will plot this and apply Fourier transform. So let's see what happens. Okay, so here you see that we have a more complex signal this time, but the transformation is correct here and it perfectly recognizes two distinct signals. One with frequency of three, the other one five, both having amplitude of two. If I add another one, let's say frequency of I don't know, frequency of maybe six, yeah. And let's leave the amplitude to one. See what happens. You have to add it to the signal, right? Again, we can now detect three signals. This one have the strength of the other two because its amplitude is one, right? So this is what you expect. Now, actually maybe another interesting question. What do you think will happen if I change the frequency, let's say of my second signal from 6 to let's say 6.5. What do you think will happen? Okay, so what happens is that Fourier transform will decompose this signal into some frequencies, right? We'll get something like this. Because we don't hear of a bin with the frequency of 6.5, this signal is being decomposed to some further signals. And when you add them together, you get this signal of frequency 6.5. Okay, this was a tricky question. But my point is about something grade and the number of bins, the resolution of the spectrogram. So if I remove these additional signals, if I go to back to my original signal that’s only one simple sinusoid, amplitude of two, frequency of three. Here you can see that I have a number of bins in my spectrogram. This is driven by my sampling grade because this tells me how many different frequencies I can recognize My sampling grade is 50 here. I don't see 50 bins because there is something else called the Nyquist limit, and it has to do with the spectrogram being actually symmetrical. So, okay, I wasn't planning to do this in this session, but maybe I'll just show you the full spectrogram. So, right. So this is the full spectrogram from the Fourier transform, all right? And there is a specific point somewhere in the middle of the spectrogram called the Nyquist limit or Nyquist point. And the spectrogram is symmetrical around this point. It's almost like a mirror. So the left hand side of the spectrogram contains all the information that we need, so normally we just don't plot this right-hand side, we just kind of ignore it, right? But the point is I have a sampling grade of 50, and I actually have 50 bins here in the full spectrogram. However, it's symmetrical and all the information I need Is contained in the first 25, so I just kind of don't plot the others. But the point is that the sampling rate drives the number of bins, right? So if I reduce my sampling grade, let's say I reduce my sampling grade to 20, and I do the same thing, you will see that the number of bins now falls down to 10, right, which is half of 20. And also you see the quality of my signal on the top right? And if I keep going down, Fourier is still doing the right thing. But if I keep going down, you will see that actually the resolution worsened, gets worse, and also the number of bins get reduced, and so on and so on. And at certain point, I will have less bins than needed to recognize my wave. And then instead of having a single bin, I will get a number of bins with different amplitudes that I have to sum up to actually approximate the original signal. And probably the original signal won't actually represent the actual signal. So the sampled version won't actually represent the original version because of the lower resolution. So that's one point. Let's go back to the lecture and talk about how we actually do this grade Fourier transform. So now that I have my date set X, I will get XK, XK is an element in X. These are my Fourier coefficients. This will be the sum, K, actually I'll use N here because I have to go over the elements in lower-case x. So let me just make this proper. This is k. Okay, n goes from 0 to n-1, okay? xN, this is lowercase x, e to the power of -2 pi i over N kn. Okay, so this is essentially the discrete Fourier transform. For each k, 0, 1, 2, 3 and so on, for each bin, each frequency that I can recognize, I can do this computation. And it will actually produce, again, as you can see here I have this complex number. So it will produce a complex number in the form of a + bi, where I have my two coefficients. For the Fourier series, now I know how to sample signals. I know how to apply this great Fourier transform. The last thing I would like to do is get rid of this complex number. Because it's not supported in NLLib, it's not supported in SystemML, so we have to find a way around it. And what I will do is I will use something called the Euler's formula, which tells me that this complex exponent, it tells me that this e to the power of i theta, let's say, can be written as cosine of theta + i sine of theta. So if I plug this here, I will get, let me rewrite it here, I will get xk = the sum, N goes from 0 to N-1. Okay, of xn and then I will use Euler's formula and I get the cosine of -2 pi Kn over N + i sin of minus 2 pi kn over N. And I can actually simplify this a bit more because I know that cosine of minus theta is actually cosine of theta. And I also know that the sine of minus theta is minus sine of theta. And if I use this here, right, I can rewrite XK is the sum of N equals 1 to N-1 of Xn, and I can say here cosine of 2 pi Kn. I get rid of the minus over N, minus, I replace the plus with the minus and I'll get rid of this minus here sine of 2PiKn over N. Okay, and I can actually break this down into two sums. So I can say that this is actually two sums. One sum going from 0 to N-1 of XN cosine of 2pi kn over N minus another sum, I will take i at the front, n-0, N-1 of sine 2 pi KN over N, right? And what did I get? Well, this is my complex number, right? So this is my coefficient ak, and this here is my coefficient bk. Actually, let me keep the notation consistent because if I'm using capitals for the Fourier coefficients, I want to stick to capitals, BK, right? So if I compute these two sums, I don't actually have to deal with the complex numbers. And this is how I can get this pair of coefficients for XK, right? And this what this grade Fourier transform looks like. Now we need to think about implementing it. And because I said that it doesn't come out of the box in MA lib, what I will do is how we used system ML, and how we write an implementation from scratch.
