in

Fourier Remodel for Time Sequence: Quick Convolution Defined with numpy | by Yoann Mocquin | Jul, 2023

Implementation from scratch vs numpy

The Fourier rework algorithm is taken into account one of many best discoveries in all of arithmetic. French mathematician Jean-Baptiste Joseph Fourier laid the muse for harmonic evaluation in his e-book “Théorie analytique de la chaleur” in 1822. Right this moment, the Fourier rework and all its variants kind the premise of our trendy world, powering applied sciences like compression, communication, picture processing.

This excellent framework additionally supplies nice instruments for analysing time-series… and that’s why we’re right here!

This submit is a part of a collection on the Fourier rework. Right this moment we are going to speak about convolution and the way the Fourier rework supplies the quickest method you are able to do it.

All figures and equations are made by the writer.

Let’s begin with fundamental definitions. The discrete Fourier rework for a discrete time sequence x of N parts is :

the place okay denotes the k-th frequency of the spectrum of x. Observe that some writer add a scaling issue of 1/N to that definition, however is just not of nice significance for this submit — all in all it’s only a matter of definition and sticking it to it.

The inverse Fourier rework is then (given the definition for the ahead Fourier rework):

That being mentioned, some of the vital theorem on Fourier rework is that convolution in a single area is equal to multiplication within the different. In different phrases, the Fourier rework of a product is the convolution of the respective Fourier spectra, and the Fourier rework of a convolution is the product of the respective Fourier spectra.

and

the place the dot represents the usual product (multiplication) and the circled star represents round convolution.

Two vital notes:

• Periodic sign : Fourier evaluation framework take into account that the indicators we deal with are periodic. In different phrases, they repeat from minus infinity to infinity. Nonetheless it isn’t all the time sensible to deal with such indicators with a finite reminiscence pc, so we solely “play” with one interval, as we are going to see hereafter.
• Round convolution : The convolution theorem states that multiplication is equal to circulation convolution, which is a bit completely different from linear convolution, which we’re extra accustomed to. As we are going to see, it isn’t that completely different, and never that difficult both.

If you happen to’re accustomed to linear convolution, typically merely known as ‘convolution’, you gained’t be confused by round convolution. Mainly, round convolution is simply the best way to convolve periodic indicators. As you’ll be able to guess, linear convolution solely is sensible for finite size indicators, that don’t span from minus infinity to infinity. In our case, within the context of Fourier evaluation, our indicators are periodic subsequently don’t fulfill this situation. We will’t speak about (linear) convolution.

But we nonetheless can intuit a linear-convolution-like operation on our periodic indicators : simply convolve the periodic sign on a one-period size. That’s what round convolution does : it convolves 2 periodic indicators of the identical size alongside a one-period span.

To additional persuade your self of the distinction, examine each formulation for discrete linear convolution and discrete round convolution :

Discover the variations :

bounds : linear convolution makes use of samples from minus-infinity to plus infinity — as said beforehand, on this context x and y have finite vitality the sum is sensible. For the round convolution, we solely must what occurred in a interval span, so the sum solely spans one interval

round indexes : within the round convolution, we “wrap” the index of y utilizing a modulo operation with a size of N. That’s only a method to make sure that y is taken into account periodic with a interval of N : once we need to know the worth of y at place okay, we simply use the worth of y at place kpercentN — since y is N periodic, we get the correct worth. Once more, that is only a mathematical strategy to deal with periodic infinite-length pattern sequences.

Numpy supplies nice instruments for finite size indicators: and that’s a excellent news as a result of as we simply noticed, our infinite-length periodic sign will be represented with only a interval.

Let’s create a easy class to characterize such indicators. We add a technique to shortly plot the array, in addition to a further interval earlier than and after the “base” array, to remember that we’re coping with a periodic sequence.