Convolution in Spatial Domain Is Multiplication in Frequency Domain

Question

I have to prove convolution in spatial domain is equivalent to multiplication in frequency domain using two matrices.

$$ x(m, n) = \begin{bmatrix} 1 && 2 \\ 3 && 4 \end{bmatrix} $$

$$ h(m, n) = \begin{bmatrix} 1 && 0 \\ 0 && 0 \end{bmatrix} $$

When I used matrix method, I got the following result

$$ \begin{bmatrix} 1 && 2 && 0 \\ 3 && 4 && 0 \\ 0 && 0 && 0 \end{bmatrix} $$

But when I converted both to DFT using the kernel

$$ \begin{bmatrix} 1 && 1 \\ 1 && -1 \end{bmatrix} $$

and multiply the result, I get

$$ \begin{bmatrix} 1 && 2 \\ 3 && 4 \end{bmatrix} $$

They are not equal. The dimensions are not matching. The first one is $3\times 3$ while the second one is $2\times 2$. Am I doing it correct? Is there something I am missing?

Answer 1

For finite size arrays, multiplication in the frequency domain is equivalent to circular convolution in the time domain, not linear convolution. (Is that toroidal convolution in the 2D case?)

Note that with sufficient zero-padding, the results of circular convolution and linear convolution end up identical.

Answer 2

The problem is not only the dimensions, you tested it with filter of single Tap (only the first element is different from 0). If you use general filter you will see that the values are also different and not only the dimensions. In the same manner that you pad the one dimension vectors before transferring to the frequency domain >> and multiplication in freq domain >> and then inverse transform >> and then droping the extra elements, In 2D each dimension need to be pad according to its supporting length (twice-1 at minimum)