title: How do I multiply the spectra of two images of different dimensions?
body: <p>This is not a "programming" question. But I'm sure it's something that is widely known and understood in this community.</p>
  
  <p>I have an image, x, and a much smaller image, y, and I need to convolve the two by multiplying their FFTs. But since they are not the same size I don't know how to do the frequency domain multiplication.</p>
  
  <p>I take the (two-dimensional) FFT of x (which is an integer matrix of dimensions 4096 x 4096), which gives me the frequency domain representation, X (which is a matrix of complex numbers and I think it's dimension is 2048 x 2048).</p>
  
  <p>Similarly, I take the (two-dimensional FFT of y (which is an integer matrix of dimension 64 x 64), which gives me the frequency domain representation, Y (which is also a matrix of complex numbers and I think it's dimension is 32 x 32).</p>
  
  <p>I'm using the fourn function in Numerical Recipes, so my input matrices, x and y must be collapsed into one-dimensional arrays, which get replaced by their discrete Fourier transforms, X and Y. The point being that even though this is a two-dimensional problem with images, I am working with one-dimensional arrays.</p>
  
  <p>If I were trying to convolve two images of the exact same dimensions, x and y. It would all be very straightforward:</p>
  
  <pre><code> X = FFT(x)
  
   Y = FFT(y)
  
   Z = X * Y (term by term multiplication)
  
   Convolution of x and y = IFFT(Z)
  </code></pre>
  
  <p>But if X and Y are different lengths, how do I do the multiplication?</p>
  
  <p>One possibility is to pad out y to have the same dimensions as x. But this seems horribly inefficient. Another possibility is to pad out Y to have the same dimensions as X. But I don't know what this means in frequency space.</p>
  
  <p>Here's another way of asking this question: If I want to convolve two images of very different dimensions using FFTs so I can do multiplication of their spectra (frequency domain representation), how do I do that multiplication?</p>
  
  <p>Thanks,</p>
  
  <p>~Michael.</p>