Lecture 8 Fall 2025: Singular Value Decomposition transcript

All right, welcome back everybody. So, today we're going to continue our discussion of the singular value decomposition. So, last time we said imagine that we've got a collection of points. And we denoted these XI and they were all P dimensional vectors for I equals 1 to N. We wanted to find the best 1D subspace fit to those points. Or more precisely, an orthonormal basis for that 1D subspace fit. And so, our basis vector which we called V1 is going to be a P dimensional vector just like all of our samples.

And we said that the way that we could find this, we derived an expression that said that V1 was the argument that maximized. So, we searched over all vectors A that were in this P dimensional space and we constrained our attention to vectors that had length or norm equal to 1 because we wanted a normal like we want normalized basis vectors. And we said we're going to find the one that maximizes the sum over all of our samples of A transpose XI XI transpose A which is the same as the argmax sum over I of the um of X I transpose A squared.

Then what we said is is that if we were to let the matrix X be composed of all of our different vectors. So, we have X1 transpose X2 transpose all the way to Xn transpose. So, this is our n by p matrix of feature vectors. Then we can equivalently write V1 using that matrix as the argument that maximizes over all vectors A with length one. Um uh A transpose X transpose X A. And then what I claimed is that this V1 is the first right singular vector.

And the other thing that I said is that if we were to take this expression and just plug in V1 then we would get So, if we look at V1 transpose X transpose X V1 then this value we're going to call sigma one squared or maybe a little bit more. Clearly, I'm going to write the square root of this quantity as sigma one, and we call this the first singular value. It's just the value of the subjective function for that best 1D subspace fit.

Okay, so this is where we left things off last time. And now what I want to do today is to talk about the full singular value decomposition. All right, so given a matrix X that is n by p, the singular value decomposition, which we write as SVD, is a set of three matrices where when we multiply them together, we get X. Um so I'm going to write this as X is equal to U sigma V transpose. So I'm factoring this matrix X into three new matrices that have important properties.

So the U matrix is going to be a square matrix that's n by n and it is orthogonal. And by that, I mean that if I take U transpose U, that's equal to the identity matrix, and that's also equal to U U transpose. So we can think about it as a collection of n different orthonormal basis vectors for the n-dimensional space. Similarly, V is a square matrix. This one is p by p, and it is also orthogonal. So, V transpose V is equal to the identity and here it's equal to VV transpose.

So, this is going to be an orthonormal basis for the space of all p-dimensional vectors. Um and in fact, the V1 that we talked about before is going to be the first column of this matrix. I'm going to talk about that in a little bit more detail in a second. But, the final matrix sigma that goes in the middle here, this matrix is n by p, so the same size as X, and it is diagonal. Um so, what I mean uh uh and uh do do do do.

Okay. Yeah, it's a diagonal matrix. And so, let me just flesh out what that looks like. But, before I do, I just want to specify here that the U columns are called the left singular vectors. The columns of V are called the right singular vectors. And the diagonal entries of sigma are called the singular values. Okay, so just a little bit of vocabulary there. So let's take a look at what how sigma looks. So we're going to have three different cases.

In one case, n is equal to p. So x is a square matrix. So in this case, if we look at our sigma matrix, it's a square and it's got entries sigma one, sigma two, all the way to sigma, let's just say n, it doesn't really matter cuz n is equal to p, and everything every other entry in this matrix is equal to zero. Alternatively, we could have n is greater than p, which means that x is a tall and thin matrix, and so sigma will be too.

So it will look, say, like this. And it will have entries sigma one, sigma two, all the way to sigma p. And then, if we think about this matrix, right? This first block, we've got p rows, and then this bottom part, we're going to have everything else, n minus p rows. And all of those rows are completely equal to zero. So this is what we mean when we talk about a diagonal matrix that could be rectangular. And then, similarly, if n is less than p, then x is a short and fat matrix.

So we would have something like this, and we would have sigma one, sigma two, all the way down to sigma n. And then everything off the diagonals is zero. And these last columns are also equal to zero. So here, I'm going to have n columns. And then here, I'm going to have p minus n additional columns. Okay, so when we talk about a diagonal matrix sigma containing the singular values, this is what we mean. And so in general, the number of singular values is equal to the minimum of n and p.

So far, so good? Okay, so now what I want to do is connect this to everything that we talked about last time and at the beginning of today about finding 1D subspace fits to collections of data. So in particular, the columns of V are going to give um a basis for the span of the x i's. And more specifically, the first r columns of V give a basis for the best r-dimensional subspace fit to the x i's. And so, to be a little bit more precise, if we were to look at this matrix V and look at its first column.

So, we're going to have a couple of different notations here. We've been writing this as the vector V1. Um but in with our book, when we talk about the first column of a matrix, we would write that matrix colon comma one. So, I mean exactly the same thing for these with these two different notations. So, whichever one you're more comfortable with, you're welcome to use. And we already said that this is equal to the best 1D subspace fit.

Once I have that 1D subspace fit, then I can see what is not represented by that subspace within my x i's. So, I can define I'll use a new color for this. x i tilde, my first um for my first round one, as being the vector x i minus everything that's already represented by this 1D subspace. So, I'm going to take this point x i and I am going to project it onto the subspace spanned by V1. So, what I'm looking at here are these residual vectors.

And so, then what we do is we say that the second column of this V matrix, which we might also choose to write as something like V2, this is going to be the best 1D subspace fit to all of these XI tildas. So, we're just taking that basic idea that we learned last time, taking a bunch of points and finding the best D1D best 1D subspace fit, and we're recursing. Find the best 1D subspace fit, calculate the residuals, and then compute the best 1D subspace fit to that, and then we're just going to repeat.

So, in general, I could say that I'm going to define at the kth round the residuals as being the XI minus the projection of XI onto my subspace so far. So, I've got V1, V2, all the way to VK. So, I've got my basis so far with those K different orthonormal basis vectors. I project my sample XI onto that subspace spanned by that basis. I look at the residuals. This gives me my new residuals, and so now my kth column of this V matrix of right singular vectors, or equivalently I could write this as VK, is going to be the best 1D subspace fit to these residuals from the Kth round.

Okay, so we just are repeatedly computing best 1D subspace fits. Yes. >> Uh is that over the X and tilde or a capital X? >> Oh, that's supposed to be a tilde. Yeah, thank you. Any other questions? Yeah. >> Is that a tilde one over there or a tilde I? >> Here? >> In the defined X. >> So, what I'm writing here is I've got a subscript I corresponding to the Ith sample, a tilde to correspond to the fact that it this is a residual, it's not an original point.

I lost who was asking the question. Oh, yeah, there. And then finally, I've got a superscript one in parentheses because I'm only projecting onto the first basis vector. And then when I get over here for instance, I've got a superscript K because I am projecting onto the K dimensional subspace that I've calculated in the previous rounds. Yeah. The notation is uglier than the concept is. Um and maybe what could be helpful is to redraw our figure from last time in 2D, which of course doesn't give us the full kind of scope of the SVD, but remember we had a bunch of points.

And then we looked at a subspace, say like this. And then we said, now let's think about the orthogonal complement to that subspace. So, we need something that's kind of perpendicular to the white line, so that looks like this. And so then for any point here, let's call this XI we can project that onto our white subspace. So in this diagram this white line was V1. And this point here now is the projection of XI onto V1.

And we can also project this XI onto this orthogonal complement here. So this is the projection of XI onto the orthogonal complement to V1. And what we derived last time is that this is the same as the identity matrix minus PV1 times XI which is the same as XI minus P projection onto V1 of XI. So reason I'm redoing all of this is because what I'm saying here is that this point here can be written as this difference here which is what we were calling the residual XI tilde one.

And so what we're doing here is we are saying once I've calculated this V1 subspace then I can project all my points onto the orthogonal complement to get all the aspects of my data that are not represented by that V1 subspace. And once I've done that then I can find a subspace a 1D subspace that spans all of those projected points. Of course in in two dimensions it's kind of trivial there's only one option left, but um hopefully this kind of clarifies why we're doing this sort of recursive operation.

Yes. >> All right, what's the subscript of what's the next >> Um so this is supposed to be I'll just write it big. V1 V2 all the way to VK. So I'm thinking of like the subspace spanned by the K basis vectors that I've calculated in all the previous rounds. Yeah. >> Does K always have to be less than the amount of features that we have? Or is there like a max value for K? When do we stop? >> Where do we stop? Yeah, the biggest that K is going to get is the number of singular values, the maximum of N and P.

So >> minimum or max? >> Sorry, minimum. Min Thank you very much, minimum. Um so K So we go So we're kind of looping this, right? So we do K from one all the way to the minimum of N and P. Uh There's some subtleties here about what you do for the remaining singular vectors that correspond So over here we said, "Oh, you're going to get some singular value matrices and they're going to have big blocks of zeros." So there are singular vectors that correspond to these, but of course they always get multiplied by zeros, so it doesn't really matter what they are.

So I'm not describing how we calculate those singular vectors here. It's just Yeah, not something we're going to talk about in this class. Yes. >> So do we project down to V1 to VK or VK-1? Because are we calculating VK in this step? >> Oh, thank you very much. Um Yeah, so here we did one for the first residual and then we did V2. So, what I really meant here is K + 1 + 1 and therefore K is going to the minimum of P and N - 1.

Thank you very much. This is some like super fancy Japanese chalk that mathematicians love. They call it the Rolls-Royce of chalk and there's a hypothesis that it's so good you cannot make a mistake with it, but we have now disproven that hypothesis. So, well done. >> [laughter] >> Okay, any other questions? Yes. >> So, is it true that that taking the residual vector from one subspace is the same as projecting it onto that subspace's complement?

Or I think it's the exact word. >> So, in general, what we showed last time is that anytime you've got a projection matrix, you can write it as the identity minus a different projection matrix or the identity minus a projection matrix gives you the projection onto the orthogonal complement. Yeah, great. Yes. >> So, the top like K or top like Y is how many times we do this fit? >> That's right. So, if I were to do this for some number R, like let's just say I do this twice, right?

Then I'm going to get So, I get the first two columns of V, then that gives me the best 2D subspace fit to my data. Um there is a picture in the lecture notes that'll be posted online that I generated with a computer script that's going to show a bunch of points in 3D and the best 2D subspace fit to it. Very hard for me to draw on the board, but the picture in the slides I think will look much nicer and maybe convey that point better.

Yeah. Any other questions? Yeah. >> Shouldn't the um like superscript on that be two for the for the V2 >> So, I've got V2 superscript two or subscript here. >> X. >> So, I'm I'm just saying like when my superscript is one, I'm subtracting off the first um basis. >> one >> Yeah. I I'm worried that, you know, like the notation is a little complex here and this is not I'm really kind of emphasizing this not because this is what you would do algorithmically.

You're not going to implement this. Um there are, like I said before, very sophisticated computational routines for computing the SVD. What I'm really trying to convey here is how to interpret what the SVD is giving you, which is um you are successively like computing the best 1D subspace fit to a bunch of data, then computing the residuals, and then computing the best 1D subspace fit to those residuals. And because we do it in this sort of recursive way, and I'm um this means that for any R less than the minimum of N and P, if I just take the first R columns, I am going to get the best R dimensional subspace.

So, I can immediately get the best 1D subspace or the best 2D subspace or the best 3D subspace just by taking the right number of the first set of columns of V. Yeah. Yes. >> Is the Can we interpret this like a partial decomposition of the matrix? >> Yes. That is exactly right. And what you described is um the way that you hear principal components analysis most frequently described. And so, we're going to talk about that in a little bit more detail, but if you don't mind, I'd just like to table that discussion for a little bit later.

Um what I want to do first of all is just do a quick um contrast to Gram-Schmidt. So, specifically, recall that our first Gram-Schmidt basis vector amounted to taking our first sample and dividing by its norm. And then, we would compute a residual vector X2 tilde by just taking X2 and subtracting off the projection of X2 onto U1. And then, we would have our second basis vector U2 corresponding to X 2 tilde, this residual normalized.

Et cetera. So, a key fact here is that if I were to shuffle my points, the order of my points, then I would get completely different basis vectors here. Whereas with the SVD, we are looking at all the samples all the time. Right? So, I am finding the best 1D subspace fit to all n of my samples here. And then, for my second basis vector, I'm computing the best 1D subspace fit to all of my residuals. So, maybe I should even just be explicit, this is for all I.

So, I'm always looking at all of my samples. So, if I change the order of my samples, that doesn't really change what 1D subspace best fits them. Okay. Uh ch- Couple of other key points. Um So, we can look at the number of sigma i's, the r j's, I guess, the number of singular values that are strictly greater than zero, not equal to zero. And that is going to be equal to the rank of the matrix X. So, if you compute the SVD of a matrix, you can just by inspection look at this sigma matrix and tell what the rank is.

So, what you would see if you had a rank one matrix is that you'd have some sigma one here, and all the rest of these diagonal entries would be equal to zero. In addition, the sigma i's or j's, I guess, I've gone with. Um indicate the spread or variation, or maybe I should say variance, of the um x i's in the v >> [sighs and snorts] >> j direction. So, if I were to go back to our little picture here, what you would find is that the first best 1D subspace fit is going to be going in the direction where the x's are varying the most, exactly like your question.

Um and the bigger sigma one is, the more variation we have. And then our second basis our second singular value is going to tell us for our second basis vector how much variation there is in that direction. And so, we've already peeled off the direction of most variation with v1, so v2 is going to tell us the direction where there's the second most variation, and sigma two is going to tell us how big that is. So, for instance, if sigma one is really big compared to sigma two, then we can infer that the data is varying a lot more in this first direction than it is in the second direction.

So, when we look at the singular values, we get an immediate geometric interpretation of how the data is structured. More generally, people will often look at things like what they'll call the singular value spectrum of a matrix X. And this will look like a plot where the horizontal axis would be an index j for the different singular values, and so this would go up to the minimum uh p and n. And then the vertical axis would be sigma j.

And so, if you were to make a plot like this of how the singular values change as you go further and further along in the diagonal matrix, you could see a variety of different things, right? You could see something that looks like you've got some high values, and and it drops off really quickly, and then everything else is really small or even zero. So, if you see this, then this indicates so, let's just say this location here is R, then this is telling us that X is almost rank R.

Because the top R singular values are big, and the rest are really close to zero. So, even though the rank of this matrix is not exactly R, because I've got a bunch of singular values that are non-zero, it's telling me that with a small little change in the matrix, I would have a rank R matrix. Yeah. Right. So, what I'm plotting in this plot is if I come over here, and I look at this matrix, I am just taking all of these diagonal entries, and I'm making a plot of them.

They can be zero. So, So, everything like in in this example here, everything below the first P rows has to be zero. And then, if I look at the diagonal entries in the top square block, then some of these might be zero if I don't have a full rank matrix. Yeah. Yes. >> I thought you mentioned that we're using some algorithm to find like V1, but how do we use some algorithm to find V2, V3, and eventually the U sigma V? >> Okay.

So, we have written an expression for what V1 is. We framed it as the solution to an optimization problem, right? I need to solve this maximization problem to get V1. What we are not going to talk about in this class is how to solve this optimization problem. We are going to assume we've got nice linear algebra solver packages that we can use to solve that optimization problem. So, I'm describing what the solution corresponds to, but not how you would actually compute it.

Um and then and more generally, like I think this is intimately related to how SVD packages work. The way I'm describing it here is this sort of kind of iterative building up. Um that's not necessarily how the full SVD is implemented. This is more to give you a conceptual understanding. >> So, like theoretically, we can use just that algorithm to compute like U, sigma, and V. >> Yeah. So, in NumPy well, now I'm going to embarrass myself cuz I don't remember exactly the syntax, but there is just a NumPy SVD package.

You feed in the matrix X, and it outputs a U matrix, a sigma matrix, and a V matrix. And so, that's for this class all you would ever need to do. Um there is a variation on that that's super important to know that's related to the truncated SVD, and we're going to get to that very soon. Yes. Okay, so um the way I wrote it on the board is right, but let me elaborate a little bit. Um so, let's think about this in terms of bases.

So, again, we are writing U is I am sorry, X is U sigma V transpose. And so, what is true is that the first R columns of U are a basis for the best R dimensional subspace fit to the columns of X. Okay? And we can kind of read this off from this expression because I'm writing each column of X as a weighted sum of the columns of U where sigma V transpose is telling me the weight for each column. Um, simultaneously, the first R columns of V are a basis for the best R dimensional subspace fit to the rows of X.

And in our example that we were starting off with, the rows of X like I put on the first board are just the X i's. And so that, yeah. Um, so we can actually see this because if we were to look at X transpose, then, well, first of all, now with X transpose, my columns are my feature vectors. These X eyes for I equals 1 10. Right? So, these are all column vectors. And I can now take the SVD and compute the transpose of that.

So, remember that to compute the transpose of a product of matrices, then we reverse the order and take the transpose of each one. So, I'm going to get V transpose transpose sigma transpose U transpose. Transpose of a transpose is just the matrix. Okay. So, now we can say that X transpose is equal to V sigma U transpose. So, we can take the SVD of X transpose and it's got the same factors or the same components as the SVD of X.

They're just in a different order now. And we can also see now that the columns of X transpose, which are the rows of X, are all being written as weighted sums of the columns of V. And so, from this we can infer that we've got a basis for um the columns of X transpose. Yeah. A little bit more specifically as we think about these basis expansions, what we're saying here is that we can write any one of our points X I as a weighted sum, so sum from J equals 1 to P of um VJ, my Jth basis vector, times a weight.

So, each XI, each column of X transpose, is a weighted sum of the columns of V, and these are giving us the weights. And specifically, the weights are going to be sigma J times UIJ. Any questions about this so far? All the questions so far have been really great. Okay. Um so, coming back here, when we first started, I think on like lecture two, we were talking about writing a matrix X as a sum of rank one matrices. And there was this question of, well, where do those rank one matrices come from?

How does this relate to the rank of the full matrix? And now we can be really precise about this. What we're going to do is we are going to write X as being a sum of rank one matrices, where we're going to have sigma one times the first column of U times the first column of V transposed. Plus, and we go all the way through to sigma, and then we've got the minimum of N I'm going to avoid the sunshine here. Plus sigma, and we've got the minimum of n and p of u and we've got this minimum of n and p here.

And v minimum of n and p transposed. So now we have written our matrix x as a sum of rank one matrices. So each rank one matrix is just an outer product of two vectors. And if we look and as I said before um if our matrix is lower rank, if the rank is even smaller than the minimum of n and p then we are going to have some of these sigmas equal to zero. So the number of terms in this sum with sigmas not equal to zero is the rank of the matrix.

Okay, that's nothing new than what I told you before about the rank. But now as we look at this from the perspective of writing x as a sum of rank one matrices, the number of terms we need in that sum in terms of the singular vectors is the rank. Okay, so now we're going to get uh to a key point that's going to be related to some of the stuff we did with least squares. So if x is square um and it um and uh there's some sigma j so uh where there's some sigma j equals to zero for some j that's less than the minimum of n and p.

All right, well I guess it's square, so it's just less than n. Then x is not invertible. Or in other words, we say x is singular. Okay, so if we have this set of this singular value matrix here with singular values sigma one all the way to sigma n. And if some if any of these diagonal entries are equal to zero then that immediately tells us that the rank of this matrix x is less than n and we cannot invert the matrix.

If x is not singular so we can compute an inverse then we can also write the inverse in terms of the singular value decomposition. So we can write x inverse as simply being v * sigma inverse * u transpose. So this is nice because if you know the singular value decomposition of your matrix then do you want to compute the inverse of that matrix? It's very trivial. You keep the same singular vectors. You just have to change the singular values.

Yes. >> Oh, we're reversing like U and V like V abs reversed. >> That's exactly right. Mhm. Okay. Okay. So, the next thing I want to talk about is something that I mentioned earlier, which is the truncated singular value decomposition. And this is something that I've been hinting at a little bit all along, so nothing should be too surprising. There we go. So, we're going to start with a matrix X, as usual, that's n by p.

And we're going to have some number k that's going to be less than the minimum of n and p. So, for this, the truncated SVD corresponds to We're going to write it as um U K sigma K V K transpose. And what this What I mean by this is the following. So, we are going to have our original matrix. So, let's see. I want to have my original X here. And then, let's imagine I do the full SVD. So, my U matrix is square. So, this is n by p.

This is n by n. Then, I've got my sigma matrix, which is going to also be n by p. And then, I'm going to have my V transpose matrix like this. And now, what I'm going to do to do the truncated SVD is I'm going to keep only components of this. So, UK is going to correspond to the first um is going to be an n by k matrix corresponding to the first k columns of U. Sigma K is going to be this diagonal matrix. It's k by k.

It corresponds to the first k by k diagonal block of my original sigma. And then, finally, I'm going to have VK transpose here. And this is k by p. So, what I'm doing with the truncated SVD is I am getting rid of everything except to the first k basis vectors in U, the first k basis vectors in V, and the first k singular values. Okay. Are there any questions so far? Yes. >> Um is this different than the structure of sigma that like we talked about before on the is uh top right board where there's in that sigma matrix a block of zeros at the bottom. >> Great question.

So, let me actually just redraw this a little bit. So, in this diagram, I'm going to have sigma one all the way to sigma K, and then I've got sigma K plus one all the way here to sigma P, and then below here I've got N minus P rows that are all zero valued, and everything away from the diagonal is zero valued. So, that was our original sigma matrix. And now what we're doing here with the truncated SVD is we're only keeping the top K by K block.

So, there's a key distinction here, right? With the original SVD, our U and V matrices were square, and sigma was potentially rectangular if X was rectangular. When we do the truncated SVD, we are going to have our sigma K matrix always be a square, and the U and V matrices are now going to be rectangular. And K is sort of the common uh dimension among them. And so, just to be super clear, UK equals the first K columns of U, VK equals the first K columns of V, and sigma K equals the first K by K diagonal Oops.

Diagonal block of sigma. Okay, so there's a specific order here. I'm not just choosing arbitrary columns of U or arbitrary columns of V. I'm choosing the first ones. So, we can think about now how to interpret this and what's going on here. So, let me say, first of all, what happens if our matrix X has low rank? So, if the rank of X is equal to R and R is less than the minimum of N and P. Then, what I can do is I can compute the truncated SVD of X.

So, I'm just going to write this as truncated SVD of X and that is U R sigma uh R V R transpose. So, if I have a rank R matrix and then truncate the SVD to have only R components, then this product corresponding to the truncated SVD is going to exactly equal X. The reason for that is because when I've got a rank R matrix X and I look at the corresponding sigma, let's just imagine our matrix is tall and skinny, so I've got sigma 1 through sigma R and then all of the other singular values have to be equal to zero, right?

Because we said the rank of the matrix is the number of singular values that's greater than zero. So, in this singular value matrix, the only things that are nonzero are these first r diagonal elements. So, if I now clip this, right? If I just keep the top r by r block, and this is sigma r, then I haven't lost any information. I haven't deleted anything, right? The only thing I've cut off are a bunch of zeros, which weren't contributing to this product anyway.

And so, when I do the truncated SVD, and I truncate to r basis vectors and r singular values, then I have exactly the same represent that this product gives me exactly my original matrix X. But, if we truncate to k singular values, where k is less than the rank of X, then we would have a truncated singular value decomposition U k sigma k V k transpose, and I'm going to call this product X k, and this is going to not be equal to X.

It's just going Yeah, it's not going to be equal to X. It's going to be something a little bit different. So, we're going to talk about how different it is in just a minute. But I want to be a little bit clear about vocabulary. So if I am truncating the SVD, but the stuff I'm clipping off are only zero valued singular values, so this is exactly equal. Then sometimes people will call this the economy or compact SVD. Because I haven't really lost any information, I'm still exactly representing my rank R matrix.

It's just that I am not wasting storage space. Right? Like if my matrix X is rank one, then I could write X as the outer product of two vectors, right? So in order if if I take So here, let me >> [snorts] >> So for example, if X is rank one, I can write X as being equal to sigma one times this U1 um first column of U times the first column of V transpose. And if I were to kind of expand this sum of for all the singular values and singular vectors, all the other terms in that sum would be equal to zeros because all of the other singular values are equal to zero.

So I only need one rank one matrix to represent my rank one matrix. And so if I want to have an efficient way to store this matrix X that's only rank one, then I really only care about the first singular vectors and the first singular value. So, computing a full SVD, having a full U that's n by n and a full V that's p by p, only to multiply those extra basis vectors by zero singu- these zero-valued singular values, it's wasteful.

It's taking a lot of extra storage space. And so, the economy SVD is saying, "Well, in this example, when I've got a rank one matrix, I really only need to keep track of the first singular vectors and the first singular value cuz everything else is irrelevant to the content of X." So, it's a economy way of representing X. But, if we have a matrix that's not um where where we truncate some of the singular values that are not equal to zero, then all of a sudden we're getting an approximation to the original matrix.

We've cut off some actual information about the content of X. So, let me try to represent this graphically in a way that I hope will help a little bit. Okay, so I've got my full matrix U, and I've got um Let's see how they do it there. Yeah. Which is a rectangle. And so, I've got my full square U. And then, I've got my sigma. And then, I've got my V transpose. And in this example, let's imagine that my singular vec- uh values, I've got a sigma one and a sigma two and a zero.

And everything else down here is zero. Okay, so this is my full singular value decomposition. Next, I can look at the economy singular value decomposition. So, I've got the exact same matrix X here. And now, I am noting that in this singular value matrix, only two of the singular values are nonzero. And so, I can just keep just a two column matrix U um and then, I can just keep the first two entries uh or the first two by two block with singular values sigma one and sigma two.

And then, I can keep just the first two columns of V. So, I've only got two rows in V transpose. So, this is sigma two and this is V2 transpose. So, this is the economy SVD. So, I've cut out parts of U that are just getting multiplied by zeros. And I've cut out parts of V that are just getting multiplied by zeros. So, I haven't changed the product. It's still exactly equal to X, but now I'm storing much smaller matrices.

And then finally, we have the truncated SVD, um where I'm going to have K is equal to one here. And with the economy SVD, the rank was equal to two. And so, here now I'm going to have a U1 that's just going to be a single column vector. And then I'm going to have my sigma one. Now, I've only got one entry left. It's just sigma one. And then I'm going to have a V vector. So, this is V1 transpose. So, now I have actually deleted by this truncation process this second singular value.

And so, the product is now something different than my original X. So, it's going to be still the same size, but this X2 matrix is not exactly my original X. It is something different. Okay. So, that's one illustration through pictures of matrices. We can also think about this in terms of actual points. Okay. So, let's take our points just like we had before. And let's have them be varying more in one diagonal direction than the other, like we've been considering.

And we have our first singular vector. Here's V1. And then we had its orthogonal complement in 2D. This was V2. So, here the full SVD is going to tell us uh is going to have both V1 and V2 in the basis. Um and so we're going to get X is equal to U sigma V transpose. If I were to give a truncated truncated SVD where K is equal to one, we are going to get U1 sigma one V1 transpose. So, what does that mean in terms of our points?

In terms of this scatter plot? What it means is that we are only keeping uh we're only representing these points in terms of the first basis vector. So, we are keeping track for each point of where they are in this V1 direction. And we are getting rid of any information about where they are off the V1 space. And so, instead of represent So, if we look at this product U1 sigma one V1 transpose, where we've been calling this X1, which is not equal to X.

So, now if we think about the rows of X1, those correspond now to these points that all lie in the V1 subspace. So, we've only kept their projections onto that subspace and we've lost any information about where they are off that subspace. Now, in contrast or maybe not in contrast, but maybe to flush this out a little bit. Imagine that we looked at our data and it happened that all of our samples were perfectly lined up.

Now, this never happens in real machine learning context. This is just a imaginary experiment, but now we've got our best one-D subspace fit and it fits our samples exactly. So, again, we could compute the full SVD and that's equal to U sigma V transpose. But now, if we were to truncate uh well, if we were to yeah, truncate the SVD and look at U1 sigma 1 V1 transpose, just like before, we're taking each of these points and projecting them onto the V1 subspace.

But, since they already lie on that subspace, the projection isn't changing those points at all. So, we're not losing any information with that truncation. And so, since the points aren't moving at all, this is just exactly equal to X. And so, this is now I'm going to call it the economy SVD. And I'm using a different name to convey the fact that we are using smaller matrices in the SVD, but we haven't lost any information.

We're not cutting off information. We're just m- having a more efficient uh or smaller set of matrices to represent X. Yeah. >> Just taking a look at the top there, shouldn't it be X1 isn't equal to X? >> Oh, thank you very much. Yeah, key point. Yes. Yes, X1 is not equal to X in general, especially in this illustration where the points aren't exactly on the V1 subspace. In this example below where the points are on the V1 subspace, then we do have equality.

Yeah, thank you very much. Yes. >> Uh in the in the second case, what would our what would our one's uh sigma one value be cuz there's no variance? >> Um in this case there is variation in the V1 direction, so sigma one is not zero, but you're exactly right. There's no variation in any other direction. So, this means that sigma two is going to have to be equal to zero. And like we said so, sigma one here is greater than zero, but sigma two is equal to zero.

And what we said before is that the rank of the matrix X is equal to the number of singular values that are greater than zero. So, when we look at these singular values, this is telling us that the matrix X is rank one. Which is telling us that all of the points lie in a 1D subspace. So, just by looking at the singular values, we can immediately say something about the geometry of the points of the the rows of X. Um and I think you're getting at sort of the reverse of that, which is um if I know that my points in X lie in a low-dimensional subspace, then I immediately know something about what the singular values are going to be and how many are going to be equal to zero or or greater than zero.

Yeah. Yes. >> Just to clarify, V1 is the best like subspace 1D subspace fit to all the X's or just X1? >> V So, we talked before about little the vector little V1. And um this is the best 1D subspace fit to all n of our samples. In terms of the SVD, this is like taking my V matrix of right singular vectors and keeping just its first column. And then when we talk about the truncated SVD, I am saying V1 corresponds to just keeping the first column of the matrix V and so then we use this notation V1.

It's a little messed up. I'm sorry that there's different ways of representing this, but all of these mean the same thing in this case. But I just want to be careful that the vector V2 that gives me the best 1D subspace fit to all of the residuals, this is going to be the second column of our right singular vector matrix. But when I talk about the V2 matrix in the truncated SVD, I mean the first two columns of V. So this is going to be a matrix whose first column is V colon 1 and second column is V colon 2.

I know that's not pretty notation. I apologize, but it's I'm trying to stay as aligned as I can with the notation in the book that's I think aligned with a lot of what you would see in NumPy um as well as trying to make this as intuitive as I can. Any other questions? Okay. Another thing that I want to emphasize here, and this is really important, um with the full SVD, we had that UU transpose U is equal to the identity is equal to UU transpose.

Um so by definition, U is an orthogonal square matrix. As soon as we have a truncated and and and similarly for V, as soon as we have a truncated SVD, we're going to have a matrix UK. So, all of the columns of UK are orthogonal to one another because all of the columns of U were orthogonal to one another. And we're just choosing a subset of the columns. So, we still have UK transpose UK is equal to the identity matrix.

But, UK UK transpose is not the identity matrix. It's an easy mistake to make, but these are rectangular matrices now, and once we compute these inner products, we no longer have an identity matrix after we've done this truncation. Okay. This will come up a little bit later when we do various machine learning tasks, but I just wanted to highlight it now. Also, there are special numerical routines for computing the truncated SVD.

If you've got a giant matrix, let's say a million by a million entries, and all you want is the truncated best rank one approximation, it doesn't make sense to compute a million by a million singular vectors, right? Or a million singular vectors on the left and a million singular vectors on the right when you only really care about say the first one. So, there are in NumPy and R and MATLAB, whatever, special methods for only computing truncated SVDs when K is small.

So, that can be helpful to know when you start implementing things. Okay. So, the final thing we're going to do today is talk about the subspace approximation theorem. So, we're going to have a matrix X that has n rows and p columns. And if it has rank r and that rank r is bigger than some number k. And we're going to do some truncation to the top k singular values and singular vectors. Then, what we could do is we could say what happens if I try to find an approximation Z to X.

So, I want to find a matrix Z that's close to X and I'm going to measure closeness using my Frobenius norm. So, the sum of the squared differences between these two matrices. And I want to search I want to minimize this difference and I'm going to search over matrices Z that are the same size as X, so they're N by P, but I'm only going to allow myself to have the rank of Z be equal to K. So, I want to find a rank K matrix that's as close as possible to X.

It turns out that the answer to this optimization problem is simply equal to UK sigma K VK transpose. So, not only is the truncated SVD kind of cutting off columns of U and sigma and V, but it also is giving us a new matrix. We've been calling this XK that's the matrix that's close as possible to X while being a rank K matrix. In addition, we can say, well, how much did we lose by doing this approximation? So, we can say, how big is the difference between X and XK?

What's the difference between What's the squared errors between them? And this is going to be equal to the sum from J equals um K plus one to R of sigma J squared. So, in our truncated SVD, effectively, what we're doing is we're taking all of the singular values above the past the Kth one and we're setting them equal to zero. So, if we look at how big those singular values are that we cut off, that's telling us how much error that we incurred.

So, remember that last time we had a little example um that I'm not going to be able to remember exactly, but X was something like 1 2 3, and then we had like 3.1 5.9 and 6.2. So, the rank of this matrix is equal to 2. And then we could consider a rank one approximation. And here I'm going to write 1 2 3 3 6 9. This matrix has rank equal to 1. And so, they're close to one another. One is rank one, one is rank two. Now, this is not what I'm getting by doing the SVD exactly.

I haven't worked out the numbers for this example, but it's an illustration of how we can get an approximate matrix that's rank one and close as close to our original matrix. Now, you might ask, "Well, is there a better rank one matrix that's even closer to my original X?" And the answer is possibly, and if you want to find it, then what you would do is you would take the SVD of X. You would truncate everything except the first singular vectors and this first singular value.

And then you would compute the product of those truncated matrices, and that will give you the very best possible rank one matrix fit to your data. Okay. So, um let me talk about one final sort of I think interesting application of this. So, we've talked before about a matrix representing Netflix's um movie ratings for all the movies and all of their customers. Right? So, let's just think about how big that matrix is.

So, So, we've got um N being, let's say, 5,000 movies, for example, and P being 100 million customers. Okay, so if I wanted to just store all of these raw ratings, the storage would be equal to the number of entries, which is 5,000 * 100 million * let's just say 4 bytes that we use to represent each rating. And this is about equal to 2 terabytes to represent this matrix. But then, let's say let's find the rank K approximation to this original matrix.

So, we want to find something that is close to the original ratings, but where K = 10 is the rank. So, let's just say that we can find that rank K matrix using our SVD, and that it's it's accurate. That that approximation isn't losing critical information about the customers' ratings. So then, how much storage do we need for UK? We're going to have 5,000 * 10 * 4 bytes. And VK is going to be 100 million * 10 * 4 bytes.

And then the actual singular values sigma K is going to be 10 * 4 bytes. And if we put [clears throat] it all together, then the total storage is going to be much smaller. So we've really reduced the amount of storage required for this matrix by doing this rank K approximation, which we can compute very easily using the truncated SVD. Okay, thank you very much. Next week we'll talk about more machine learning applications of the SVD.