We will now look at how we can use an FFT to perform convolution. Let's review what exactly convolution is, first: given two one-dimensional vectors, x and y, their convolution is defined as follows:

This is of interest to us because if x is some long, continuous signal, and y only has a small amount of localized non-zero values, then y will act as a filter on x; this has many applications in itself. First, we can use a filter to smooth the signal x (as is common in digital signal processing and image processing). We can also use it to collect samples of the signal x so as to represent the signal or compress it (as is common in the field of data compression or compressive sensing), or use filters to collect features for signal or image recognition in machine learning. This idea forms the basis for convolutional neural networks).

Of course, computers cannot handle infinitely long vectors (at least, not yet), so we will be considering circular convolution. In circular convolution, we are dealing with two length n-vectors whose indices below 0 or above n-1 will wrap around to the other end; that is to say, x[-1] = x[n-1], x[-2] = x[n-2], x[n] = x[0], x[n+1] = x[1], and so on. We define circular convolution of x and y like so:

It turns out that we can perform a circular convolution using an FFT quite easily; we can do this by performing an FFT on x and y, point-wise-multiplying the outputs, and then performing an inverse FFT on the final results. This result is known as the convolution theorem, which can also be expressed as follows:

We will be doing this over two dimensions, since we wish to apply the result to signal processing. While we have only seen the math for FFTs and convolution along one dimension, two-dimensional convolution and FFTs work very similarly to their one-dimensional counterparts, only with some more complex indexing. We will opt to skip over this, however, so that we can get directly into the application.