Convolutions and Correlations

Convolution and correlation are central to many kinds of operations on lists of data. They are used in such areas as signal and image processing, statistical data analysis, and approximations to partial differential equations, as well as operations on digit sequences and power series.

In both convolution and correlation the basic idea is to combine a kernel list with successive sublists of a list of data. The convolution of a kernel (Subscript[K, r]) with a list (Subscript[u, s]) has the general form (∑_r)(Subscript[K, r])(Subscript[u, s-r]), while the correlation has the general form (∑_r)(Subscript[K, r])(Subscript[u, s+r]).

Convolution and correlation of lists.

This forms the convolution of the kernel {x,y} with a list of data:

ListConvolve[{x,y},{a,b,c,d,e}]

This forms the correlation:

ListCorrelate[{x,y},{a,b,c,d,e}]

In this case reversing the kernel gives exactly the same result as (RefLink[ListConvolve, paclet:ref/ListConvolve]):

ListCorrelate[{y,x},{a,b,c,d,e}]

This forms successive differences of the data:

ListCorrelate[{-1,1},{a,b,c,d,e}]

In forming sublists to combine with a kernel, there is always an issue of what to do at the ends of the list of data. By default, (RefLink[ListConvolve, paclet:ref/ListConvolve]) and (RefLink[ListCorrelate, paclet:ref/ListCorrelate]) never form sublists which would "overhang" the ends of the list of data. This means that the output you get is normally shorter than the original list of data.

With an input list of length 6, the output is in this case of length 4:

ListCorrelate[{1,1,1},Range[6]]

In practice one often wants to get output that is as long as the original list of data. To do this requires including sublists that overhang one or both ends of the list of data. The additional elements needed to form these sublists must be filled in with some kind of "padding". By default, the Wolfram Language takes copies of the original list to provide the padding, thus effectively treating the list as being cyclic.

Controlling how the ends of the list of data are treated.

The default involves no overhangs:

ListCorrelate[{x,y},{a,b,c,d}]

The last term in the last element now comes from the beginning of the list:

ListCorrelate[{x,y},{a,b,c,d},1]

Now the first term of the first element and the last term of the last element both involve wraparound:

ListCorrelate[{x,y},{a,b,c,d},{-1,1}]

In the general case (RefLink[ListCorrelate, paclet:ref/ListCorrelate])[kernel,list,{(Subscript[k, L]),(Subscript[k, R])}] is set up so that in the first element of the result, the first element of list appears multiplied by the element at position (Subscript[k, L]) in kernel, and in the last element of the result, the last element of list appears multiplied by the element at position (Subscript[k, R]) in kernel. The default case in which no overhang is allowed on either side thus corresponds to (RefLink[ListCorrelate, paclet:ref/ListCorrelate])[kernel,list,{1,-1}].

With a kernel of length 3, alignments {-1,2} always make the first and last elements of the result the same:

ListCorrelate[{x,y,z},{a,b,c,d},{-1,2}]

For many kinds of data, it is convenient to assume not that the data is cyclic, but rather that it is padded at either end by some fixed element, often 0, or by some sequence of elements.

Controlling the padding for a list of data.

This pads with element p:

ListCorrelate[{x,y},{a,b,c,d},{-1,1},p]

A common case is to pad with zero:

ListCorrelate[{x,y},{a,b,c,d},{-1,1},0]

When the padding is indicated by {p,q}, the list {a,b,c} overlays {…,p,q,p,q,…} with a p aligned under the a:

ListCorrelate[{x,y,z},{a,b,c},{-1,1},{p,q}]

Different choices of kernel allow (RefLink[ListConvolve, paclet:ref/ListConvolve]) and (RefLink[ListCorrelate, paclet:ref/ListCorrelate]) to be used for different kinds of computations.

This finds a moving average of data:

ListCorrelate[{1,1,1}/3,{a,b,c,d,e}]

Here is a Gaussian kernel:

kern=Table[Exp[-n^2/100]/Sqrt[2. Pi],{n,-10,10}];

This generates some "data":

data=Table[BesselJ[1,x]+0.2 RandomReal[],{x,0,10,.1}];

Here is a plot of the data:

ListPlot[data]

This convolves the kernel with the data:

ListConvolve[kern,data];

The result is a smoothed version of the data:

ListPlot[%]

You can use (RefLink[ListConvolve, paclet:ref/ListConvolve]) and (RefLink[ListCorrelate, paclet:ref/ListCorrelate]) to handle symbolic as well as numerical data.

This forms the convolution of two symbolic lists:

ListConvolve[{a,b,c},{u,v,w},{1,-1},0]

The result corresponds exactly with the coefficients in the expanded form of this product of polynomials:

Expand[(a+b x+c x^2)(u+v x+w x^2)]

(RefLink[ListConvolve, paclet:ref/ListConvolve]) and (RefLink[ListCorrelate, paclet:ref/ListCorrelate]) work on data in any number of dimensions.

This imports image data from a file:

g=ReadList["ExampleData/fish.data",Number,RecordLists->True];

Here is the image:

Graphics[Raster[g]]

This convolves the data with a two-dimensional kernel:

ListConvolve[{{1,1,1},{1,-8,1},{1,1,1}},g];

This shows the image corresponding to the data:

Graphics[Raster[%]]