How Do You Resolve Negative Indices in Convolution Calculations?

[AlecYates]

Hey,

I've begun going through a book called "An introduction to geophysical exploration" by Phillip Kearey and Michael Brooks and I've come across a problem I can't for the life of me see how they got their answer.

Essentially, given an input function g_i (i = 1,2... m), and a convolution operator f_j (j = 1,2 ...n) the convolution output is given by:

y_k = $\Sigma$g_if_{k - i} (k = 1,2 ... m + n - 1)

(with Sigma index counter starting at i = 1 and going up to m).

Their example is with an input of g(2,0,1) and operator of f(4,3,2,1) the output is y(8,6,8,5,2,1).

If I'm trying to find y₁ I end up with negative index of f_j as I perform f_{k - i} as i increases from 1 to 3 with the largest index being f₀ (from f_{1 - 1} where k = 1 and i = 1). How can this be correct?

Either way, based on my own understanding and setting impossible indexes as 0, I get:

y₁ = 0
y₂ = 8
y₃ = 6
y₄ = 8
y₅ = 5
y₆ = 2

so my solution is y(0,8,6,8,5,2). Similar to theirs but shifted one place to the right (with 0 occupying the initial y₁).

Any help with where I've gone wrong would be appreciated.

 

[collinsmark]

Hey,

I've begun going through a book called "An introduction to geophysical exploration" by Phillip Kearey and Michael Brooks and I've come across a problem I can't for the life of me see how they got their answer.

Essentially, given an input function g_i (i = 1,2... m), and a convolution operator f_j (j = 1,2 ...n) the convolution output is given by:

y_k = $\Sigma$g_if_{k - i} (k = 1,2 ... m + n - 1)

(with Sigma index counter starting at i = 1 and going up to m).

Their example is with an input of g(2,0,1) and operator of f(4,3,2,1) the output is y(8,6,8,5,2,1).

If I'm trying to find y₁ I end up with negative index of f_j as I perform f_{k - i} as i increases from 1 to 3 with the largest index being f₀ (from f_{1 - 1} where k = 1 and i = 1). How can this be correct?

Either way, based on my own understanding and setting impossible indexes as 0, I get:

y₁ = 0
y₂ = 8
y₃ = 6
y₄ = 8
y₅ = 5
y₆ = 2

so my solution is y(0,8,6,8,5,2). Similar to theirs but shifted one place to the right (with 0 occupying the initial y₁).

Any help with where I've gone wrong would be appreciated.

Yup, their answer is straightforward, linear convolution.

Linear convolution happens all the time in nature, and one needs to deal with it all the time in all sorts of aspects of engineering and physics. [Edit: and statistics too.]

It's not so bad once you get used to it. At the risk of giving "too much help" on this, let me walk you through the beginning. I don't think I'm doing you a disservice by walking you through this, because you'll be doing this same sort of thing over and over again on your own eventually. I'll just try to get you started.

When convolving two functions, you need to take one of the functions and "flip" it. It turns out, it doesn't matter which one you flip, but you need to flip one (and only one) of them, around the first data point (for a continuous, time varying function the flip rotates the function around t = 0. But for this discrete function, we flip at i = 1, the first data point). Traditionally, the second function is flipped, but it really doesn't matter. So let's try this

Original functions:

            2   0   1
            4   3   2   1

Flipping the second function around the first point.

            2   0   1
1   2   3   4

Now to find the first output: we multiply each column, and add the results.

            2   0   1
1   2   3   4
--------------------
            8

So our first output value is 8.

Next, we shift the second function up by 1.

          2   0   1
  1   2   3   4
--------------------
          6 + 0

The second value is 6.


Shifting again for the third output,

          2   0   1
      1   2   3   4
--------------------
          4 + 0 + 4

Which gives 8 for the third value.

And you just keep on shifting,

          2   0   1
          1   2   3   4
------------------------------
          2 + 0 + 3

which gives 5,

And so on (you can finish up the rest). And you just keep on shifting and shifting until there is no more overlap. And that's linear convolution. Flip and shift as you multiply the two functions, summing the results of the multiplication (if it were a continuous function, you'd be integrating rather than summing). And that's all there is to linear convolution.

Now as an exercise, make sense of that with the i and k indexes and your original formula to make sure you understand what the formula is saying.

Edit: As another exercise, flip the first function instead of the second, and make sure you get the same results.

 

[AlecYates]

"Now as an exercise, make sense of that with the i and k indexes and your original formula to make sure you understand what the formula is saying."

Awesome feedback. It's actually the 'exercise' I was having the most issue with, though I appreciate the strong explanation of the method of convolution as it's new to me. I decided I wanted to use the sigma summation method as first point of call as having a mathematical background it seemed quite simple. I'm pretty sure at this stage there is an error in the textbook where...

y_k = $\Sigma$g_if_{k - i} (k = 1,2 ... m + n - 1)

should be...

y_k = $\Sigma$g_if_{k - i + 1} (k = 1,2 ... m + n - 1)

This would give me the desired outcome. With the original y(1) = 0 in all cases, the issue I found.

 

[collinsmark]

"Now as an exercise, make sense of that with the i and k indexes and your original formula to make sure you understand what the formula is saying."

Awesome feedback. It's actually the 'exercise' I was having the most issue with, though I appreciate the strong explanation of the method of convolution as it's new to me. I decided I wanted to use the sigma summation method as first point of call as having a mathematical background it seemed quite simple. I'm pretty sure at this stage there is an error in the textbook where...

y_k = $\Sigma$g_if_{k - i} (k = 1,2 ... m + n - 1)

should be...

y_k = $\Sigma$g_if_{k - i + 1} (k = 1,2 ... m + n - 1)

This would give me the desired outcome. With the original y(1) = 0 in all cases, the issue I found.

This is one of the reasons I like to index things starting the 0 instead of 1. It avoids issues like this.

 

[HalfLostAndSearching]

Hi there,

Thank you for reaching out with your question regarding the Sigma Summation Issue. It seems like you have a good grasp on the concept, but there may be some confusion with the notation used in the example.

In the formula for convolution output, the index counter for Sigma starts at i = 1 and goes up to m. However, in the example given, the input function g(2,0,1) has a length of 3, so the index counter for Sigma would go from i = 1 to 3, not just 1 to 2 as you have calculated.

Also, the convolution operator fj (j = 1,2 ...n) in this case has a length of 4, so the index counter would go from j = 1 to 4, not 1 to 3 as you have calculated.

Taking these adjustments into account, the convolution output would be:

y1 = g1f4 + g0f3 + g2f2 = (2)(1) + (0)(2) + (1)(3) = 5
y2 = g2f4 + g1f3 + g0f2 = (1)(1) + (2)(2) + (0)(3) = 5
y3 = g3f4 + g2f3 + g1f2 = (0)(1) + (1)(2) + (2)(3) = 8
y4 = g4f4 + g3f3 + g2f2 = (0)(1) + (0)(2) + (1)(3) = 3
y5 = g5f4 + g4f3 + g3f2 = (0)(1) + (0)(2) + (0)(3) = 0
y6 = g6f4 + g5f3 + g4f2 = (0)(1) + (0)(2) + (0)(3) = 0

So the final convolution output would be y(5,5,8,3,0,0), which is the same as the example given in the book. I hope this helps clarify any confusion. Keep up the good work in your exploration of geophysical concepts!