How to understand the process of ListCorrelate when it in two-dimensional condition?

Toady,I learn a function ListCorrelate,and I can understand process of execution his result in one-dimensional. However,the documentation gives a two-dimensional correlation example(shown as below)

ListCorrelate[{{1, 1}, {1, 1}}, {{a, b, c}, {d, e, f}, {g, h, i}}]


{{a + b + d + e, b + c + e + f}, {d + e + g + h, e + f + h + i}}

To understand it,I replace {{1,1},{1,1}} to {{u,v},{x,y}}.

ListCorrelate[{{u, v}, {x, y}}, {{a, b, c}, {d, e, f}, {g, h, i}}]


{{a u + b v + d x + e y, b u + c v + e x + f y}, {d u + e v + g x + h y, e u + f v + h x + i y}}

My trail to figure out how his result be generate:

I think two-dimensional correlation is the composition of two one-dimensional correlations, but,unfortunately, from the results that Mathematica executes it is not what I think.

ListCorrelate[{{u, v}}, {{a, b, c}, {d, e, f}, {g, h, i}}]


{{a u + b v, b u + c v}, {d u + e v, e u + f v}, {g u + h v, h u + i v}}

ListCorrelate[{{x, y}}, {{a, b, c}, {d, e, f}, {g, h, i}}]


{{a x + b y, b x + c y}, {d x + e y, e x + f y}, {g x + h y, h x + i y}}

Question:

How to understand the process of ListCorrelate when it in two-dimensional condition?

The intuitive way to understand ListCorrelate is that the kernel is "moved" to every position in the array, and the sum of the products between the kernel values and the array values at that position is stored in the output array:

(if the kernel is separable, i.e. if there are two 1d kernels so that Transpose[{k1}] . {k2} == k2d, then ListCorrelate can be understood as the composition of two 1d correlations. But not every kernel is separable.)

Description

Today, I know this resourse http://library.wolfram.com/infocenter/MathSource/4557/ accidentally, in this notebook, I find the detailed useage of ListCorrelate,so I post here to share to more Mathematica user that need to improve their capability.

Hope

I hope sincerely others to edit and check it to make it complete and correct.

Statement

Author Ted Ersek

https://mathematica.stackexchange.com/users/460/ted-ersek

The copyright belongs to the original author

Main Tutorial

The next cell demonstrates the basic use of ListCorrelate.

Clear["Global*"];
ListCorrelate[{a1,a2,a3,a4},{b1,b2,b3,b4,b5,b6}]


{{a1 x1 + a2 x2 + a3 x3 + b1 y1 + b2 y2 + b3 y3 + c1 z1 + c2 z2 + c3 z3}}

Next we see that ListCorrelate is equivalent to flattening the result of a certain matrix product.

True

• Specifying the "overhang" using ${K_L,K_R}$

In the next cell we provide ListCorrelate {-1,-1} as a third argument.

ListCorrelate[{a1,a2,a3,a4},{b1,b2,b3,b4,b5,b6},{-1,-1}]


{a4 b1+a1 b4+a2 b5+a3 b6,a3 b1+a4 b2+a1 b5+a2 b6,a2 b1+a3 b2+a4 b3+a1 b6,a1 b1+a2 b2+a3 b3+a4 b4,a1 b2+a2 b3+a3 b4+a4 b5,a1 b3+a2 b4+a3 b5+a4 b6}

The previous example is equivalent to the matrix product in the next cell. Here we have the last element of {a1, a2, a3, a4} in the upper left position of the left matrix.. We also have the last element of {a1, a2, a3, a4} in the lower right position of the left matrix. The (-1) indicates last element of {a1, a2, a3, a4}, and (-2) would indicate the second from the last element of {a1, a2, a3, a4}.

In the next cell we provide ListCorrelate {1,1} as a third argument.

ListCorrelate[{a1,a2,a3,a4},{b1,b2,b3,b4,b5,b6},{1,1}]


{a1 b1+a2 b2+a3 b3+a4 b4,a1 b2+a2 b3+a3 b4+a4 b5,a1 b3+a2 b4+a3 b5+a4 b6,a4 b1+a1 b4+a2 b5+a3 b6,a3 b1+a4 b2+a1 b5+a2 b6,a2 b1+a3 b2+a4 b3+a1 b6}

The previous example is equivalent to the matrix product in the next cell. Here we have the first element of {a1, a2, a3, a4} in the upper left position of the left matrix.. We also have the first element of {a1, a2, a3, a4} in the lower right position of the left matrix. The (1) indicates first element of {a1, a2, a3, a4}, and (2) would indicate the second element of {a1, a2, a3, a4}.

In the next cell we provide ListCorrelate {1,-1} as a third argument.

 ListCorrelate[{a1,a2,a3,a4},{b1,b2,b3,b4,b5,b6},{1,-1}]


{a1 b1+a2 b2+a3 b3+a4 b4,a1 b2+a2 b3+a3 b4+a4 b5,a1 b3+a2 b4+a3 b5+a4 b6}

The previous example is equivalent to the matrix product in the next cell. Here we have the first element of {a1, a2, a3, a4} in the upper left position of the left matrix.. We also have the last element of {a1, a2, a3, a4} in the lower right position of the left matrix. The (1) indicates first element of {a1, a2, a3, a4}, and (-1) indicates the last element of {a1, a2, a3, a4}.

In the next cell we provide ListCorrelate {-1,1} as a third argument. Notice this gives the same result as ListCorrelate[{a1,a2,a3,a4},{b1,b2,b3,b4,b5,b6}] (ie. {-1,1} is the default for the third argument).

ListCorrelate[{a1,a2,a3,a4},{b1,b2,b3,b4,b5,b6},{-1,1}]


{a4 b1+a1 b4+a2 b5+a3 b6,a3 b1+a4 b2+a1 b5+a2 b6,a2 b1+a3 b2+a4 b3+a1 b6,a1 b1+a2 b2+a3 b3+a4 b4,a1 b2+a2 b3+a3 b4+a4 b5,a1 b3+a2 b4+a3 b5+a4 b6,a4 b1+a1 b4+a2 b5+a3 b6,a3 b1+a4 b2+a1 b5+a2 b6,a2 b1+a3 b2+a4 b3+a1 b6}

Length[%]


9

The previous example is equivalent to the matrix product in the next cell. Here we have the last element of {a1, a2, a3, a4} in the upper left position of the left matrix.. We also have the First element of {a1, a2, a3, a4} in the lower right position of the left matrix. The (1) indicates first element of {a1, a2, a3, a4}, and (-1) indicates the last element of {a1, a2, a3, a4}.

ListCorrelate with matrices

m1 = {{a1, a2, a3}, {b1, b2, b3}, {c1, c2, c3}}
m2 = {{x1, x2, x3}, {y1, y2, y3}, {z1, z2, z3}}
ListCorrelate[m1, m2]


True

The next cell shows how the same ListCorrelate can be done as Dot products on parts of the matrices.

 ListCorrelate[m1,m2]=== {{Part[m1,1].Part[m2,1]+Part[m1,2].Part[m2,2]+Part[m1,3].Part[m2,3]}}


True

We can give ListCorrelate a level specification as a 7$^{th}$ argument. The next cell shows that level (2) is the default specification when working on matrices.

ListCorrelate[m1,m2]===ListCorrelate[m1,m2,{1,-1},m2,Times,Plus,2]


True

In the next cell we give ListCorrelate the integer (1) as a level specification.

 ListCorrelate[m1,m2,{1,-1},m2,Times,Plus,1]


{{a1 x1+b1 y1+c1 z1,a2 x2+b2 y2+c2 z2,a3 x3+b3 y3+c3 z3}}

The next cell shows how the same ListCorrelate can be done as Dot products on parts of the matrices.

mat1=Transpose[m1];
mat2=Transpose[m2];

ListCorrelate[m1,m2,{1,-1},m2,Times,Plus,1]===
{{Part[mat1,1].Part[mat2,1],Part[mat1,2].Part[mat2,2],Part[mat1,3].Part[mat2,3]}}


True

The next cell shows two ways of expressing the default for the third argument of ListCorrelate when working with matrices.

ListCorrelate[m1,m2]===ListCorrelate[m1,m2,{1,-1}]===ListCorrelate[m1,m2,{{1,1},{-1,-1}}]


True

• Er… Why the output of the 4th picture is False? And where's the introduction for the usage of the 4th argument? Sep 19 '14 at 5:18
• @xzczd,Looking at verbeia.com/mathematica/tips/HTMLLinks/Tricks_L-O_4.html
– xyz
Sep 19 '14 at 5:31
• I just checked it, and found it confusing, if I understood the document well, the output should be True`. Also, I think it'll be better to paste the part about the 4th argument here, or simply cut off the part below Generalizing beyond Times, Plus in your post, anyway, it's no longer related to your specific question. Sep 19 '14 at 5:41
• @xzczd, OK,I will edit right now.
– xyz
Sep 19 '14 at 6:43
• I just post a separate question for the confusing statement in Ted's document, you can have a look: mathematica.stackexchange.com/q/60101/1871 Sep 19 '14 at 9:07