# Fourier Transform for Time Series: Fast Convolution Explained with numpy | by Yoann Mocquin | Jul, 2023

## Implementation from scratch vs numpy

The Fourier transform algorithm is considered one of the greatest discoveries in all of mathematics. French mathematician Jean-Baptiste Joseph Fourier laid the foundation for harmonic analysis in his book “Théorie analytique de la chaleur” in 1822. Today, the Fourier transform and all its variants form the basis of our modern world, powering technologies like compression, communication, image processing.

This wonderful framework also provides great tools for analysing time-series… and that’s why we’re here!

This post is part of a series on the Fourier transform. Today we will talk about convolution and how the Fourier transform provides the fastest way you can do it.

All figures and equations are made by the author.

Let’s start with basic definitions. The discrete Fourier transform for a discrete time sequence x of N elements is :

where k denotes the k-th frequency of the spectrum of x. Note that some author add a scaling factor of 1/N to that definition, but is not of great importance for this post — all in all it is just a matter of definition and sticking it to it.

The inverse Fourier transform is then (given the definition for the forward Fourier transform):

That being said, one of the most important theorem on Fourier transform is that convolution in one space is equivalent to multiplication in the other. In other words, the Fourier transform of a product is the convolution of the respective Fourier spectra, and the Fourier transform of a convolution is the product of the respective Fourier spectra.

and

where the dot represents the standard product (multiplication) and the circled star represents circular convolution.

Two important notes:

• Periodic signal : Fourier analysis framework consider that the signals we handle are periodic. In other words, they repeat from minus infinity to infinity. However it is not always practical to handle such signals with a finite memory computer, so we only “play” with one period, as we will see hereafter.
• Circular convolution : The convolution theorem states that multiplication is equivalent to circulation convolution, which is a bit different from linear convolution, which we are more accustomed to. As we will see, it is not that different, and not that complicated either.

If you’re familiar with linear convolution, often simply referred to as ‘convolution’, you won’t be confused by circular convolution. Basically, circular convolution is just the way to convolve periodic signals. As you can guess, linear convolution only makes sense for finite length signals, that do not span from minus infinity to infinity. In our case, in the context of Fourier analysis, our signals are periodic therefore do not satisfy this condition. We can’t talk about (linear) convolution.

Yet we still can intuit a linear-convolution-like operation on our periodic signals : just convolve the periodic signal on a one-period length. That’s what circular convolution does : it convolves 2 periodic signals of the same length along a one-period span.

To further convince yourself of the difference, compare both formulas for discrete linear convolution and discrete circular convolution :

Notice the differences :

bounds : linear convolution uses samples from minus-infinity to plus infinity — as stated previously, in this context x and y have finite energy the sum makes sense. For the circular convolution, we only need to what happened in a period span, so the sum only spans one period

circular indexes : in the circular convolution, we “wrap” the index of y using a modulo operation with a length of N. That’s just a way to ensure that y is considered periodic with a period of N : when we want to know the value of y at position k, we just use the value of y at position k%N — since y is N periodic, we get the right value. Again, this is just a mathematical way to handle periodic infinite-length sample sequences.

Numpy provides great tools for finite length signals: and that’s a good news because as we just saw, our infinite-length periodic signal can be represented with just a period.

Let’s create a simple class to represent such signals. We add a method to quickly plot the array, as well as an additional period before and after the “base” array, to keep in mind that we are dealing with a periodic sequence.