Convolutions and Fourier Transforms
Contents
Convolutions and Fourier Transforms¶
A convolution is a linear operator of the form \begin{equation} (f \ast g)(t) = \int f(\tau) g(t - \tau ) d\tau \end{equation} In a discrete space, this turns into a sum \begin{equation} \sum_\tau f(\tau) g(t - \tau) \end{equation}
Convolutions are shift invariant, or time invariant. They frequently appear in temporal and spatial image processing, as well as in probability.
If we want to represent the discrete convolution operator as a matrix, we get a toeplitz matrix
A circulant matrix acting on a discrete signal of length
both toeplitz and circulant matrices have special solve
function in scipy.linalg
Example¶
One place where convolutions appear is in combining probability distributions. For instance, if we take a sample
Fourier Transforms¶
A Fourier transform takes functions back and forth between time and frequency domains. \begin{equation} \hat{f}(\omega) = \int_{-\infty}^\infty f(x) e^{-2\pi i x \omega} dx \end{equation}
A discrete Fourier transform (DFT) operates on a signal represented as a finite dimensional vector. On a signal of length
\begin{equation} \hat{f}k = \frac{1}{N} \sum{n=0}^{N-1} f_n e^{-2\pi i k n / N} \end{equation}
In practice, discrete Fourier transforms are often computed using the Fast Fourier Transform (FFT) algorithm, which runs in

the function in frequency space typically has real and imaginary components.

real-valued signals should have anti-symmetric complex components and symmetric real components.
Fourier transforms can reveal a variety of useful information and have many useful properties. One of which is that convolutions in the time/spatial domain become pointwise multiplication in the frequency domain.
\begin{equation} h = f \ast g \Leftrightarrow \hat{h} = \hat{f} \hat{g} \end{equation}
This means that circulant matrices and their inverses can be applied in
Exercise 2¶
Let
Given that the inverse of a circulant matrix can also be applied using a Fourier transform, is
Write a function to compute the inverse of
Higher Dimensions¶
In 2 dimensions, you can use scipy’s fft2
and ifft2
for 2-dimensional signals such as images. For an
For general image processing, you may find it useful to install scikit-image
Sparse Convolutions¶
In image processing, you may often encounter sparse convolutions, particularly convolutions that are very localized (e.g. only the first few entries of the firs row c
are nonzero). One example is that many camera lenses cause a slight blur which mixes light from nearby sources. In deep learning, these sparse convolutions have been very effective in image processing tasks. Perhaps the simplest explanation of why learning parameters for a convolution is a good idea in this situation is that convolutions are translation invariant allowing the neural net to learn regardless of where a target appears on an image.
In this case, we typically think of convolutions as
The time complexity of applying this convolution using standard for-loops to a
If you’re using this sort of convolution in PyTorch, you can use torch.nn.Conv2d
or torch.conv2d
Discrete Cosine Transform (DCT)¶
One of the potential annoyances with Fourier transforms is that even with real-valued signals they produce complex output. If you want to stick to real output with a similar interpretation, you can use the Discrete Cosine Transform (DCT) or Discrete Sine Transform (DST). Both are implemented in Scipy.


The DCT can also be used for a simple method of image compression - you can simply remove the high frequency componenents of an image and retain most of the large structure while losing some detail.
Now, we’ll cut out the highest-frequency DCT coefficients.

alternatively, we can make the image the original size by just setting the high-frequency DCT coefficients to 0.

Now, let’s really compress the image…