Our next topic is convolution.
Uh, it's something you may have seen in
other courses as well or will see in other courses as well.
For example, it comes up in probability, um,
it comes up in signal processing, a bunch of areas.
So it's actually something very good to know about.
So, and this is, I should say,
this is completely standard mathematical notation,
so, uh, the- and it comes up in lots and lots of different areas.
Okay. So if you have an- an n-vector a and n-vector b,
the convolution and it's denoted with this star,
uh, of course, the star hints that it's some kind of a multiplication.
That's true, uh, it is a kind of a multiplication.
So, um, this is denoted- you- so you say,
a convolved with b is what c is,
and it's an n plus m minus 1 vector and its entries are given by,
uh, sums of products of an entry from a and an entry from b.
Now, whi- which- which entries?
Uh, that's complicated, it's given by this kind of scary-looking formula here,
um, but what it is,
it's all the products a_i and b_j where i plus j adds up to k plus 1.
So let's take a look at an example.
Let's do this with n equals 4 and m equals 3.
So a is a 4-vector and b is a 3-vector.
Then we form c,
we're going to simply form c equals a convolved with b, um,
and now we'll tell you what the entries of c are and we're just using this formula here,
but I think you'll see a pattern here.
So c_1 is going to be the product of every a_i and b_j,
where i plus j adds up to 2.
Well, the only choice there, is they're both 1.
So you get c_1 is a_1,
b_1, which notice is like a product.
C_2 is all of the products of a_i and b_j for which i plus j adds up to 3.
And there's two ways to do that.
There's 1 plus 2 and there's 2 plus 1, and there you go.
These are the two entries. It's a_1,
b_2 plus a_2, b_1.
C_3, that's gonna be all the ways,
it's- it's the product- it's the sum of the products
of all of- of the entries of it's a_i,
b_j, where i plus j adds up to 4.
And the ways to do that are 1,3, 2,2, and 3,1.
Okay? And so on.
Okay. So at this point,
you might be saying like, well,
this is crazy, this is complicated.
It is complicated, but in fact,
you'll get used to it and it'll actually have a meaning for you,
and depending on what field you're in,
it- it may end up being, ah,
well, a very important part of your life as convolution.
Okay, so here's a specific example.
If I just take the convolution of these two vectors here,
um, I- I get this vector here and we can at least audit the size, right?
So here m and n are both 3,
and so you should get something that is, uh,
3 uh, it's- it's uh,
3 plus 3 minus 1,
so you should get a 5-vector and indeed that's- that's exactly what we get.
I'm not gonna audit it, uh,
I- there might be an- an error in that anyway,
but- but my suspicion is it's right,
uh, in that this is actually what the convolution of that is, right.
So at this point, by the way,
you should have absolutely no idea why anyone should care about this or why would- okay.
Fine. So here's really, here's where it comes up.
This is a very important idea, um,
it's essentially polynomial multiplication and to be honest,
it's the way I think about it.
I only think about it as polynomial multiplication.
So let me explain,
so suppose the n vector a represents the coefficients of a polynomial,
this way, so a_1 is the 0th order of coefficient,
a_2 is the x_1 coefficient, right?
And so on, up to a_n,
which is the x_n minus 1 coefficient, okay?
And the same for b, except b only goes up to the x_m minus 1 coefficient.
So- so the vectors a and b represent the coefficients of a polynomial.
Well, it turns out if I call this polynomial p of x and that's q of x,
and I take the product, now the product of two polynomials is a polynomial also.
And in fact it is one of degree up to m plus n minus 1- m- uh,
n plus m minus 1.
And its coefficients are precisely the convolution, like that.
So, uh, if we were to go back and- and see that, um, here, uh,
it says that another way to get these coefficients is actually, uh,
to multiply two polynomials together and collect the coefficients,
and the coefficients give you the entries of the convolution.
So for example, it would be a_1 plus
a_2x plus a_3x squared plus a_4x cubed.
And we would multiply that by b_1 plus b_2x plus b_3x squared, right?
And if I multiply these two polynomials together,
I multiply everything out and I collect the terms and I would get things like,
for example, the constant term when I multiply this polynomial by this polynomial,
well, the only way to get the constant term is by multiplying a_1 and b_1.
Oh, hey, look at that, that's what c_1 is.
Now, how do you get the x term,
the linear term when I multiply this polynomial by this one?
Well, the only way to do that is the constant times the
linear part plus the linear part here, times the constant.
So that's a_1 times b_2 plus a_2 times b_1,
and that is exactly c_2, and so on.
So- so basically what convolution is,
is it tells you how the coefficients-
it gives you the coefficients of the product polynomial.
Okay. So that's the idea.
Now, once you have that interpretation,
you- a lot of things come for free that would otherwise be,
well, kind of a pain to show yourself.
So for example, it turns out that the,
uh, the convolution of a and b is the same as convolution of b and a.
So or you would say it is commutative.
Commutative means you can carry out
an operation in either order and you get the same thing.
So that's what- that's what this tells you.
Why is the answer,
is that when I multiply the polynomial p of x times q of x,
I get the same thing as multiplying the polynomial of q of x times p of x,
so it's gotta be the same.
Here's one, it is associative if I take the convolution of
a and b and then convolve that with c. It turns out that's
exactly the same as convolving b and c first,
and then convolving that with a. Convolving is the verb for convolution, right?
Okay. Okay, so that's, again,
that comes just from polynomials.
So you're just multiplying three polynomials together and you're
collecting the coefficients in like powers of x,
and then the result is what you get.
Okay, and it also tells you this,
it says that the convolution of two vectors is 0 only if one of them is 0.
Okay? So, um, that's the idea.
Oh, I should also say if- if the two- if the two vectors are 1-vectors, right?
Like they are, m- n equals m equals 1,
then convolution is just ordinary multiplication,
it's nothing but multiplying two,
uh, two numbers together.
So in that sense,
you can think of convolution as a generalization of multiplication.
Okay? Now, we can represent convolution using matrix vector product.
Okay, so let's see how that works.
Uh, Suppose c is,
uh -is a convolved with b. I can write that as a matrix T of b times a.
So, uh, that's how that works.
And for example, this is- this is an example for a particular size of b,
which is b is 3 and a is 4.
So it's following the example from here.
So the- these- these dimensions, okay?
But for that- that example,
a T of b looks like this,
and you can just check that if I multiply this by a1, a2, a3, a4.
If I multiply this matrix here by this vector,
what I will get, that's no longer T of b, uh,
but this is going to tell me it's gonna give me the convolution and
I'll just work on a couple of things like the first row is gonna be-,
uh, the first one is going to be a1, b1.
Uh, which is correct, okay?
And the next one is,
I'm going to go across here and down here,
and I'm gonna get b2,
a1 plus b1, a2, right?
And I- I keep going down,
and you'll see that I'm getting the convolution.
So that's- that's- now the matrix t of b is super interesting.
It's called a Toeplitz matrix or Toeplitz matrix,
um, that's named after a mathematician named Toeplitz.
Um, and it's a super interesting matrix,
If you take a look at it.
Um, It's- so on the- these are the- when- when you
look at the- these are called the diagonals of a matrix right?
They're-They are all the entries where, um,
you know i plus- i- i mi- i minus j is equal to some number, right?
Like when they're equal,
that's- that- that- that is called the diagonal, right?
But these are- these are the diagonals.
And what you see is a- this is a Toeplitz matrix is constant on the diagonals.
That's the right way to say it.
So in other words,
if you're- if you have a Toeplitz matrix and you know what the value is at one point,
then it's gotta be the same all up and down that diagonal. So that's it.
Um, so these come up in a- in a lot of areas.
But what this says is- another way to say it if you connect all these things is
you're saying that to multiply a polynomial,
if you represent a polynomial by a vector of its coefficients,
and it says if you multiply it by another polynomial,
you get, of course, another polynomial and its coefficients are given by
a matrix times the original vector.
And that matrix is this Toeplitz matrix at T of b.
Okay, so that's the idea.
Okay, now I'll just mention a few quick, er,
cases where convolution and therefore Toeplitz matrices come up.
So one very common thing is- um, is in time series.
So I think of x representing a time series.
So x1 is the first sample, it's a number.
X2 is the second sample,
x3- then it can be anything you like.
It could be the temperature in ten minute intervals.
It could be the price of something.
It doesn't matter what it is, right?
It's just- it's just a time series.
Okay. Now, if I do a convolution with, uh, a,
where a is this vector is one-third, one-third, one-third,
then it turns out what you get is yk is- is this and it's actually beautiful.
What it is, is it is a sum.
So each yk is a su- is an average of a little window of three different x's, okay?
And so people call that a three period moving average.
And it's used- of course what it does is it smooths out a time series.
So over here, there's a time series.
Uh, I don't know what it is, it doesn't matter.
And here it is, I have now convolved it with,
uh a which is one-third, one-third,
one-third and you get kind of something that has the same shape,
but it has,um- it- but it's smoother.
And it's smoother because you're sort of averaging stuff.
So if it kinda jumps up and jumps down,
that gets smoothed out a little bit by the averaging.
Okay, so it's just smoothing.
Very, very common.
Uh, this is a very common operation to carry out on
a time series just so that your eye is not,
you know, whatever, distracted by all the wiggles, right?
So it would be very common in economics or finance to quote,
like a five-day- a five day,a
you know moving average is what this would be called.
So that's an example. Okay, so- so it comes up a lot in- uh, in time series.
This is one example.
Now it also comes out in, uh- it, uh- it,
uh- as an interpretation of an input-output system.
And let me explain what that means.
So we think of, uh, you,
that's actually one of the traditional names used for it is for an input.
So, and it's a time series.
And then the vector y also represents a time series,
but we think of u as an input and y as an output.
I could give you lots of examples of this,
but u could be the power that we
apply to a heater and y could be the temperature rise of,
let's say, whatever I'm heating.
Um, and let's say this is sampled on every, you know,
five minute intervals or one minute intervals it do- it really doesn't matter, right?
Then, um- then that's the idea. That would be an example.
And by the way, such a- such systems,
I mean, depends on what it is,
of course, but we would generally be described precisely by convolution, right?
So it says- uh,
so you think of u as- as what goes in and y is the result.
Um- and so when- when it turns out that the- the so-called output, um,
is- is simply a convolution of the input with something,
um, actually one of the traditional names is h,
it's called the convolution model.
So it means that I- I don't know what this thing- well, okay.
What it says, it's a very specific I'm saying what this- what- the way
you relate the input to the output is- it's via convolution.
And h is called lots of different things.
It's called the system impulse response.
That would be in mechanical engineering and electrical engineering for example.
Um, it would have other names in statistics,
it comes up as well.
Um, and, uh, it's called the kernel in mathematics,
that would be a- a very common thing you might have heard.
It'd be the convolution kernel,
you would hear that and if you hear that- um,
so it's just an impulse response is actually
a little bit of a dialect, that's not standard.
Like if you walk into a math department and say, oh,
the impulse response is this,
they'll say, "what is that? "
right? But if you say, sorry,
I meant to say convolution kernel,
they'll say, "Oh, cool. Why didn't you say so?"
Okay. And what it says is this,
if we write out what it means,
it- it- it looks like this and it's a- it's a- it's a kind of a scary equation.
Um, but let's take a look at it.
It says that the- the ith output is equal to- it's a sum um,
over the inputs here multiplied by hj.
Now, u minus j plus 1 is something- if- if you think of i as now,
then u minus j plus 1 is something like,
you know, j minus 1 steps ago.
That's what it means.
And it says you multiply that by hj.
And so what it says is the output now is
a linear combination of previous inputs with the coefficients given by hj.
Okay? So that's the idea.
And so in fact, you can even interpret j as literally the number of periods ago.
That's what it means because it's- it- it tells you your current output.
How does it depend on the input,
let's say three samples before.
And that would be something like h3.
Okay, so that's what it says.
Um, and here you can interpret h3 as the fa- as
the factor by which
the current output depends on what the input was two time steps before.
Two time steps because the first one tells you how it
depends on now and then previous then previous,
previous and that would give you h3.
So that's the- and input output systems come up thr- throughout,
actually, all of science and engineering.
I mean, it's just, it's absolutely ubiquitous, right?
It could be things like, you know,
the rainfall in a region that could be u and y could
be the height of a river above some normal height.
That would be given by convolution.
Um, in thermal systems,
dynamical- mechanical systems would- many mechanical systems would work this way.
So it would just be,
this is an extremely common model of systems.