Contributed by Louis-Guillaume Gagnon

- Consider a convolution operation over continuous functions: . Using the definition of the Fourier transform and its inverse , show that taking the inverse transform of the product of two fourier-transformed functions yields the convolution of these functions in their original domain.
- 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?
- Using the programming language of your choice (e.g. python with numpy), empirically verify your results of 2).

### Like this:

Like Loading...

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.

LikeLike

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.

LikeLike