This blog is a continuation of my previous blog Advantages of FCNN Over CNN – Part 1
Computational complexity in the Fourier domain is less expensive than in the spatial domain, as I explained in my previous blog. Now, in this blog, I would like to talk about how spatial domain convolution is equivalent to Fourier domain multiplication, as well as a python example of O(T) reduction.
1. How is the convolution of the spatial domain equivalent to the multiplication of the Fourier domain?
The convolution theorem states that under suitable conditions, the Fourier transform of a convolution of two functions or signals is the pointwise product of their Fourier transforms.
Mathematically, a convolution is defined as the integral over all space of one function at x times another function at x-τ. Where g is the output of the convolution operation and f is convolving h in the spatial domain.
Proof of the Convolution Theorem
To prove the convolution theorem, in one of its statements, we start by taking the Fourier transform of a convolution. What we want to show is that this is equivalent to the product of the two individual Fourier transforms.
G(u) is the Fourier transform of g(x), we substitute g(x) in the equation and now we end up with a double integral equation looking like the below.
Now, we are going to replace u with u+τ-τ, which is the same thing as e, but it allows us to separate out the above expression into a product of two integrals.
Let us look at the first integral which is the Fourier transform of f(x), if you look at the second integral, we can choose any variable inside the integral, hence we can substitute x-τ with any other variable so that we can define the second integral is Fourier transform of h(x).
Therefore, we can write the above equation as follows:
Now, we have the convolution of f(x) and h(x) in the spatial domain corresponding to the multiplication of f(u) with h(u) in the Fourier domain.
Using the same approach, you can also show the product of two functions in the spatial domain is equal to the convolution of the spatial domain.
2. An example of Reduction in O(T):
We have seen that according to the convolution theorem, convolution in the spatial domain is equivalent to multiplication in the frequency domain. The computational complexity for a K x K convolution kernel implemented in the spatial domain on an image of N x N is O(K2) where the complexity is measured per pixel on the basis of the number of multiplies-and-adds (MADDs) and the computational complexity per pixel of the Fourier approach for an image of N x N and for a convolution kernel of K x K is O(logN) complex MADDs independent of K.
Here is the python implementation of discrete convolution and FFT.
Performance comparison between FFT and normal discrete convolution
⦁ The np.convolve function will be used to compute the normal linear convolution of two vectors and signal.fftconvolve will be used to compute FFT convolution.
⦁ %timeit jupyter notebook function was used to calculate the time required by each of the given 2 functions.
You can see that the time taken to generate the FFT output is 100 times less than the normal convolution.