# Fourier Transformation and Its Mathematics

Here is an example of how the form of the signal changes with the change in sampling rate :Let the original signal be a signal with an amplitude of two and frequency of five over a period of one second :sampling rate = 1000Now, as we decrease the sampling rate, let's look at how the shape of the signal changes :sampling rate = 50As we decrease the sampling the sampling rate further, we get :sampling rate = 15So, the bottom line is : The higher the sampling rate, the better the quality of the signal and also we can distinguish between more frequencies.Now, that we know how to sample the signals, we will look at the modification of the algorithms known as Discrete Fourier Transform.Discrete Fourier TransformAny 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.What is the difference?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.But, How come the two datasets {x} and {X} have the same length?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 :Fourier TransformSo, 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 :Eulers FormulaSo, If we plug Euler's formula in Fourier Transform equation, we getwe 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.ConclusionIn practice we use a slight modification of the Discrete Fourier Transform known as Fast Fourier Transform because Discrete Fourier Transform is very simple, basic and also slow..Its not fit for purpose If we really want to do something in production environment..Computation complexity of Discrete Fourier Transform is quadratic time O(n²) and Fast Fourier Transform for comparison is quasi-linear time O(nlogn)..Fast Fourier Transform does this by exploiting assymetry in the Fourier Transformation.. More details