5
$\begingroup$

I'm a little confused... I always thought the DFT of a convolution was equal to a product of DFTs, but when I tried this in Python:

from scipy import *

a = [1+0j, 2+0j]
b = [4+0j, 5+0j]

print list(ifft(fft(a) * fft(b)))
print list(convolve(a, b))

I got back:

[(14+0j), (13+0j)]
[(4+0j), (13+0j), (10+0j)]

Why are they not the same thing?

$\endgroup$
  • $\begingroup$ You could just use fftconvolve $\endgroup$ – endolith Sep 24 '12 at 16:35
  • $\begingroup$ @endolith: That returns the same thing as convolve. $\endgroup$ – Mehrdad Sep 24 '12 at 17:26
  • $\begingroup$ Isn't that what you want? You're trying to use FFTs to calculate the same output as convolve, which is exactly what fftconvolve does. $\endgroup$ – endolith Sep 24 '12 at 17:28
  • $\begingroup$ possible duplicate of Efficiently calculating autocorrelation using FFTs $\endgroup$ – endolith Sep 24 '12 at 17:29
  • $\begingroup$ @endolith: I'm not asking how to calculate anything; did you read the question? $\endgroup$ – Mehrdad Sep 25 '12 at 8:14
16
$\begingroup$

ifft(fft(a) * fft(b)) performs a cyclic convolution, convolve apparently zero-pads the inputs. If you pad both arrays with zeros, the result should be the same:

a = [0,0,0,1+0j, 2+0j,0,0,0]
b = [0,0,0,4+0j, 5+0j,0,0,0]

print list(ifft(fft(a) * fft(b)))
print list(convolve(a, b))
$\endgroup$
  • $\begingroup$ numpy.core.numeric.convolve uses numpy.core.numeric.multiarray.correlate (correlation via shifted dot products) with the 2nd array time reversed. It doesn't use the FFT, so it preserves the array type according to the highest priority of the two arrays, as long as the type has a dot function defined. $\endgroup$ – eryksun Sep 27 '12 at 12:12

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.