1
$\begingroup$

As stated by the convolution theorem, a convolution in spatial domain is equivalent to a
multiplication in the frequency domain.Nevertheless, when should the first be preferred over the latter?

$\endgroup$
1
$\begingroup$

It is very broad question. But few things to remember:

  • convolution in time domain is the linear convolution.
  • convolution in frequency domain with usage of DFT is a circular convolution, that's because DFT 'repeats' your signal - assumes it is periodic.

Additionally convolution in time domain is slower than one in frequency domain. It is therefore preferred to do it by FFT. For that case we are using algorithms such as overlap-add and overlap-save. These are widely used for performing of fast filtering or correlation calculation.

$\endgroup$
1
$\begingroup$

If your data is originally in the time or spatial domain, converting that data into the frequency domain and back has costs (in computational cycles, energy, etc., possibly including some added costs due to any needed zero-padding). There is also added latency due to both the conversion(s), plus waiting for enough data to make the FFT/IFFT block conversions for overlap-add/save fast-convolution more efficient.

If the convolution is short enough, it might cost less (in MACs, cycles, energy, etc.) than the above conversion(s) to do the convolution directly in the time or spatial domain. And direct convolution can be done on a per-sample basis, potentially minimizing latency by a significant amount, compared to block-based FFT/IFFTs.

$\endgroup$
  • $\begingroup$ thank you for the reply. So if the convolution is long(large matrix and kernel size) enough it is better do it in frequency domain due to complexity in time domain, even though the cost involoved is high in frequency domain. $\endgroup$ – blues Jun 25 '14 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.