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).

 

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s