Fourier Transformation for a Data Scientist

Source: Deep Learning on Medium

Also, when we actually solve the above integral, we get these complex numbers where a and b correspond to the coefficients that we are after.

The continuous Fourier transform converts a time-domain signal of infinite duration into a continuous spectrum composed of an infinite number of sinusoids. In practice, we deal with signals that are discretely sampled, usually at constant intervals, and of finite duration or periodic. For this purpose, the classical Fourier transform algorithm can be expressed as a Discrete Fourier transform (DFT), which converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform:

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 the Fourier Transform equation and solve it, it will produce a real and imaginary part.

As you can see X consist of a complex number of the format a+ib or a-ib. So if you solve the above equation you will get the Fourier coefficients a and b.

Now if you just put the values of a and b in the equation of f(t) then you can define a signal in terms of its frequency.

In general practice, we use Fast Fourier Transformation(FFT) which is a discrete Fourier transform algorithm that reduces the number of computations needed for N points from 2N² to 2NlogN.

Why are cosine and sine functions used when representing a signal?

While Sine and Cosine functions were originally defined based on right-angle triangles, looking at that point of view in the current scenario isn’t really the best thing. You might have been taught to recognize the Sine function as “opposite by hypotenuse”, but now it’s time to have a slightly different point of view.

Consider the unit circle :

on a Cartesian plane. Suppose a line passing through the origin makes an angle θ with the 𝑥-axis in a counterclockwise direction, the point of intersection of the line and the circle is (cos⁡θ, sin⁡θ).

Think about it. Does this point of view correlate with the earlier one? Both of the definitions are the same.

Suppose we start to spin the line, by making θ increase linearly. You’d get something like this:

Credits

The Sine and Cosine functions are arguably the most important periodic functions in several cases:

  1. The periodic functions of how displacement, velocity, and acceleration change with time in SHM oscillators are sinusoidal functions.
  2. Every particle has a wave nature and vice versa. This is de Broglie’s Wave-Particle duality. Waves are always sinusoidal functions of some physical quantity (such as Electric Field for EM Waves, and Pressure for Sound Waves).

The sound itself is a pressure disturbance that propagates through material media capable of compressing and expanding. It’s the pressure at a point along with the sound wave that varies sinusoidally with time.

Convergence in Fourier transformation

If a point travels around a circle at a constant speed, its height above the ground traces a sine function. The speed at which the point moves corresponds to the frequency and the radius of the circle corresponds to the amplitude.

Add 1 more circle,

Add 2 more circles,

Add 9 more circles:

Almost a discrete waveform.

Because of the Fourier theorem, we can generate any signal with circles of appropriate frequencies and radii. Here’s an approximate square wave, for example.

I used Dan Shiffman’s code from coding challenge #125 to make the animations. You can get the javascript code from his GitHub and can try yourself.

Fourier Transformation in AI

Fourier Transformation is a linear function, to induce non-linearity. Convolutions are used.

Fourier Transformation of the product of 2 signals is the convolution of the 2 signals.

Let x(t) and y(t) be two functions with convolution x(t)*y(t), then

Remember the fact that a convolution in the time domain is a multiplication in the frequency domain. This is how Fourier Transform is mostly used in machine learning and more specifically deep learning algorithms.

I’ll take Convolutional Neural Networks, CNNs as an example;

90% of computations in CNNs are convolutions and there have been many approaches to reduce the intensity of such computations, one of them is Fast Fourier Transform (FFT).

Instead of convolutions, the input and filter matrices are converted into the frequency domain by FFT, to do multiplications. Then, the output is converted back into the time domain by Inverse FFT (IFFT).

Another use of FFT is that it can be used for dimensionality reduction or feature extraction.

When each sample in the dataset is a signal (time series, or images, etc.), it may consist of thousands of samples. But they might actually correspond to just a few points in the Fourier domain (especially if there is some periodicity). This simplifies the problem a lot.

Or sometimes using the Fourier domain might provide translation-invariance. That is, even if there are lags between the signals, such variances will not affect their presentation in the Fourier domain.

Conclusion

The FFT is used in digital recording, sampling, additive synthesis and pitch correction software.

The FFT’s importance derives from the fact that it has made working in the frequency domain equally computationally feasible as working in the temporal or spatial domain. Some of the important applications of the FFT include:

Well, that’s all for this article hope you guys have enjoyed reading it and I’ll be glad if the article is of any help. Feel free to share your comments/thoughts/feedback in the comment section.

Thanks for reading!!!