## Convolution as Multiplication in Fourier domain

Let $X$, $K$ be $m \times n$ matrices. The convolution of $X$ and $K$ is equivalent to element-wise multiplying them in Fourier domain:

$$K \ast X = f^{-1}(f(K) \cdot f(X))$$

$f$ is the 2D Fourier transform function:

$$f(A) = \mathcal{F}_m^{T} A \mathcal{F}_n$$ and $\mathcal{F}^{T}$ is the conjugate transpose of the $t \times t$ Fourier matrix $\mathcal{F}_t$.

$f^{-1}$ is the inverse function of $f$:

$$f^{-1}(A) = \mathcal{F}_m A \mathcal{F}^{T}_n$$