Lecture 6 Fall 2025: Finding Orthogonal Bases transcript

All right, welcome back everybody. So today we are going to continue from where we were before and we are going to start talking about how we can learn or find um orthogonal oops learning [Music] bases. So given a set of points we want to find an orthonormal basis that correspond or spans I'm sorry that represents the subspace spanned by those vectors. So we in general are going to be given um end points in a pd- dimensional space and we will write these points as x1 x2 etc uh all the way to xn in RP.

And so now we can think about the subspace that's spanned by those points and try to find the basis a a basis that represents that subspace. So as we do this I want to think about what are the options or what might that basis look like and I want to consider a couple of key cases. So the first case we're going to consider is where n the number of points that we have is less than or equal to p. So we've got a small number of points in a potentially highdimensional space.

So in this case if we were to think about the span of the points x1 through xn then how many or how big can this basis be? How many different basis vectors might we expect? So this span is going to be a subspace with dimension R. And the question that I'm trying to ask is how big might R be? What's the biggest that R could possibly be? Yes. >> Yes. The biggest that n can be that r can be is n. And in general, r is going to be less than or equal to n.

In this case, um the dimension r will be exactly equal to n if the nxis are linearly independent. But more generally, the subspace dimension r will be the number of linearly independent vectors in this set between uh x i to x1 uh x uh 1 to xn. And so just to kind of illustrate some of the possibilities graphically, let's imagine that p is equal to 3. So for example, P is equal to 3. So here's one possibility where here's our first coordinate X1, our second coordinate X2, our third coordinate X3, and then we consider some vectors that we might have in this space.

So one possibility is that we get two vectors. Our first vector here is x1 and our second vector maybe is x2 like this. So now if we think about the span of those two vectors that subspace is going to be the plane that contains both of these vectors. So you could kind of imagine like forming a little um plane here and then expanding it in all directions infinitely far and that would be the subspace spanned by the two those two vectors.

So this is an example of a two-dimensional subspace within a three-dimensional space. So this subspace S has dimension of S equal to R and in this case that dimension is equal to two even though we are in a P= 3D dimensional space and this happens in part because we only have well exactly because we only have two vectors and they are linearly independent from each other. So we have two linearly independent vectors and therefore the subspace has dimension two.

We could also imagine a case where again we're in 3D space and now we've got two points. Maybe the first one here x1 is the same as before but the second one out here x2 now is linearly dependent on x. So this is a case where n is equal to two but x1 and x2 are linearly dependent and therefore r is going to only be equal to one. We have a one-dimensional subspace in this case. Any questions about this case? All right.

So then the second case I want to consider there we go is where n is greater than p where we've got for instance a large number of points in a relatively low dimensional space. So in this case if we were to look at the span of x1 x2 all the way to xn this is going to be equal to a subspace with dimension r and how big can r be in this case? What's the biggest it can be? Yeah. >> P. That's right. So r is going to be less than or equal to p.

Um and notably in this case the x i are linearly dependent. Okay. So the number of linearly independent x i's is the dimension of the subspace. It cannot go above p and we are in the setting where p is smaller than n. So let me illustrate this graphically. So again we'll work in the p= 3 setting. And now imagine that the points that we are looking at [Applause] here maybe we've got x1 and then we've got x2 here's x3 x4 x5.

These are all points within this threedimensional space. And in this case, they might span the entire threedimensional space. So in this case, the span would just be equal to all of R3. But the biggest the dimension of the subspace can be is this ambient dimension P. We can't have a higher dimensional subspace than the space that we're originally in. So um in this case r is equal to p is equal to 3. But another example that we could consider would be it's going to start off looking like our first example in case one.

So here we've got x1 and then we've got x2 and then imagine we've got a third vector x3 and now we're going to just like before imagine sort of the plane that connects x1 and x2 and that subspace corresponds to taking that and extending it infinitely in all directions. And in this case, we're imagining that X3 is also lying in that same plane or in that same subspace. So the span of these three vectors, even though I've got three vectors in three-dimensional space, in this example, that span is only two-dimensional.

So R is equal to two. And this is a result of the fact that there is linear dependence among these vectors. So what this is showing graphically is that x3 here can be written as a weighted combination of x1 and x2. And so it doesn't add any dimension to our subspace. All three of these are lying in the same two-dimensional subspace. Okay. So this is going to be important when we start thinking about finding orthogonal bases given a collection of vectors because it's going to be important to understand how big we can expect that basis to be in terms of how many different basis vectors we might expect to find and how that relates to the number of samples that we have and the dimensionality of each sample.

Yes. >> Yeah. I think in general I'm going to try to use n to be the number of samples and p to be the dimension of each sample or like the number of features corresponding to each sample. Yeah. >> Can you explain why number of features determines like the ambience? Um so imagine for so sorry just for the recording the question is why do we think about um P corresponding to the ambient space? Um so first of all I want to just these are abstract concepts that work even without this machine learning interpretation that I'm giving you to try to make things tangible.

So we could reverse the roles of N and P here and everything would still be the same. There's still limits to the dimensions of subspace spans by points. That said, within a machine learning context, the way I like to think about it is um I'm just given a whole bunch of different features for different samples. So for instance, right, maybe I've got um two features. Let's just say in this case of trying to determine whether a photograph represents someone smiling or not, one feature could be um eye to mouth distance and the other could be the mouth width, right?

And then I can imagine making a scatter plot of all of my different samples. And so for each sample or each photograph, I'm going to have a different pair. I guess all of these should be positive, shouldn't they? Uh I'm going to have a different pair of feature values. And so to me, it makes sense to think about having n different points in my scatter plot here within a pdimensional space where P is the number of different features that I'm um considering.

Is that answering your question? Okay, great. Are there any other questions? >> Yeah. >> So the label y will be outside. >> That's right. So in this context when we're talking about subspaces um and spans, we're really not focusing on labels at all. We're just talking about the feature vectors and trying to understand the geometry of them. Yeah. And so what we will see is that once we understand how to find bases for these feature vectors first today using Graham Schmidt and then next week using the singular value decomposition then there's a number of different things we can do.

First, we can return to this notion of supervised learning, classification, or regression. And we can revisit some of the things that we've already looked at with lease squares, but look at them through a different lens. And it's also going to lead to new methods um and um kind of take us beyond where we've already been in that supervised learning setting. In addition, we're going to be able to look at unsupervised learning where there are never any labels where we can say for instance um just given the X's um can I reduce their dimension?

So let's say for each sample I've got millions of different features that someone observed, right? Maybe for each X I've got uh each X corresponds to an image with millions of pixels. And what I'd like to do is to boil that down to a small number of salient features. The tools that we are learning here will enable us to do that even without any labels. So for this discussion, there are no labels whatsoever. Once we learn how to find bases given a set of points, then we'll return to supervised learning and we will also look at unsupervised learning.

Yeah, great question. Any other questions? Okay, that was just a perfect segue into the next thing I wanted to mention. So [Music] here's our central question. Given a set of vectors spanning a subspace, how do we find an orthogonal? And I guess I keep saying orthogonal, but every time I do, I really mean orthonormal. an orthonormal basis for that subspace. And so today we are going to look at one approach called Graham Schmidt orthogonalization.

And as I mentioned, next week we are going to look at the singular value decomposition. Okay, so both of these are ways to find bases that span a subspace given a set of vectors and we are going to see that they can give very very different bases. So what we saw at the end of the last lecture on Tuesday is that given a set of points or given a subspace there are many different bases that can represent that subspace. And so depending on which method you use here you will get a different basis.

It'll still be an orthonormal basis but it will have different characteristics and we're going to talk about what those characteristics are. Okay. So let's start with an example. So before I give you just a recipe for Graham Schmidt orthogonalization, I want to provide a little bit of intuition. And so in particular, we are going to have um five different vectors X1 through X5. And all of these are going to be in um 3D, but they also span a 2D subspace.

So in other words, there's only two linear independent vectors in this space. And so if I try to make a drawing here, we imagine that we have a subspace S. I'm going to draw it as a plane here. And right in the middle is my origin. And then I'm going to have five different vectors in lying within this 2D subspace. Okay. So here we've got x1, x2. Okay, so now we could have a couple of different options for what that basis might look like.

So basis option one and I'm going to call that u1. I could form a basis matrix where the first basis vector is just x1 and the second basis vector is simply x2. Right? So these are two different vectors. They are not linearly dependent on one another and together they span this subspace. So this is not orthogonal or orthonormal. So there could be you know this might not be the most desirable basis and we're going our focus today is finding orthogonal or orthonormal bases but this is a valid basis for this subspace.

The alternative is that we could find two different a different basis where here or maybe I'll draw it here. I've got my first basis vector u1 and my second basis vector I'm going to have be perpendicular or orthogonal to that first one. So basis option two. So u2 here is going to have vectors u1 and u2 and this is orthogonal. And so this is what we're headed toward today with Graham Schmidt orthogonalization. Taking a collection of vectors and finding an orthonormal basis where all of the basis vectors have the same length equal to one and they are all perpendicular to one another.

Yes. >> Um I'm just trying to think about this more like theoretically once you choose one vector that's in that in that set, you could choose any other vector that's kind of on that same plane and it would still be a basis for the sub. Yes, I could take in that example any two linearly independent vectors and together they would form a basis for the subspace. So the thing I would have to watch out for is imagine in this example that I had um x1 was here.

It's going to get a little crowd or crowded here. Let me draw it this way. Here I've got x2 and then imagine I had another vector that looks like this. This is going to be my x6. Maybe I've got a sixth vector. Right? So they're not exactly the same vector, right? They've got different lengths, but they are pointed in exactly the same direction or they could even be like pointed opposite directions. But in this there in either case, they are linearly dependent on x2.

So though that pair would not span the subspace. So as long as I choose any pair that's linearly independent, then that will form a basis that spans my subspace, but not an orthonormal basis. [Music] Okay, so let's look at an even more kind of concrete example. [Music] And here P is equal to two. So we just have two dimensional vectors. X1 is going to be the vector 2 0. And X2, my second vector here, is going to be just kind of generically a vector with entries A and B.

And I'm not going to specify exactly what A and B are. And if we draw this now, so this is my first coordinate and this is my second coordinate. And so my x1 vector is going to be right here. So this drawing a little bit below just so it's visible, but this is my first point x1. And then my second point x2, I'm just going to draw it like this. It's got coordinates a comma b and this is x2. Okay. So I want to find a basis now for this space given these two vectors.

Now immediately from this visualization you can tell that this is kind of trivial, right? I've got two vectors and you know for almost all A and B they are linearly independent. And so I'm just going to have the whole 2D plane be the subspace. and I just want a basis for that 2D plane and we know how to do that already. But to illustrate where we're headed with the Graham Schmidt orthogonalization procedure, I think it's helpful to walk through this.

And so what we are going to do um is we are going to start with our first basis vector u1 and we are going to form it by taking our first sample x1 and then dividing it by its norm by its length. And if we do that, then this resulting u1 is going to be a vector that's pointed in the same direction as x1, but only has length one. So going back to our figure here, this point is 1 comma 0, whereas this was 2 comma 0. So right here we are going to have u1.

Okay, so the first step in grammar orthogonalization is always pretty easy. we simply do this normalization step. The next thing we are going to do is we are going to write x2 as the sum of a weighted version [Music] of our first basis vector and a residual. And I'm going to call throughout these lecture notes the residual x2 prime. [Music] Okay. So we've got this point x2 here that has coordinates a and b. We want to write it as a weighted sum of u1 plus whatever else we need to represent x2.

And so and in particular when we do this we want to make the residual as small as possible. [Music] And so to do this the we want to figure out how much weight to put on u1 to make it as close as possible to x2. So, in other words, we're going to say find whatever weight um what did I call the weight find a weight a so that [Music] if we look at oh shoot I can't use a here find a weight w I guess so that if we were to look at that weight times u1 It's as close as possible to x2.

And so we're going to measure as close as possible by just looking at the sum of the squared errors. So we want to make the sum of squared errors as small as possible possible minimized. And so what weight would accomplish that? I'm not sure what you mean by the position >> but Oh, okay. Projection. Yeah. So, it's true that we're headed towards a projection, but we can this for this particular example, this is very simple because we are looking at a weight times u1 is just going to be that weight and then a zero.

And so, we want to make these two vectors as close as possible. So there's nothing we can do about that second element because it's just fixed at zero. So what's the best value of W to minimize the sum of the squared errors? Yeah, A. Exactly. And so we're going to choose W is equal to A. And so now what we're doing is we are saying that X2 [Music] is going to be a weighted version of U1. So we are going to have a * u1 which is 1 comma 0 plus our residual x2 prime.

And so sorry this was x2 not x^2. And so from here we can derive that x2 prime is going to be equal to what? Remember that x2 has entries a and b. So we're writing it as a vector with a in the first entry and zero in the bottom entry. So what's left in the residual x2 prime? Yeah. >> B. >> B. So we're going to have a vector with the first entry zero and the second entry being equal to B. And so what we will do for our next step in this Graham Schmidt orthogonalization is have our next basis vector correspond to taking this residual x2 prime and normalizing it.

So we take x2 prime and compute its norm and divide by it. And so that's going to give us 0 comma one. And maybe I'll just write up here to be really explicit. Our first vector was 1 comma 0. And so overall what we've derived here is that our basis has vectors 1 0. This is our u1 and 01. And this is our vector u2. And going back to our drawing now, our second basis vector is exactly like you'd expect, this vertical axis.

And so now we can represent any point in this 2D subspace as a weighted sum of U1 and U2 which is just the canonical cartisian coordinate vectors. Okay, so we already kind of knew that this would be a good basis for this space. But now we've kind of walked through the steps through which you would get to that basis using the Graham Schmidt orthogonalization. And now no, we're going to do one more little example before we write out an abstract algorithm that you can follow for general data sets.

Yes. So why are we setting ass? >> Okay. And starting with a handwavy explanation, we've already just defined our first basis vector to be the normalized x1. Now that that's fixed, we want to say, okay, how much of my next vector x2 is already being represented by this first basis vector? And so this is where we come up with this kind of least squares question because the answer to this is telling us that maybe I can write it a better way.

I want to be able to write my x2 which has coordinates a and b first using my u1. So I'm going to do a * my first vector plus and what we eventually derive is b * my second vector. So before we have this we just say this is some generic residual that we called x2 prime and what we were doing here is we were saying all right I have to decide how much weight to put on to u1 and what I'm trying to do is I'm trying to get the most accurate representation I can of x2 using only that first basis vector u1 and so that leads me to this weight a and then I know that everything that's left in x2 that I haven't already captured with u1 is going to be b * this 01 vector.

Um does that get add your question? Okay, great. Any other questions? Okay. But I I think your question raised a really good point like there is no notion of what I mean there's this notion of there is a formal Graham Schmidt procedure and so there's a correct U1 for that procedure but it's not like more generally for a subspace there's a right orthonormal basis or wrong orthonormal basis and so we are making design choices when we choose an algorithm.

Um okay. So now what I want to do is work with a slightly more complicated um example. And again we're going to only have two points and in this case they are going to be three-dimensional. So the first one is 1 1 0 and the second one is going to be 1 3 0. Okay, so before we get started, what do we know about the subspace that's spanned by these two vectors? Any thoughts? >> Yeah, >> very basic, but it's two dimensional. >> Yep, it's two-dimensional.

And in fact, it's just the horizontal plane, right? The span of these two points is a set of all vectors where the third coordinate is equal to zero. Um, and so now what we would like to do is to seek an orthonormal basis for this 2D plane. Again, you can probably imagine right off the bat what that might look like, but we are going to kind of derive it step by step. is an example of this Graham Schmidt procedure before we write down the full abstract recipe.

Okay, so again our first step is always the easiest. Our first basis vector is always just our first point x1 divided by its norm. So for this particular example, the norm of x1 is the square root of the squares of the entries. So 1 2 + 1 2 + 0 2. So I've got just the square root of two. And so my first basis vector is going to have entries 1 over the<unk> of 2, 1 over the<unk> of two, and zero. All I did is I took that first b uh first sample and normalized it and that gives me my first basis vector.

Now, just like before, we want to write X2 as a weighted U1 plus a residual and that residual we are going to denote X2 prime. So, we want that residual to be as small as possible. And so we want to figure out what weight is going to make that weighted U1 as close as possible to X2. So we want to minimize with respect to the weight distance between W U1 and X2. [Music] So first of all this is something that we can just simply use our le squares formula for right.

So when we were doing le squares before uh well the n the variable names were different but the idea is still the same. So when we think about what we were doing before, this x2 here is playing the role of our y vector and this u1 is playing the role of our feature matrix x. Um and then we were trying to find a weight vector w in this case just a weight scaler. So we can just plug in our formula here. And if we were to do that, we would get U trans U1 transpose U1 inverse U1 transpose X2.

And so now if we were to try to write our x2 as this residual x2 prime plus our weighted u1, we are going to have our weight times u1. And if we were to kind of spell that out, what we get is u1 times u1 transpose u1 inverse u1 transpose * x2. And I spell it out like this for a couple of reasons. First of all, this has a very special form. This is a matrix. It's got a name. We've talked about it a few times. Anybody remember what this matrix is? >> Yeah.

Projection. >> This is a projection matrix. Exactly. Right. So what this is doing is it is projecting X2 onto the subspace [Music] spanned by U1 and the notation we introduced is this would be P U1. All right. So we are saying that um putting all this together we are writing x2 as being the projection of x2 onto that u1 subspace plus everything else everything that got left behind when we did that projection and that would be x2 prime.

Now I'm also going to note from a computational perspective things are even a little bit simpler than I've already written them. And in particular what what kind of simplification might we have here that we haven't taken advantage of? >> Yes. >> Identity matrix. >> Yes, you're thinking exactly the right direction in this setting. So far U1 is still just a vector. So u1 transpose u1 is just a scalar and that scalar value is one.

So this is just one. And so this p uh u1 matrix is simply u1 * u1 transpose. Okay. So because we are forming an orthonormal basis then when we form these projection matrices lots of things are going to cancel out because we're going to have you know matrix inverses that turn into identity matrices all over the place and in this first step that just manifests as this whole um inner product inverses simply being one. Okay.

So x2 we are going to write as simply u1 u1 transpose * x2 plus whatever is left x2 prime. And so now what I'm going to do is I am going to write I'm going to just rearrange the terms and I'm going to write that x2 prime this residual that we care about is simply x2 the original point in our data set minus this projection on to u1 of x2. So we've got x2 and then we subtract off everything that can be represented in x2 using u1 using our first basis vector.

And it's this difference this residual that we want to use to form our new basis vector u2. So u2 is simply going to be the normalized version of u2 prime. this residual I'm sorry let's say U2 X2 prime okay so if we work this out numerically now for our example um when we compute this projection when we compute U1 transpose X2 what are we going to get maybe I'll just change colors here so U1 transpose X2 is equal to y.

So here was our u1 vector and here's our x2 vector and we just want to take the inner product of those two. >> What over roo<unk>2? >> Four. >> Four. Yes. Exactly. This is just 4 over <unk>2. And so now if we were to compute um this expression here, u1 U1 transpose X2 or or maybe I sorry, let's just go straight over here. So if we're trying to compute this residual U2 prime, then we start with X2, which is 1 3 0, and we subtract off U1 times this weight.

So we're going to have 4 over the<unk> 2 * u1 which was 1 over <unk>2 1 over <unk>2 and 0. And so then we have 1 3 0 minus 2 2 0 which is going to give us 1 1 0. And so now if we want to compute U2, we're going to take that vector -1 1 0 and divide by its norm. And what's the norm um of this vector also roo<unk>2 excellent and so I am going to have -1 over <unk>2 1 over <unk>2 and zero. And so my final answer here is that my basis u has got a first basis vector of 1 over<unk>2 1 over <unk>2 0 and a sec.

So this was what we called u1 here and then my second basis vector is - 1 over<unk>2 1 over <unk>2 and zero and this is my u2 vector. So in this example, we knew from the beginning that our subspace was the horizontal plane and it was only two-dimensional. We ended up with a basis that had two basis vectors. Um in addition, when we look at these basis vectors, we can see that they also only span that horizontal plane.

It's a good gut check. Um, and if we wanted to look at this graphically, [Music] then we have the following. So, here's my first, second, and third coordinates. and my x1 vector 1 1 0. This is in the horizontal plane and it's got equal weight on the first and second coordinates. And then the second one is 1 13 0. So I think we would draw that like this perhaps. So this is x2. And then when we go through this Graham Schmidt orthogonalization procedure, then we end up with a U1 that's lined up exactly with X1, but it's normalized to have length one.

Oops. And then we find a U2 that's perpendicular or orthogonal to that using X2. And that ends up being Okay, I might not be drawing it in exactly the right direction, but the point is that it's also in this 2D horizontal plane and it also has length one and it is orthogonal to U1. And so when we went through this procedure after we found U1, we're saying okay, X2 is now in a different direction. So we first figure out how much we can represent x2 using u1.

And so what we're doing with that is we're it's almost like we're taking u1 and stretching it out and seeing what the projection of x2 is onto u1. So here we go. This point here is the projection of x2 onto u1. So what we're saying with this is that we can represent X2 using kind of two pieces of information. First, how long it is in this U1 direction and then everything else which is going to tell us how long it is in the U2 direction.

So for this point X2, now we can write it as a weighted sum of U1 and U2. And the weights are basically telling us how far out, we're stretching these basis vectors so that we can represent x2 now in this new coordinate system. So instead of representing x2 in terms of its x1, x2, x3 coordinates, we can represent x2 as a weighted sum of these basis vectors. So it's giving us a new way of representing x2. >> Yes. >> In the second line here on the right with u1 U1 transpose and then >> right so the question is could we when we're computing this compute this matrix first and then multiply it by this vector you would get the equivalent result but it's much more of a pain.

So in particular um right now we're working with um these vectors u they're three-dimensional so this matrix would be 3x3 but if we were in a million dimensional space the process of first computing this matrix means computing a million by million matrix and then multiplying it by a length 1 million vector. It's much more efficient to first do a matrix a vector vector inner product and then multiply that scalar result by a vector then we never form a matrix.

So mathematically totally the same computationally not the same at all. Yeah great question. Yes. >> Could you explain why the projection of U1 is like U1 U1? >> Okay. So why is the projection onto U1 U1 U1 transpose? So the projection is coming immediately from this notion of least squares. So maybe I'll just give myself a little space and come back over here. So in general we said if you wanted to project onto a space spanned by the columns of some matrix A and we wanted to project a vector let's just say X onto that then the projection matrix that we derived before when we were talking about le squares had the form A a transpose A inverse A transpose X.

Okay, so this was the general form for a projection matrix. Now we're talking about a special case where this matrix A is simply a single vector U1. And so now we're just going to plug u1 into this formula and get p u1 of x is simply equal to u1 time u1 transpose u1 inverse * u1 transpose x. So this is just a direct sort of variable substitution here. Nothing exciting going on. But then we say that this uranspose U1 transpose U1 by construction is equal to one because remember our very first step to compute U1 was to take X1 and divide it by its norm.

So that we know we because we did that we know U1 transpose U1 has to equal one. And so now here we just have a one which we can ignore. And so then this simplifies to U1 U1 transpose * X. And this is what we've been using. >> Yes. Okay, so we've got um I'll just do really big here. U1 * U1 transpose U1 inverse U1 transpose. So u1 is a vector and so in this set this is a p by1 dimensional vector. So in this product this is p by 1.

Um this is this vector transpose is 1 by p. This is p by 1 and this is 1 by p. And so within this parenthesis I multiply these two together. The inner dimensions are what I take the inner product of. So this becomes just a one by one scalar. Yeah. Now more generally let's let U be an orthonormal basis matrix. So remember we said one of the key properties of that is that um u transpose u has to be equal to an identity matrix.

So when that basis only has one element then we're in this u1 setting. But more generally for a basis with more vectors we have that urpose u is the identity matrix. So now if we were to compute the projection of a vector x onto the spa subspace spanned by this basis u. Then again we just plug in our formula u uranspose u inverse uranspose x. But now we use the fact that we know that uranspose u is an identity matrix.

And it I don't know if I've said it explicitly before, but if I take an identity matrix and I compute its inverse, that's still just an identity matrix. Just like if I take one and I divide by one, I get one or maybe not just like, but analogous to. And so in this case, the projection matrix on to u corresponds to u uranspose times whatever vector x. This is part of why people care about orthonormal bases and not just arbitrary bases, right?

So if I think about just think about computation, right? If you give me a basis matrix A, so A's got linearly independent columns, but they're not orthonormal and then I want to project a vector onto that subspace. I'm going to have to do this matrix matrix product and inverse in order to do that projection. that could be a very computationally intensive operation and not something that I want to repeat. But if you give me an orthonormal basis and then ask me to project um a point onto that, then I don't have to compute any inverse of any matrix.

I only ever have to compute matrix vector products. I never have to compute a matrix at all. Well, I got to compute the U matrix, but I never have to compute a big square matrix. So, one of the reasons we care about orthonormal bases and not just arbitrary pairs of vectors or or collections of vectors that span a basis, span a subspace is because we get these very nice simple expressions for things like projection that we would not have available otherwise.

Okay, this is not me just rambling. We are going to use this very soon because once we go to higher dimensional subspaces, we are going to be projecting onto subspaces that are bigger than one dimension. All right, these are fantastic questions. [Music] [Applause] [Music] And I think now, if I remember correctly, we are ready for the full shebang. [Music] Okay. So the input is going to be a set of n vectors in our P which we call X1 through XN.

Um and yeah. Okay. Um and the output [Music] is going to be a basis matrix U and this matrix is going to be P by R. So it's going to have R columns corresponding to the R basis vectors where R is equal to the basis I sorry the subspace dimension. So we're going to have one column for each um dimension or I guess the number of columns is equal to the dimension of the subspace and the number of rows P is now going to be the number of different say features that we have in our feature vectors or just more generally the ambient dimension of all of our vectors.

Okay, so the first step is to pre-process and specifically delete any x i that's equal to the zero vector. So we're just from here on out going to assume that none of our points none of the x i's are equal to zero. You can imagine for instance right if our first vector was equal to zero and our first step is to take that vector and divide by its norm. We're dividing by zero. So we're just zeros don't tell us anything about the subspace because any subspace contains zero.

And so we are just going to totally delete all of the totally zero vectors. Okay. Second we start with u1 our first basis vector being equal to our first vector x1 divided by its norm. Just like we've done in our two examples. so far. And I'm just going to move boards because the sunlight is um causing problems with our video. [Music] Okay. So now for i = 1 or I'm sorry I'm going to start with two 3 all the way to n.

So we're going to continue going through our samples here. We're going to do the following. First we are going to compute xj prime or x i prime. So this is our residual that we've been talking about. which we compute by taking our X I sample and subtracting all of the components of it that are already represented by the basis that we've learned so far. So I am going to have my current basis matrix be U1 all the way to U I minus one.

I've got all of the basis vectors so far and then I am going to project my sample XI onto that. Okay. So let's just unpack that a little bit. This is equivalent just to make sure we understand to saying that we are taking x i and we are going to subtract off all of the components of x i in the u1 direction and then we're also going to subtract off all of the components in the u2 direction and then all of the components in the u3 direction etc all the way up to i.

So when I is equal to two, this is maybe a little bit off, but what I'm trying to say conceptually is that we are subtract, we are doing this procedure that we described before, but now for each of the different basis vectors because now we've got more than one basis ve or make more than one basis vector that we're building off of potentially in later iterations of this loop. So to make this a little bit um clearer in terms of how you would compute this, I would let's just call u um tilda i this matrix that I have up here.

So just all of the basis vectors that I have so far. So then what we're saying here is I'm going to take x i and I'm going to subtract off the projection of x i onto this ui tilda basis. And this we can now use our projection formula corresponds to taking this ui tilda ui tilda transpose time x i and we are just using here exactly the formula we derived over on the right. I guess another way of writing this in case it just adds illumination is we are taking x i and then subtracting the sum from j = 1 to i -1 and we are going to have our vector ui times the weight on that vector that helps makes x i as close as possible to that vector. which we computed before to be the inner product between ui uh sorry u j and x i.

[Music] So what we are doing is we're taking our new point x i and we are seeing how aligned it is with each of the previous basis vectors u.js that we had. This gives us a weight and then we're computing this weighted sum of the previous basis vectors that is as close as possible to x i and that's giving us our residual xi prime. And then we form our new basis vector. I guess this isn't step four. We form our new basis vector ui by taking our x i prime and dividing it by its norm.

I want to be a tiny bit careful here because this is nominally what we would like to do. But we are only going to do this if the norm of x i prime is not equal to zero or I don't even need the norm as long as x i prime is not equal to zero and otherwise did I say equal? Yeah, I meant not equal to zero. Thank you very much. and otherwise we want to skip it. So I'm just going to say that UI is going to be um the zero vector.

This is important because as we saw in a previous illustration, it's possible that some of the XI's are linearly dependent. And so what can happen is that if I get an x i that's linearly dependent on all the previous x i's then this residual is going to be equal to zero. And we want to avoid dividing by zero. So we've got this kind of check here. And so then we end the loop. And then finally, we remove any basis vectors that are equal to zero so that we're only left with a basis matrix that's got no zero valued columns.

Okay, so that's really all there is to it. Um, and what I would like to do now is to work through a slightly more complex example um than we have had so far. Just give me a quick second. Yeah. [Music] So in this example we are going to have x1 = -11 x2 is equal to 1 -1 and x3 is equal to 2 2. Okay, so this is an example where p is equal to 2 and n is equal to 3. So before we get started with just applying our graham orthogonalization procedure, do you have any observations about this collection of vectors or what we might expect for the subspace?

Yeah. X1 and X2 are not independent. >> That's right. X1 and X2 are linearly dependent. Right? X1 is just X2 * negative1. Okay. So now what we're going to do is we're going to work through this Graham Schmidt procedure noting right off the f bat we are going to have linear dependence showing up here and we're going to see how that manifests in this algorithm. All right. So first step U1 is equal to what? Right. We're just going to have -1 over <unk>2 and 1 over <unk>2.

Very good. Next, we want to compute x2 prime, which we compute by taking x2 and subtracting the projection of x2 onto u1. And so this is going to be equal to 1 minus and now we're going to have um u1 -1 over<unk>2 1 over<unk>2 times the inner product of u1 and x2. So what is that inner product? Um, okay. So, let's just do this carefully. So, we've got -1 over<unk>2 * 1 over <unk>2. This is u1 transpose * 1. So, to do this, we're going to take the first entries and multiply them together.

So we get -1 over<unk>2 and then we're going to add that to the product of the second entries which is -1 over <unk>2. So then we're going to get 2 over <unk>2. Yes. Okay. So then we get -2 over <unk>2. And so moving forward we have 1. This is our x2 vector. And now if we multiply this weight times our u1 vector we are going to get here um -2 over <unk>2 * 1 over <unk>2 is going to be >> positive 2 over >> 2 which is 1 and then in the second entry we're going to have -1 and so this difference now is equal to I heard it earlier zero [Music] Okay, so this is an indication when we get this residual equal to zero that we have hit a vector that is linearly dependent on the vectors we have already processed which was obvious in this toy example but if you know if you've got like just a real data set and things are a little bit more complex it might not be as apparent by inspection.

Um but nevertheless we get this this indication. And so then we move on to the third point. So we're going to compute x3 prime which is x3 minus the projection onto this basis now of u1 and u2. So this is sort of what we're calling u2. But like I said, we're going to get rid of that at the end because we don't want zero valued basis vectors. Um, so we're going to compute the projection of x3 onto this basis that we have so far.

And the only part that really matters is u1 and then we've got x3 here. And so we're going to have 22 minus and then our u1 vector is -1 over <unk>2 1 over <unk>2 times the inner product. Maybe we'll just be super pedantic over here too. So we're taking the inner product of u1 and x3 and so we are going to get -2 over <unk>2 + pos2 over <unk>2 which is equal to zero. Good. Okay. So then the residual is simply 22. And so our final basis vector is going to be this divided by its norm which is simply going to be 1 /<unk>2 1 over<unk>2.

And so putting all the pieces together our final basis is -1 over<unk>2 1 over<unk>2. This is our u1 vector and 1 over <unk>2 1 over<unk>2 and this is our u3 vector. Yes. >> Um in this case U2 turned out to be this or we got this zero vector. So we don't want to incorporate that into our basis. If it had not been a zero vector then we would incorporate it just like we did with um X3. So you know if if it helps you could just imagine that this X2 points it didn't even exist.

We skipped all this and then this part here would tell you what would have happened if we hadn't had this linear dependence. Right? So we compute the difference between our point and its projection onto the basis that we have so far or onto the subspace spanned by the basis that we have so far and we then normalize and we get our final or we get our new basis vector. >> I guess my question was what would we do if x2 was not a zero vector for example? >> Right.

So if x2 had been 1 one so it's no longer linearly dependent on x1 then we would have had a nonzero vector here >> and we would have just normalized it divided it by its norm and that would have been our new basis vector. >> Okay but when we calculate x would that have factored in or no >> so in this case we have vectors in a two dimensional space but we have three vectors. So one of the things I' I've tried to say for a few lectures now and I I think it's the importance of it hasn't really like become apparent until now is that when you're in say a pdimensional space the most linearly independent the biggest number of linearly independent vectors you can have is p.

So the fact that I'm giving you three points in a two-dimensional space immediately is a sign that there's going to be linear dependence. there's just no way you can't have it because we can only have two linearly independent vectors here. So before we did any calculations at all, you would know that there's no way we're going to have three basis vectors even though we've got three points. So this is just generally true whenever you've got P, your dimension being less than N, the number of points.

Yeah, great point. Any other questions? Yeah, >> if I may clarify like >> Yeah. I I would say as soon as you find a basis vector that's equal to zero, just delete it. Don't append it to your basis matrix. Yeah. Yeah. All right. So, next time we are going to talk about an alternative way of finding a um basis for points. In the lecture notes that will be posted online, there is one additional example of Graham Schmiden in action.

So, please take a look at it and um it'll also give you a little bit of a a preview of where we're headed with the SVD. Thanks very much.