# Q8 – Convolution and Fourier Transform

Contributed by Louis-Guillaume Gagnon

1.  Consider a convolution operation over continuous functions: $s(t) = \int_{-\infty}^\infty x(a)w(t - a)da$. Using the definition of the Fourier transform $F(k) = \int_{-\infty}^\infty f(x)e^{-2i\pi k x}dx$ and its inverse $f(x) = \int_{-\infty}^\infty F(k)e^{2i\pi k x}dk$, show that taking the inverse transform of the product of two fourier-transformed functions yields the convolution of these functions in their original domain.
2. For discrete functions over a finite domain, what is the time complexity of the regular, time-domain-only convolution operation? What is the time complexity of a convolution implemented using the Fourier transform?
3. Using the programming language of your choice (e.g. python with numpy), empirically verify your results of 2).

## 2 thoughts on “Q8 – Convolution and Fourier Transform”

1. Hint for Q1 : Try to prove that the product of two Fourier transform F(f).F(g) is equal to the Fourier transform of the convolution f*g (i.e F(f).F(g) = F(f*g)). For this, use Fubini Theorem and then make the change of variable y = x – a

Concerning Q2, I am waiting for someone who know the answer because I think mine is false.

Like

2. gagnonlg says:

For Q2: the goal here is to realize that the naive approach to Fourier-transform convolution is still O(n^2), but that there exists clever fast Fourier transform algorithms: https://en.wikipedia.org/wiki/Fast_Fourier_transform. There maybe should be a hint given to this effect, since deriving a O(n log n) Fourier transform algorithm is out of the scope of this class.

Like