Lecture 7 Fall 2025: Introduction to the Singular Value Decomposition transcript

All right, welcome back everybody. So last week we talked about learning bases and subspaces and in particular finding the Graham Schmidt orthogonalization procedure to find a basis for the subspace spanned by a collection of samples. So today we're going to talk about um another approach to finding a basis for the subspace spanned by a collection of data points using the singular value decomposition. [Music] Okay, so the SVD is not only useful for finding bases, but it's really a huge workhorse for almost all of machine learning.

It's an extremely important topic. Um, and it's going to build upon things that we've been talking about already all quarter. So to get started, let's go back to the general setting that we were considering last week. So imagine that I have a whole bunch of samples XI that are all in 2D and I'm just going to make a plot of them here. So this point here is my first sample, but then I've got a whole bunch of others that look like this.

Okay, so these are my n different samples. And now let's imagine that we were to apply the Graham Schmidt orthogonalization procedure to learn a basis for these samples. Um I we're in 2D. This is pretty trivial, but if what specific basis would we find if we were to perform Graham Schmidt on this data? What would be the first basis vector? >> Yes, >> that would be 01. >> Yeah. So, it would just be exactly this vector here.

This is the U1 that we would find with Graham Schmidt. And then our second basis vector has to be orthogonal to this one. And so depending on which point is x2, it would either be um this or it would be the um the sign opposite of that. So there's there's a little bit of sign ambiguity perhaps. Um but other than that, these are the two sort of basis vectors that we would learn for this data set. And one of the things that we said last week is that if we were to just shuffle the order of all the XI's so that X1 was a different data point then we would have a different U1 and a different U2.

Every time we shuffle the order of these exact same data points we get a different basis out of the Graham Schmidt procedure. So today what we are going to talk about is another way of finding a basis for these points. And what we're going to find is that the first basis vector and I'm going to write that here as V1 and it also has length one here is going to be coming out of the singular value decomposition [Music] and it is going to vary in the direction of maximum variation among the data points.

So this is going to correspond to if we wanted to find a onedimensional subspace that fits our data, which one is closest to our samples? And then the next basis vector is going to have to be the same length and orthogonal to that. And so we might have a vector V2 that looks like this. So we're finding now a different basis. This basis in particular is going to be um invariant to reshuffleling our samples. No matter which sample I call X1 versus X2 versus X3, I'm going to get the same vectors here. again modulo some sign ambiguity I might have gotten like that V1 is pointed this way or V2 is pointed that way but the the orientation of the axes would be exactly the same no matter how I shuff my samples and this is what we are going to learn about today and so in particular V1 and this is what we're really going to focus on today is just that first basis vector and then we will build on that to get the entire singular value decomposition.

But this first basis vector corresponds to um the best one-dimensional subspace fit to the x i's. [Music] And in general, we are going to continue to build upon this by finding a succession of 1D basis or 1D subspace fits to the data and different residuals. So understanding how we find this first 1D subspace fit, this first singular vector is essential to understanding the entire SVD. Now before we proceed, I want to make a very crisp and clear distinction between what we're doing when we find this best 1D subspace fit and what we've done previously when we have done regression.

So in particular in the regression setting when we have done least squares in this picture I'm going to have each x i as just being a scalar value. And so we might have samples where we've got the x eyes on the horizontal axis and the y eyes on the vertical axis. And then we've got a whole bunch of samples here. And I just want to actually draw this in a more extreme way like this. And so what we did when we were doing regression is we were trying to find a line here that was a good fit to the data.

And when we minimized least squares, what we were doing is for each point we were seeing how big this residual was. So if this point were X I, then this residual would be R I. And in this particular case, that residual is just a scalar, right? Right? It's the scalar distance from this point to of the sort of y value for this point and the y value for the line. And so what we were doing is we were choosing the weights to minimize the sum from i = 1 to n of these different squared residuals.

And so for each point we would have this squared residual measuring how close the y label for our training sample was to the predicted y label given by this regression this green line. Okay. So now today we're going to be talking about something that's a little bit different from that where we are going to um find the best 1D subspace fit to points xi in two dimensions. So our picture might initially look the same, but what I'm plotting here now is the first coordinate of each xi versus the second coordinate of each x i.

And I might have in this plot even the same kind of set of points perhaps. We'll do our best here. And now what we're doing is we are again trying to find a 1D subspace. So a line like this. But now when we talk about finding a best 1D subspace fit, our objective here is a little bit different. We don't have labels and instead we are looking at how far from like a ukitian distance spa perspective each point is to the line.

And so this now would be my residual. This is a 2D vector and I am trying to minimize these distances. So each of these dotted lines I'm drawing is perpendicular to the 1D subspace. So I'm basically trying to find the closest point on the 1D subspace to my actual training sample here. And I'm trying to find the subspace that's as close as possible to all of these different 1D or all of my different training samples. So this is qualitatively different here.

And so now what we're trying to do is to find the 1D subspace that minimizes again the sum from i= 1 to n of these residuals. But now these residuals are these 2D vectors. And so we're going to try to minimize the norm of these 2D vectors or the squared norm of these 2D vectors. Okay. So is the distinction here clear? We're still going to be using the ideas from le squares that we've covered previously in this class.

But the geometry is a little bit different here because instead of trying to find a pred line that corresponds to predictions coming out of corresponding to that line where we have labeled data here instead we have no labels. We're just having feature vectors and we're trying to find whatever 1D subspace is closest to all of those feature vectors. Any questions about this so far? >> Yes. So this right side that's to confirm the uh the singularity composition that we're doing >> right with the singular value decomposition.

This is how I I don't want to get too much into jargon, but as a preview, this 1D subspace that's closest to all the XI's, this is going to correspond to the first right singular vector. Okay, so we're going to talk more about what we mean by right versus left singular vectors. What exactly we mean by singular vectors, but we are just today going to focus on this idea of finding a good 1D subspace fit. This is going to tell us one small component of the singular value decomposition.

But once we understand this, all the other components are going to very easily just fall right into place. Yes. Did you have a question? again like singular value decomposition doesn't need to be labeled >> right the singular value decomposition is something that we're doing without any labels at all we just have a collection of training feature vectors and what we're doing at least in this very first stage is trying to find a one-dimensional subspace that's as close as possible to all of our feature vectors so no labels are required for So what we're going to see is that people use this for all kinds of things.

One way in which you might use it is to reduce the dimensionality of your data, right? So you could say, well um h let's imagine we're in this Netflix example where we've got a whole bunch of X eyes that correspond to the movie ratings for all of our different customers. So each point I corresponds to a different customer. Um so I've got a vector of say P different movie ratings for each of my different customers. And so now what I could do is I could just store all of those raw movie ratings.

Or I could represent each one as a weighted sum of just a small number of representative movie watchers. So we've said before that this seems plausible and we've used it to introduce the notion of matrix uh matrix products but what we'll see is that this notion of the singular value decomposition gives us a way to take that full matrix of movie ratings and identify painlessly what those representative movie rating vectors might look like.

And so um for that we don't need any labels. We just have these vectors of ratings. Any other questions? >> Yeah. >> What's the sub? >> Oh, yeah. Sorry. Um, this is just something I do by by habit. So when we write when we have a general vector a and then we have the norm and we write let's just say uh p here what that means is that we are going to sum over all the entries um shoot I'm just going to write this as sum over j of all of the entries aj to the p power and then at the end I take that to the 1 over p power.

And so often or well typically when you see something that just looks like this, the norm without anything in the subscript, then we assume that it's a two because pals 2 is by far the most commonly used one. Um in machine learning context, sometimes we will often see pals 1. We might talk about that later in the quarter. Um but the two just refers to this as being so what this is here is just the sum of the squared entries of the RA vector.

Okay. So as you might have guessed what we're doing here is if if we knew what this green line was we are taking each sample and projecting it onto the green line. Right? So in order to understand how we find that green line, we need to um talk a little bit more about projection matrices because we're going to use some facts about projection matrices in order to um find the best green line. So [Music] more information or facts about projection matrices.

So first of all um just recall from previous lectures that if we wanted to talk about the projection onto a subspace S that's spanned by the linearly independent columns. of a matrix A, then we can write the projection matrix as PS. And in this class, we will equivalently write PA. And we mean exactly the same thing whether we write it with the S subscript or the A subscript. And we have a formula for that. It looks like a * a transpose a inverse time a transpose.

So this is the projection matrix that we talked about and derived earlier in the context of le squares. So special case if a only has one column little a. So in other words, this subspace is one-dimensional. Then this projection matrix PA looks like A * A transpose A inverse A transpose. Okay, we talked about this last time as well. Um if we are given a point Z that is inside our subspace already and then we try to compute the projection of that point onto the subspace then we are just going to get that point back.

And remember the reason for this is that what the projection is doing is it's saying find the point in the subspace that's as close as possible to Z. So if Z is already in the subspace then Z is the point closest to Z and so the projection doesn't do anything. Okay. So the reason that this is important or or going to come up is that if I were to compute a projection matrix squared. So in other words, if I compute a projection matrix and then multiply it by a projection matrix, then that just gives me my original projection matrix back.

Okay. So, first of all, intuitively, this should make sense because if I take a point and I project it onto S, then I'm going to get a point Z that's in that subspace. And so, if I project it onto the subspace again, it's not going to do anything. And so, one projection is enough. I don't need to project a point multiple times onto the same subspace. But we can also see this um just algebraically because in particular we could compute PA a squared.

So I just plug in my formula here. I get a * arpose a inverse arpose. That's my first pa. And my second pa I'm going to have a * arpose a inverse arpose. And then when I look at this, maybe it'll be more helpful if I just put some parentheses around to this. I see I have a matrix here that's multiplied by its inverse. So these are going to cancel out with one another. And so what I'm left with is a * a transpose a inverse a um transpose.

Wait, sorry, that's inverse. That one's transpose. And this is just our original PA. Okay. So, we've seen this now algebraically, but also we've got this sort of geometric perspective of it. Any questions about any of that? >> Yes. >> So, like for this like finding the closest distance to all the feature factors. Yeah. >> If we have like more than feature vectors. Are we still finding a line? Are we like finding something nice? >> So in this case, we have many feature vectors.

We've got one 2 3 4 5 6 7 eight eight feature vectors. Each yellow point here corresponds to a different feature vector. So I'm not I'm in two dimensions, but the fe the number of feature vectors. So this is in the um uh notation previously. This is a case where P the dimension of each feature vector is two and N the number of features is equal to eight. So the story is the same if we have a different number of feature vectors.

Now if you're saying what if the num what if the dimension of each feature vector were higher um still the first step is to find the best 1D subspace. So even if we were in three dimensions or four million, we would still as a first step be thinking about the best 1D subspace fit. [Music] Okay, the other concept we need to introduce is the notion of an orthogonal complement. Okay, so given a subspace s the orthogonal um and maybe I'll just yeah say spanned by the linearly independent columns of a matrix A.

The orthogonal complement is the set of all vectors. B orthogonal to all the columns of A. Okay, again this sounds a little bit abstract. So let's dive into an example where I think there's a very clear geometric interpretation that helps me personally a lot. So for example, we could have a subspace s correspond to all points in three-dimensional space where um the third coordinate x3 is equal to zero. And this is a subspace that we have seen before.

Um, so we can just draw it again. So here's my first coordinate, third coordinate, and second coordinate. And in this case, that subspace S corresponds to the horizontal plane. And like before, I want to emphasize the subspace goes infinitely far in all directions. I'm just drawing it this way to kind of convey it's the horizontal plane. It's a little hard to do on the board. Okay. So now we can think about well what is the orthogonal complement?

Any thoughts on what that might be? >> Yeah, >> exactly. So the ortho orthogonal complement and I'm going to write this as s and then with a little perpendicular sign as a superscript is going to correspond to all the vectors x that are also in 3D that where you have the first coordinate and the second coordinate equal to zero. And so this would be vectors of the form oops 0 0 and then some value let's just say alpha.

And so in our picture here the orthogonal complement is corresponding to all vectors that look like this. So this here is going to be our SP. Make sense? >> Yeah. >> Just like an upside down T like >> Yeah. An upside down T um is a good way to describe it. Um, if you're into latex, this would be perpet [Music] Let's let um S be a subspace that's spanned by R linearly independent columns of A. um and we're going to imagine that this subspace is inside an uh a pd- dimensional space.

So we're in a pd- dimensional space, but the subspace is rd dimensional. So for instance, in our previous example here, we had that we were in a three-dimensional space and our subspace dimension was two-dimensional. It was just this 2D plane. So more generally, we're in a pd- dimensional space and we've got an rdimensional subspace. So this means that A is going to be a P by R matrix where those R columns are linearly independent.

Then we have SP as the orthogonal complement and we are going to let another matrix B um be a basis for this orthogonal complement SP. So because of that, if we were to look at the product A transpose time B, that is going to have to equal zero because every column of B since it's in this orthogonal subspace uh or orthogonal complement of the subspace has to be perpendicular to every column of A. And when we compute this product arpose b what we're doing is we are computing the inner products of every column of a with every column of b.

And we know just by the definition of orthogonal complement that all of those inner products have to equal zero. Um [Music] And furthermore, if B is a basis for that orthogonal uh complement, then it corresponds to a matrix that also has P different rows because we're also in P-dimensional space. But the number of columns now is P minus R. So if we go back to our previous little example with the horizontal plane then here A the MA matrix A would be a basis that spans this 2D plane and B would be a basis corresponding to this orthogonal complement.

So if we're in a 3D space and our subspace is two-dimensional, then A would have two columns and our orthogonal complement has to be one-dimensional because there's only one dimension left that's not in the subspace. And so here we would have a basis matrix A that is 3 by 2 and a orthogonal complement B basis B that is 3 by 1. Okay. So one of the reasons that this is significant and important is the following. If I were to take any point x that's in this pd dimensional space, I can write it as a sum of the part that is in the subspace s and the part that is in the orthogonal complement b.

So if I know what these basis matrices A and B are really if I just know A from there I can figure out a B and then there's always going to be vectors weight vectors U and V. So I can write any point at all X as a weighted sum of these components. Um so this here corresponds to the projection of my vector X onto the subspace spanned by A. So this is equivalent to the projection onto curly s of x. And this second part is the projection of x onto b or rather the orthogonal complement of my subspace here.

So I can always write any point as the sum of the part that's in the subspace and the part that's orthogonal to the subspace. And if we go back to our example over here, then this is saying for any point X in 3D, I can write it as the part. So if I've got an X here, I can write it as the sum of the part that's in my original subspace. So this here would be P A of X plus the part that's in the orthogonal complement. So this part here would be P B of X.

So if I've got a vector x that um I had that has entries let's say a b and c. I can write this as the sum of the projection onto the horizontal plane which would just be a b and zero. This is in my subspace s plus the part that's in that orthogonal complement z c. So this is the part that's in the subspace and this is the part that's in the orthogonal complement to the subspace. So in particular, what this tells us is that if I were to take a projection onto A plus a projection matrix onto its orthogonal complement spanned by B, that that's going to have to be equal to an identity matrix.

Okay? Because what we've written here just to be clear is that X is equal to P A of X plus PB of X which means that it is P A + PB of X and the only way this is possible is if PA and PB are equal to the identity matrix. So equivalently the projection on to A is simply the identity matrix minus the projection on to B. And so what from there we can say that whenever we have an identity matrix minus a projection matrix it is also a projection matrix.

Okay, I'm happy to pause and answer any questions. I think this seems like a big list of facts and maybe it seems a little irrelevant to where we started finding a 1D subspace fit to a collection of data points, but we're going to use all of this information um on the next board unless there are any questions first. Yeah. explain what does it mean? >> Um I'm saying that if I take a um projection matrix PB and subtract it from the identity matrix then that difference is itself a projection matrix.

That's all I mean by that also there. Yes. Okay. Um so the question was about this board and you said why can't I think about this is the norm of the residual squared but that is what I meant. Yes, that's true. We could think about this as the norm squared. In this particular case, when we're just in 1D, then the norm is a scale or well, we just have scalers, so you don't need to write the norm notation. The bigger point I'm trying to make here is not like whether it's a a norm or not, but rather what distance it is that we're measuring. how we're measuring the distance to the line.

So when we talk about fitting a 1D subspace, we're really talking about the distance between a point and its projection onto the line. Right? So this is going to correspond exactly to, you know, taking a projection as we've been talking about for the last few minutes. Whereas when we were doing le squares regression, we're not really doing projection the same way. We're rather saying I've got a training label and I've got whatever label will be predicted by this regression line.

And so the way that we measure how close our um line is to our training data is measured in a different way. Here we're using labels to measure it and here we're using um there's no labels. We're just looking at projections onto the line. Yeah. Yes. Okay, so there's two separate things going on here. Here I just have an arbitrary basis, not necessarily orthonormal. Um, but I can still have an orthogonal complement to the basis even if I'm not or I'm sorry, an orthogonal complement to the subspace even if I'm not representing that subspace with an orthogonal basis.

Okay. So when we talk about orthogonal bases like with A and B, we're just talking about how we are representing the subspace, right? We're using the matrices A and B to communicate what subspace we're talking about. But when we talk about orthogonal complements, this is a a geometric notion that exists independent of the way we choose to describe those the bases for those subspaces. So if we go back to our little um 2D plane example here, right?

Um regardless of how I choose to represent these subspaces, I have this horizontal plane subspace and then I have sort of the vertical subspace that's orthogonal to it. whether or not I choose to use an orthogonal or orthonormal basis to represent these. So nothing that I did on this middle board here is assuming that these bases A and B are ar orthonormal bases. >> So the problem lies on whether it is mobilized or both like it is also not necessarily to be.

So if we go back to this um third board, we talked about projection onto a subspace where we've got a matrix that corresponds to a basis where in this case we're only assuming that the columns are linearly independent and nothing else. Give a little bit more room. [Music] If you is ortho normal basis matrix for our subspace S. Then the projection onto S corresponds to the projection U. And we can write down our formula which was just u * uranspose u inverse uranspose.

And then in this case because it's an orthonormal basis this would just have to be an identity matrix. And so we would have upose. So the projection matrix has a particularly simple form in the special case when we have an orthonormal basis for it. Um, and like you said, you can use it to compute the projections that we were talking about earlier with the subspace and its orthogonal complement. But a subspace has an orthogonal complement regardless of whether we choose to represent that subspace using an orthonormal basis. >> You you got it.

You sure? >> Yeah. Yeah. I previously assumed that >> I I think I understand what you're saying. So before we wrote any x can be written as a * some vector u plus b * some vector v. So we can write a point x as its component in the subspace plus its component outside the subspace. And in particular, this is the projection of x onto a plus the projection of b, I'm sorry, projection of x onto b. And this does have the form a ar a transpose a inverse arpose x plus b branspose b inverse brpose x.

Um, and so we it's not just like some we don't know what U and V are. We have very specific forms of U and V. This is going to be U, and this is going to be V. And these do correspond in fact to what you would get if you were to try to find the least squares estimates of U and V, right? So it all goes back to lease squares. Um, and if we had orthonormal bases, this equation would be even further simplified. I think that answers my question. >> Super.

Okay, great. Any other questions? >> Yes. >> So from um this here right what we've written is that X is equal to P A of X plus P B of X. So now I'm just going to gather terms and say this is P A plus P B of X. So now I'm saying X is equal to this matrix time X no matter what X is for all X's in so this is for all X in my P-dimensional space. So what matrix would make that true? the identity matrix. And so that's how we get that if I were to take the projection onto a subspace, the projection matrix onto a subspace plus the projection matrix onto its orthogonal complement together those are the identity.

[Music] Okay, super question. So now we will actually talk about finding a 1D subspace fit to a collection of points. [Music] All right. So we've got our axes here. [Music] And we've got our collection of different samples and we are going to try to find a good 1D subspace fit. And I am going to write that vector that spans that subspace as a and that is going to have an orthogonal complement which I can draw like this.

So this is I'm going to write that as a perp. So that's the orthogonal complement to that subspace. All right. So let let's consider maybe a more extreme point out here. Here's a point x i. And so now, as I said before, we can project that point onto the subspace spanned by a and simultaneously we can take that point and project it onto the orthogonal complement. So this is the projection of x i onto the subspace spanned by a perp.

So when we think about how well this subspace A is fitting our samples, we can now think about the distance [Music] of X I to the subspace spanned by this vector A. And what does that correspond to? Well, I'm going to look at this point x i minus its projection onto a. And sorry, the sun came out and the um video doesn't record anything in the sun. Okay, so going to look at x i minus p projection onto this span of a of x i. and we're going to look at that squared distance.

And so what we have here is I'm going to gather my xis together and what I've got left is the identity minus the projection onto a. So given everything we've been talking about for the last I don't know 10 minutes or so what is this identity minus PA? Yeah. >> Right. This is exactly the projection onto the orthogonal complement which in this case we are now calling a per. And so in our picture here what we are doing is we are looking at the projection of x i onto that orthogonal complement and we are seeing how long that vector is or how far away that is from the origin.

Okay. So we're going to measure that distance. This is what we are going to call what happened to my white there. um we're going to call this diar for that e distance squared. And now what we want to do is we want to break this down a little bit, get a simpler expression. So the first thing I'm going to do is recall that if I were to have for a vector uh I don't know, I I don't want to use a again. Let's just say uh v squared.

This is just vanspose v. So I'm going to use that here. And so what I'm going to have is PAP * XI transpose time PAP time X I or rather X I transpose P A P transpose PAP XI Okay. [Music] Now we can use the fact that this corresponds to x i transpose pa per squared x i. And what did we say about squaring projection matrices? Yeah, >> it's the same as >> same as a single projection. So now we've got XI transpose PAP XI.

Okay. [Music] Sorry. I guess it's okay. Just erase this one. [Music] All right. So we are trying to write down this squared distance of a point to our uh line and we said on the previous board this is xiranspose pa xi and now we are going to plug in the form of pa perp and so actually I think it'll be a little bit easier to write this as x I transpose * i - p a * x i. And so what I'm going to get here is xirpose xi minus xirpose and then pa is going to be uh a ar a transpose a inverse arpose x i.

So just plugging in the form of our projection matrix. Now in this case a is a vector. So this arpose a is simply a scalar. So we can equivalently write this as xirpose x i minus x i transpose a a transpose x i divided by a transpose a. [Music] Okay. So now we have an expression for the distance of a point x i to the subspace spanned by a vector a. Now what we want to do is minimize [Music] the sum from i = 1 to n of these di squares.

We want to find the subspace a that minimizes the sum of these squared distances. So we are looking for the minimum with respect to a of the sum from i = 1 to n of x i yeah xpose x i minus xpose a arpose x i divided by arpose [Music] Now when we look at this similar to something that we observed in le squares this first term here is independent of a. So when we're trying to find the best subspace fit, no matter what subspace we choose, this first term doesn't matter at all.

And so we are going to ignore it and we are going to say, okay, moving forward, what we want to do is we want to search among A's and we're going to look at the sum from I = 1 to N of just this second part. We've got xiranspose a ar a transpose x i divided by aranspose a. And here we were minimizing the sum of the negatives but equivalently we can just maximize this and then instead of carrying around this denominator which is a bit of a pain.

What we are going to do is we are going to maximize and we are only going to consider vectors A which have unit norm right we want orthonormal bases we want basis vectors that have norm one so we're just going to constrain our search for the best 1D subspace by looking at vectors that have unit length and if they've got unit length then that means arpose a is equal to one so we don't have to worry about the denominator anymore.

So now we just have the sum from i = 1 to n of x i transpose a a ar a transpose x i. [Music] So now what we can do is we can write a matrix X which is going to correspond to our X I. So we've got X1 transpose X2 transpose all the way to XN transpose like this. So this is an N by P feature matrix just like we talked about in the context of le squares. And now what we are going to do is we are going to rewrite this um objective function using the matrix.

So instead of having a sum over all the x i's we're going to use matrix vector notation. And so what we get is that this is the same as maximizing over all basis vectors a where the basis vector has norm equal to 1. And it's going to look like a transpose xrpose x a. And so the best 1D subspace fit to our n different samples is going to correspond to the a that maximizes this expression and which has norm or length equal to one.

So in particular, the vector A that achieves, this maximum is denoted V1. This is what we had on the very first board today and called [Music] the first right singular vector of the matrix X. Okay. So, I want to flush this out a little bit more, but are there any questions so far? Yeah. >> So, um the question is why do we want a or v1? Why do we want it to have norm one? And the answer is that first of all we've our our goal is to find orthonormal bases.

So we know we want basis vectors that have norm one. It's convenient. It makes things like computing projections easier. And so it's a good kind of just standardization. Um secondly imposing this constraint that the norm is equal to one allows us to avoid having this denominator. So it makes this maximization problem not have anything in the denominator. It I mean it is a choice. This is how we choose to define the singular value decomposition. we choose to define it in terms of bases that are orthonormal.

Um, so you could imagine somebody making a different choice where they don't make this constraint. And if all we cared about was finding a basis, then I guess like if we go if we think about um our example over here in 2D, right? So we know that the subspace is this white vector here. But there's many different basis vectors that we could write of all different lengths. So there's no unique basis vector that corresponds to this subspace.

So what we what we've really done here at first is we've tried to find the best 1D subspace. Now we have to make a choice. what is the um choice of basis vector we're going to use to represent that subspace? There's infinitely many. And so just to kind of keep things standard so we all know what we're talking about when we talk about the SVD, we make the choice to just say, well, we're only going to consider basis vectors that have length one. >> Yeah. >> Yes. >> Why? >> Oh, projection matrices are symmetric.

So if I were to look at PA um transpose then this is equal to well first let me write PA which is A * A transpose A inverse time A transpose and now if I take that whole thing and transpose it remember that when we take the transpose of a product of matrices then we reverse the order and transpose each factor. And so we first take the transpose of arpose which is a. Then we take the transpose of arpose a inverse. But this is a symmetric matrix.

So the transpose doesn't do anything. So I get a transpose a inverse. And then finally I take the transpose of a and I get a transpose. And this is exactly pa. So PA transpose is equal to PA which means that so all right first PA transpose is equal to PA and we can also say PA is symmetric. I mean these two things mean the same thing. Um and so that's why in this expression here I said PA transpose PA is equal to PA^2.

Any other questions? Yeah, >> I'm not entirely clear on how we get from uh the equation you have on the upper right of the center or the one that says like max of xrpose a ar a ar a ar a ar a ar a ar a ar a ar a ar a ar a transpose x i how you get from that just because you make I'm not sure how you get from there to mapose >> so I just want to make sure so you're saying how did I get from here to here >> exactly Okay.

Um, yeah, I forgot what board I'm on. And we're Okay, but I guess I guess I can use this one. [Music] All right. So when we look at xiranspose a a transpose x i it's important to remember that all these things are vectors of the same length and so this inner product is just a scalar one by one right one by one so I can swap the order it doesn't matter normally if I'm just swapping like the order of matrices that I'm multiplying I can't do that but when things are scaled I can swap the order.

So this is the same as a transpose x i x i transpose a. Now if I were to look at the sum over i of this, then what I can do is I can well the sum doesn't affect the a's. I can pull the sum in. So I'm going to have a transpose times the sum from i = 1 to n of x iixir transpose time a like that. And now if I think about well what is this sum of x iixi xirposes how can I write that then that is going to be exactly xtranspose a does that answer a question super any other questions [Music] one thing I want to mention now before we move forward forward is that we boiled everything down to this optimization problem here.

So when we did le squares regression or classification before we had an optimization problem and then we derived a simple closed form expression for the solution to that is not something we can do here. So in order to find a, we really do have to use um sophisticated iterative optimization techniques in order to find the A that achieves this maximum. In this class, we're not going to talk about those methods. They're beautiful code bases mostly written in forran that do that for us.

And so we will use software packages that will compute singular values and singular vectors. So it's important to understand what it's doing but this is not something where you can just solve this easily on your own. Okay. So the next thing um I wanted to say is just to set up a little bit more notation or vocabulary. So another way of saying what I wrote on the previous slide is that this first basis vector v1 is equal to the argument that maximizes over a of over all a's with norm equal to 1.

This a transpose xrpose x a. We also are going to have another variable sigma 1 and sigma 1 um well uh is equal to the actual maximum value that this takes. So we've got the same optimization objective function just arrpose xrpose x a but here v1 is finding whatever vector achieves the maximum and sigma 1 is the maximum value and so this is called the first singular value of the matrix X. We're going to talk more about how to interpret that number and how to think about it in the next few lectures here.

But this is also equivalent to taking this v1 vector and computing it transpose x transpose x v1 v1. So sometimes people also call sigma 1 um the operator norm of a matrix. And they will write it as using the same norm notation of the matrix. And they might write OP here for the operator norm. Or sometimes people will write it with this little two down here. All of these mean exactly the same thing. It's the first singular.

Oh well, sorry. Sigma 1 is the square root of this. Apologize. And this is the first singular value. All of these mean exactly the same thing. Now I want to be very careful here. There are different ways we can compute norms of matrices. So an alternative is the Frobenius norm. And the probinius norm is equal to the sum of the squared entries. So this is just equal to the sum from i = 1 to n and j = 1 to p of x i j^2 and um well the square root of all these things and so this we write as x with a little f here for froinius norm.

So I just want to pause for a moment because this is something that certainly messed me up when I was first learning this and I've found many students get confused by this. When we're talking about the two norm of vectors, we sum all the entries and then or all the squared entries and then take the square root. When it comes to matrices, summing all the squared entries and taking the square root is the frobinius norm.

And when we've got this little two here in a matrix norm, it does not mean taking the sum of all the squared entries and then taking the square root. It means this other thing. It means this operator norm. These are not the same thing. Okay, so it's a little perhaps confusing that this two subscript on a norm um can feel like it has a very different meaning for matrices versus vectors. And so I just want to draw attention to that so that nobody forgets.

Okay. But one of the reasons why I'm mentioning this is not only to draw this distinction but also to give us a little bit of interpretation for sigma 1. So in particular when this operator norm or this first singular value is big relative to the froinius norm of a matrix. It means that the x i's are close to a 1D subspace or in other words the matrix x is almost rank one. [Music] So these singular values are telling us how well we can fit or the first singular value is telling us how well we can fit a 1D subspace to our data.

I think I have an example of this. Oh, okay. Well, next lecture, let me make a a smaller toy example. Right? I could have a matrix that looks like 1 2 3 and then 3 6 9. This has got one column that's a weighted version of the other column. So this matrix is rank one. Okay. Alternatively, I could have a matrix that's like 1.1 2.2 two and then 2.9 and then say 369. This is rank two. But we can see that it's close to being something that's rank one, right?

And so often things are not exactly in real world, we've got data, it's messy. Things are not exactly low rank or say rank one, but they're just close to something that's low rank. We find this in many many real data settings. And so the singular values are going to be telling us information about how close a matrix is to being low rank. Um and in particular when sigma 1 is big relative to the froinius norm it's going to be an indication that even if we're not in a rank we don't have a rank one matrix we do have a matrix that's somehow close to being rank one.

Okay so even though we've got this relatively abstract seeming definition this is telling us something very concrete about the nature of our data. So if we think about for instance this running example we've had where we have images of people's faces or and we construct features say the distance between the left eye corner and the left mouth corner and the distance between the right eye corner and the right mouth corner.

So for most people those two distances are not exactly the same or all a little bit asymmetrical but they're highly correlated with one another. So if I formed a feature matrix with just those two features, then it would be something like this. It's going to be rank two. Those two features are not exactly the same or linearly dependent, but they're pretty close to something that is right. So before when we talked about le squares, we talked about whether our features were linearly independent or not.

In general, a lot of times our features really for real world data really are linearly independent. Um, but they're really highly correlated and close to being linearly dependent. And the singular value decomposition gives us a principled way of thinking about this notion of being close to low rank or close to linearly dependent. And we're going to see more about that coming up. Yes. >> What is the range of sigma 1? something like if sigma 1 is one that means it's exactly dependent.

So what are the range of values that sigma 1 can take? I think yeah if x is the zero matrix it could be zero. It's always non- negative. And then um the biggest it could be is actually the frobinous norm of the matrix um the sum of all the squared entries. Okay, you guys have asked so many wonderful questions today. This is not