ABSTRACT
In signal processing, filters are used to modify a signal in some desired way – for example, to cut off the high frequencies. Imagine you have the Fourier-transformed representation of a time series; meaning, a set of frequencies with associated magnitudes and phases. From the way I've described the output view, you may well think there's not much to say about how to code this. It looks straightforward: Loop over the input vector, and compute the dot product at every prospective output position. But that would mean calculating many vector products, the more, the longer the input sequence. The way two-dimensional convolution is actually implemented in code again involves Toeplitz matrices.
