Now we gonna look at a very famous algorithm called the Gram-Schmidt algorithm.
Uh, the name stands for two mathematicians, Gram and Schmidt.
Um, so we'll- we'll take a look at it, um,
and it's- it has to do with linear independence and in fact it is an algorithm.
I mean, for- for- for right now its main purpose is to detect whether a set
of vectors is linearly dependent or linearly independent.
We're actually gonna see later that it is
enormously useful in a lot of practical applications,
but that's not gonna come up for a while.
So right now it is again,
I'm sorry, just kind of weird and abstract.
Um, I should also say another thing about it.
Um, you know, we described one algorithm already,
that's the K-means algorithm and- and now we're gonna describe Gram-Schmidt.
I guess, I'm not one who thinks that
students should be forced to implement these things by themselves.
I mean, I don't know.
I mean, I suppose there is a point to it.
Um, I don't, b- but it- I will describe it.
And of course, you know, when you're doing this in practice, um,
you're gonna rely on,
ah, on- on- on implementations written by others.
Um, so- so the point of it is not that you're gonna go out and code this yourself,
but the point is you should understand what it is, and how it works, and what it does.
But when you actually use it,
you're gonna call, uh, you know,
some routine written by someone else.
[NOISE] Okay. So here's what it is.
Um, for now we'll see that it's a lot more than this,
but for now, here's what it is.
It is simply an algorithm that checks that a set of
vectors is linearly independent. That's it.
Um, we're gonna see it has a lot of other uses later.
In fact, you know,
when the whole class is about 2 or 3 algorithms
and this is- they're basically all related to that.
That's all- it's all this- this one. This is Gram-Schmidt.
Okay. So here it is.
We're just going to jump right in.
[NOISE] Um, and like I said right now it's kind of abstract,
but that it'll- you know,
it'll emerge later in the book,
uh, that it has a lot of uses.
Okay. So we're given a set of vectors,
uh, and there are n vectors and we have k of them.
And what's gonna do is it's gonna process them,
the vectors one at a time,
um, and in the end it is going to, uh,
will be- will be able to use this to determine if those vectors
are linearly independent or linearly dependent, right?
To remind you, linearly dependent means that there's
a linear combination of them at 0 with the coefficients not all being 0.
Linear independent means that's not the case.
Okay, so here's what it does.
Um, the first step is it takes the a_i th vector a_i and it subtracts from a_i, um,
a it main- maintains,
I should say it maintains a set of vectors,
q_1, q_2, q_3, up to q_k unless the algorithm terminates early.
It generates a set of q's which are orthonormal.
Oh, I should mention,
uh, that the, uh,
the notation q, uh,
is- it is just a convention.
Typically, a set of q's are orthonormal vectors, right?
By the way, same- same for Us and Vs. And this- this is just convention, so, okay.
But in this case it- it's following the convention.
So the vectors, ah,
it's gonna generate a set of vectors q_1,
q_2 which are orthonormal.
So here's what's going to happen.
Um, you're going to take a_i and you are gonna subtract from it the- this,
uh- this, um, the inner part of q_1 and a_i.
Look that's a number times q_1 and so on.
Now, what you'll recognize,
you may remember this from last time in fact,
is that if- if a_i is a linear combination of q_1 up to q_i minus 1,
then in fact, all of this is equal to a_ i and q_1 tilde is 0.
So if q_1 tilde turns out to be 0,
that mean- that means that a_i is a linear combination of q_1 up to q_a minus 1,
uh- uh, are q_i minus 1, sorry.
Now what we do is again,
we- we check if q_i tilde is 0, if it is we quit.
Uh, and because in that case it'll turn out that these vectors are linearly dependent.
Um, If not- if non-zero,
we simply divide by the norm and we normalize and we get q_i from q_i tilde.
Okay. So if this algorithm runs all the way to the end and does not quit,
as in step two here of the algorithm,
then that's gonna be,
that's gonna tell us that those vectors are linearly independent.
If it stops here,
if it stops in algorithm in- in step j,
then it's gonna tell us that- that
vector a_j is actually a linear combination of the previous ones,
a_1 up to a_j minus 1.
And that means that our set of vectors is linearly dependent, okay?
So that's the algorithm, um,
now the one that's actually used numerically in practice,
is mathematically equivalent, but it's not quite the same as this.
I mean, it generates exactly the same vectors and things like that,
but it's- its slightly different.
Okay. Now let's walk through an example, um.
Here's two vectors which are 2, 2 vectors.
Um, they are a_1 and a_2.
Um, this gray circle is showing you all points of norm 1.
So its a circle basically of- of radius 1.
Um, okay, and so let's see.
So that would tell us, for example,
the norm of a_1 is about 1 point whatever, 3,
I'm making that up, but that's about it.
Okay. So let's run Gram-Schmidt.
Well, we grab a_1 and the first thing we do is we subtract off from a_1,
uh, some linear combination of the previous q's.
But we have no previous q's,
so we subtract nothing.
And so that tells us that q_1,
this is the first step, right?
q_1, there we go, sorry about that.
So q_1 tilde is in fact just nothing but a_1.
Okay. So now that's the first step.
We check if it's 0, and it's definitely not 0.
And so we normalize it,
and that means we shrink it to get q_1,
and you see now it's green.
Um, and you can see that it's- it's arrow,
the tip of the arrow,
you know, shows, it's on that unit circle.
That's what it's called. And that means that now has norm 1 so that's q_1.
Okay. Next step.
Now it gets interesting, right?
Because now we go over to here.
And what happens is we take a_2 and we subtract off from a_2,
a multiple of q_1 to make a result orthogonal to q_1.
And so the correct thing to s- to subtract is minus q_1 transpose a_2, q_1.
And that's this vector here,
and we end up with this red vector here, which is q_2 tilde.
Now notice that q_2 tilde is orthogonal to q_1.
Because that's actually what we're doing is we're- we're- we're slowly
producing and we're- we're generating a set of orthonormal vectors.
Okay. Now, at this point is,
they're just ortho, they're not normal yet.
And so what we do here is we check if q_2_2 tilde is 0, it is not 0.
And therefore we- we scale it to make it have length 1 and we end up with,
there we go, there's q_1 and q_2.
And so this is extremely boring.
There's no reason to- to have any interest in because
there's nothing we- just to be completely open about it.
There's nothing practical we can do with this, yes. So yeah.
So I'm just- I'm admitting, that's all.
I'm admitting it. Okay, so.
Uh, so the point is if you run the- the,
if you run Gram-Schmidt on these two vectors,
a_1 and a_2, that's what comes out, q_1 and q_2.
And you could well ask, who cares?
And I would say, you don't know.
The answer is, you don't know yet.
You'll know later that this actually can do all sorts of supercool practical stuff.
But for the moment,
this is all just weird and abstracting, whatever.
So just trust me. All right.
So we can analyze this a bit.
I'm not gonna go into it in too much detail, um,
because this is the kind of thing that's best done by you kinda,
you know, reading through the book carefully and stuff like that.
But I will say just a few things about how the algorithm,
what it does. Um.
So the first thing, and I think our example already kind of gave us a hint,
is the q's that come out of the Gram-Schmidt algorithm are orthonormal, okay?
And the- the reason- we can check, um,
suppose it's true for i minus 1,
and we'll show this by, uh, recursion, okay?
Um, in that orthogonalization step,
you are actually subtracting
exactly the coefficient you need to of the previous q's to make it orthogonal,
uh, to all of them, okay?
So when you finish q_i tilde is orthogonal to all the previous ones.
That- that's how that works.
Um, now to see that,
all we do is we take an inner product, uh,
with q_j so q_j transpose q_i tilde is equal to,
and this is q_i tilde here and I'm just gonna simply work it out and see what we get.
Um, but over here we get things like,
uh, q_j tilde q_1,
well, uh, that is gonna be,
uh, that's gonna be 0, right?
So the only one that comes out is we end up with q_j transpose, uh, sorry,
the inner product of q_j and a_i and then again q_j and a_i,
and you subtract them, you get 0, so it's orthogonal,
um, and what that says is that the new- it says q_i tilde
is orthogonal to all the previous ones but
if I scale it by a number because to make its norm 1,
it's still orthogonal, so- so the- so the q's are orthogonal and of course,
the normalization step guarantees that the norm is 1, okay,
so- so it says that the q_i's that come out of
the back end of the Gram-Schmidt algorithm are orthonormal.
Okay. Um, now, if it hasn't- if the algorithm has not terminated before iteration i,
then it turns out i- a_i is a linear combination of q_1 through q_y,
um, and we can even see that because we
can actually very explicitly write down what the linear combination is.
It is literally the norm of q_y tilde times q_i plus,
and then again, this inner product,
uh, this- these are inner product coefficients.
It's the one you've already seen before in an orthonormal, uh, basis expansion.
Um, so what we do is we- we get that, that's very explicit,
so a_i is literally a linear combination of q_1 up to q_i, okay?
In fact, no, that's one of the ways we can say this is that each,
each a_i is a linear combination of q_1 up to q_i, okay?
Um, and it turns out the reverse is true too,
each q_i is a linear combination of a_1 through a_i and again, you can see that, uh,
by induction, I'm not gonna go into the details there,
but that's- that's how the- that's the case.
Okay, we get to, uh, early termination.
Um, if it terminates in step j,
what that says is that q_j tilde is equal to 0.
That means that when you took a_i and you- a_j and when you subtracted
the appropriate linear combination of q_1 up to q_j minus 1 from it, you got 0.
Uh, and that tells you actually that equality holds um,
now- now will meet- now we'll notice that each of these
q_i's here is a linear combination of the a_i's,
uh, a_1 up to a_j minus 1 so this is a linear combination of linear combinations.
Linear combination of linear combination is a- is again
a linear combination and that says that when it stops,
it says if a_j is a linear combination of a_1 up to a_j minus 1,
that's- that is one of the definitions of being dependent.
So what that says is that the- the Gram-Schmidt algorithm,
if it terminates early,
then it- it term- it terminates because the a's you started with were linearly dependent.
I want to say a little bit about the complexity of the Gram-Schmidt algorithm,
about how long does it take to, you know,
basically how many flops does it take to actually carry this out?
Um, well, let's figure it out in iteration i,
uh, you have- you have to evaluate i minus 1 inner products, right?
Um, and that costs- each inner product costs 2n minus 1 flops,
uh, and there's i minus 1 so that's that, okay?
So that's the total number of flops.
Um, to compute q_i tilde,
you have to, uh, subtract, uh,
subtract off various things and that costs you 2n i minus 1 flops, okay?
Um, then it costs you 3n flops, uh,
to calculate the norm and then divide q_i tilde by that norm to get q_i,
so that's 3n flops.
And the total is now uh,
we add this plus this,
plus that, and we have to now sum that from i
equals 1 to k and you get something horrible that looks like that.
Now, you could work out what that is.
In fact, it's exactly this and I- I'll- I'll tell you why.
It's- I'm going to use a formula which you can just remember or
lookup or go to Wikipedia to find out or something like that.
And it's this, it's the sum from i equals 1 to k of i
minus 1 is actually k times k minus 1 over 2.
In other words, uh,
the following sum, you know,
if- if- you can check it,if k equals 5 and says you should add up 0 plus 1 plus
2 plus 3 plus 4 and you will find out that that is 5 times 4 divided by 2, which is 10.
And it's correct, I mean,
maybe I misspoke it,
but it's correct, um, so.
Anyway, so you get some horrible thing like this,
now what you have to remember about flop counts is it's extremely crude.
So we're gonna drop what are- what we call a non-dominant terms, right?
So for example, ah, you know,
when you work this out,
the biggest term you're possibly going to get is going to be
this 4n times k squared divided by 2, that's 2nk squared.
All the other terms have a coefficient of either n or k which is
smaller and we're interested in the case where n and k are reasonably large,
so we just drop them.
And so this is completely standard in- in a flop count and you would say that
Gram-Schmidt has a complexity of 2nk squared flops.
Um, and the truth is- is that it's not quite right um,
but the whole flop count model is so approximate that this is just fine, right?
Because we're, you know,
we're pretending that multiplies and adds and divisions and things like that,
even a square root because we have to calculate a norm,
and we're kinda pretending that these all cost the same, which they don't.
Okay, so you get 2nk squared.
Uh, that's interesting, right?
Because it tells you that it is, um,
it is- it is quadratic in the number of vectors,
uh, that you apply it to, um,
and it's linear, you would say in the dimension n.