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 ...
