Fourier Space Filtering
Filtering in real space can be represented by the following relationship:
Where $x$ is the filter, and $C$ is a circulant matrix constructed using the input image. For a simple example let us assume the input image and filter are 1D. The matrix $C$ is constructed by shifting the image periodically once at each row. Notice below the 1D image starts with the green pixel and ends with the red, and repeatedly shifted to produce the matrix $C$. The vectors corresponding to these shifts are illustrated to the left. Convince yourself the multiplication in the image below is equivalent to filtering of the 1D image at the first row of the matrix with the yellow filter.
Any circulant matrix can be diagonalized by the Fourier matrix F as:
This fact can be exploited to achieve multiplication of a vector with in O(nlogn) time using FFT. The following scheme can be used for this purpose, where is the first column and is a vector containing the main diagonal of :
where is element-wise multiplication. Notice the above algortihm is actually the Convolution Theorem in disguise, where is the Fourier Transform operator:
The mirror mismatch between convolution and correlation operations can be accounted for by conjugation of the filter in Fourier space.