Okay. Time to open the box. So the idea of Fourier transform stems from the work of Jean-Baptiste Fourier, a French mathematician who came up with this idea that any continuous signal in the time domain can be represented uniquely by an infinite series of sinusoids. So what does this mean? If we have a signal, it doesn't matter how complex the signal is. This signal is being generated by some function. Let's say the function is x_t. Then we can come up with another function f which is also a function of time, that has this form a0 over two. This is just a constant plus a sum that goes from, let's say K1. K is our indicator variable to infinity of ak times cosine of 2Pikt plus bk sine 2Pikt. So it doesn't matter how complex this signal is. We can find a function like this one which is a sum of an infinite series of sinusoids that will actually represent the signal perfectly. Of course, the question here, if you look at this function f_t is how do we find the coefficients here, ak and bk because these are the coefficients that determine the shape of the output. These are the coefficients that determine the signal. To get a and k, we use Fourier transform and the result from Fourier transform is a group of coefficients. So I will use capital X to denote the Fourier coefficients and this is again a function of the frequency this time, which we get by solving the integral that goes from minus infinity to plus infinity. So technically speaking, we are doing this because we want to cover non-periodic signals. If you are dealing with a repeating signal, what you can do is you can get this interval and make it one over t integral of minus t over two to plus t over two. But we can just generalize it. We can say that's an integral from minus infinity to plus infinity. We don't carry the signal is periodic or a periodic. What we do is we plug the function x_t times e to the power of minus two PiiFtdt. Right. Now the tricky part in this integral is actually this i here which denotes a complex number. So you probably remember a complex number is i to the power of 2 equals 2 minus 1 or if you prefer the square root of minus 1 equals i, and the form of the complex number is a plus bi. So it has a real and imaginary part and actually when you solve this integral, you get these complex numbers, where these parts corresponds to the coefficients that we're after. We do have however, three problems that we have to deal with. l'll write them down here. First and foremost, how do we implement this? How to implement Fourier transform. Because if you look at things like MLlib, it doesn't provide Fourier transform out of the box. We have to write our own implementation. When it comes to big data this might be a challenge. The second question is, how to deal with i this complex number. Because again if you think about it, MLlib doesn't support complex numbers. The third question will be, how to deal with discrete signals. Because first of all, we don't get continuous signals. When we get audio data in the computer it gets sampled by the analog-to-digital converter, so it is not continuous. Second of all, I really don't like this infinite series of sinusoids because honestly from a practical perspective, we can't have an infinite series that we sum over. So these three problems we have to tackle. I will start with the last one. How to deal with discrete signals. So if we look at this signal, if we have a continuous signal and we want to record it pretty much like what I did with my phone when I recorded the court, is what happens is the actually the signal gets sampled. So over a period of time, we take a bunch of points evenly spaced, so maybe one here, maybe one here, maybe one. I want to make them evenly spaced. So one here, one here, and one here. These are the data points that we rate in our computer. Now, if you link these points here, now I have used 1, 2, 3, 4, 5 points over a period of one second. So I have used five points over a period of one, which gives me five hertz sampling rate. If I connect these points, I'll get something like this which is not an ideal representation of my signal, it gives me the idea may be, I will have a point here somewhere. It gives me an idea of what the signal looks like, but it's not perfect. Now if I instead take more points, if I take, I don't know, if I take 30 points. If I get something like this, I will get much better representation of the signal. Because the curvature will, my when I connect the dots the lines that I get will follow the curvature of the actual signal more closely. So this is the idea, the higher the sampling grade is, the more data points per second we get. So there is the high-resolution the signal has and better represents what actually is in the real world. So that's why in my function that generates signals, I also had the perimeter of a parameter for the sampling right and maybe that's a good time to show you what happens when we start playing with the sampling rate. So if I go back here and I want to generate a signal, let's say phase shift zero. What does this do? This is too large. Lets say amplitude of two. Okay. Let's say frequency of five. So I have this signal now. Amplitude of two, frequency of five over a period of one second. As you can see here my sampling rate is something like 1000 hertz. So the curve of my signal is very smooth. But if I decrease the sampling rate, if I say something like I don't know 100, I still get a good representation of the signal. But you can see that it's getting less smooth. Maybe if I reduce this a bit more, you see it even better. Yeah. You see that I get the idea. But now because the resolution is slower, my signal, my plot is not so smooth and if I keep decreasing maybe if I go down to 15 this is what I get. If I keep going down the signal will diverge more and more from the original and 10 I get a flat line because what actually happens is that my sampling points coincide with the values for the signal on the zero of the y-axis and when I joined them together, I get a flat line and just because I don't have a sufficiently dense resolution I'm missing the actual curves in the signal. I'm only reading points on the axis and when I joined them together I get this flat line which is no longer a representation of my signal. But the bottom line is the higher the sampling rate, the better the quality of the signal is and also more frequencies we can distinguish in the signal and that's something that we will cover now because, now that we know how to sample signals and what the sampling rate is, we took problem three out of the picture and we have to think about how to change the mats to actually handle these discrete signals. So let me go back to go here. Let's talk about a modification of Fourier Transform called discrete Fourier transform, which handles that kind of sampled signals.