How do I understand ListCorrelate(contains $\{k_L,k_R\}$) when it works for 2-dimensional data?

Question

Two months ago, I asked a question here

And @nikie give me a solution:

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:

I make a graphic to show this process as shown below:

However, I cannot understand this built-in function (contain $\{K_L,K_R\}$) when it works for 2-dimensional data.

For example,

$\{K_L,K_R\}=\{2,2\}$

ListCorrelate[
  {{x, y, z}, {u, v, w}}, 
  {{a, b, c, d}, {e, f, g, h}, {i,j, k, l}},
  {2, 2}]

$\{K_L,K_R\}=\{2,3\}$ or $\{K_L,K_R\}=\{1,3\}$ or $\{K_L,K_R\}=\{-1,3\}$

According this result, I figure the picture:

However, I cannot find the regulation, namely, how does ListCorrelate pad?

Update

Thanks for @DumpsterDoofus's solution, I know how the ListCorrelate work in 1-dimensional data when it contains ${k_L,k_R}$ (as shown below)

the ListCorrelate work in 1-dimensional data when it contains $\{k_L,k_R\}$

And now my main confusion is ListCorrelate works in 2-dimensional data.

Is there a analogous graphic to show the process in 2-dimensional data?

Answer 1

$K_L$ and $K_R$ represent positions in the kernel, specifically the positions of the kernel elements that overlap the first and last array elements. Here's an example showing the correlation of a 5×5 array with a 2×3 kernel, with each element of the result showing the overlapping kernel position. The array is in red and the kernel in grey. Here we are using the default "no-overhang" values KL={1,1} and KR={-1,-1} (note that the positions are lists of length 2, as we are specifying a position in a 2D kernel. When we use KL=1 that's just a shorthand for KL={1,1})

Referring to the image above, we can see that in the top left corner, the kernel element {1,1} (KL) overlaps the top left element of the array. And in the bottom right corner the kernel element {-1,-1} (KR) overlaps the bottom right element of the array.

Now suppose we want a 2D correlation where the kernel overhangs by one element on the left hand side. Like this:

What should KL and KR be to get this? Look at the top left corner - the kernel element {1,2} is overlapping the top left element of the array, so we need KL={1,2}. And in the bottom right corner kernel element {-1,-1} overlaps the bottom right array element so we still have KR={-1,-1}.

Hopefully it will be no surprise that KL=-1, KR=1 gives "maximal overhang" on all sides. This is shorthand for KL={-1,-1} and KR={1,1}, so the kernel element {-1,-1} overlaps in the top left and element {1,1} overlaps in the bottom right:

The padding option just determines how to deal with the parts of the kernel that hang outside of the array. You can imagine the array surrounded by zeros or by copies of itself (the default "periodic" padding) or whatever other values you specify. But for understanding KL and KR forget the padding and just look at which kernel elements overlap the first and last array elements.

Answer 2

It becomes slightly easier if you look at 1-dimensional data first. Here's an example:

KER = Table[k[i], {i, 5}];
LIST = Table[l[i], {i, 8}];
ListCorrelate[KER, LIST, {2, 4}]

which produces:

{k[2] l[1] + k[3] l[2] + k[4] l[3] + k[5] l[4] + k[1] l[8], 
 k[1] l[1] + k[2] l[2] + k[3] l[3] + k[4] l[4] + k[5] l[5], 
 k[1] l[2] + k[2] l[3] + k[3] l[4] + k[4] l[5] + k[5] l[6], 
 k[1] l[3] + k[2] l[4] + k[3] l[5] + k[4] l[6] + k[5] l[7], 
 k[1] l[4] + k[2] l[5] + k[3] l[6] + k[4] l[7] + k[5] l[8], 
 k[5] l[1] + k[1] l[5] + k[2] l[6] + k[3] l[7] + k[4] l[8]}

To understand this output it helps to introduce some notation: given a list $l$ and a kernel $k$ of length $M$, define

$$F(j)=\sum_{\ell=1}^M k_{\ell}l_{\ell+j}$$

where the subscripts are interpreted modulo the length of the corresponding list. We then have

$$\text{ListCorrelate}\left[k,l,\{K_L,K_R\}\right]=\{F(-K_L+1),F(-K_L+2),...,F(K_R)\}.$$

In short, it is a partial cyclic correlation; $K_L$ determines how far to the left the correlation hangs, $K_R$ determines how far right the correlation hangs, and the resulting list has $K_L+K_R$ elements.

In particular, we have the following identity:

$$\text{ListCorrelate}\left[k,l\right]=\text{ListCorrelate}\left[k,l,\{1,M\}\right]$$

which relates the default behavior of ListCorrelate with the behavior with overhang lengths specified.

Answer 3

If you want to understand the built-in function when it contains $\{K_L,K_R\}$

For the example you mention,

$\{K_L,K_R\}=\{2,2\}$

ListCorrelate[
  {{x, y, z}, {u, v, w}}, 
  {{a, b, c, d}, {e, f, g, h}, {i,j, k, l}},
  {2, 2}]

The best way is to split it up in simpler ListCorrelate functions.

ker = {{x, y, z}, {u, v, w}}
list = {{a, b, c, d}, {e, f, g, h}, {i, j, k, l}}

first row of the outcome is generated by starting with $K_L$ which means to start with ker[[2]] , at the position in list after skipping the first correlation of ker[[1]] (in case of a kernel with length 3, this means to start at list position 4). This can easily be shown with:

Total@
   (Flatten@      
      {
       ListCorrelate[ker[[2]], list[[1, {4, 1, 2}]]], 
       ListCorrelate[ker[[1]], list[[3, {4, 1, 2}]]]
      })

Total@
   (Flatten@
      {
       ListCorrelate[ker[[2]], list[[1, {1, 2, 3}]]], 
       ListCorrelate[ker[[1]], list[[3, {1, 2, 3}]]]
       })

Total@
   (Flatten@
      {
       ListCorrelate[ker[[2]],list[[1, {2, 3, 4}]]], 
       ListCorrelate[ker[[1]],list[[3, {2, 3, 4}]]]
      })

Total@
   (Flatten@
      {
       ListCorrelate[ker[[2]], list[[1, {3, 4, 1}]]], 
       ListCorrelate[ker[[1]], list[[3, {3, 4, 1}]]]
      })

(* OUT *)

d u + a v + b w + l x + i y + j z

a u + b v + c w + i x + j y + k z

b u + c v + d w + j x + k y + l z

c u + d v + a w + k x + l y + i z

In this way you I hope can see how the 'list' and 'kernel' are rotated and can expand the example up until the last row which uses $K_R$ = 2, or again ker[[2]].