Transcript

Okay, this is the lecture on the singular value decomposition. But everybody calls it the SVD. So this is the final and best factorization of a matrix. Uh let me tell you what's coming. The factors will be a orthogonal matrix, diagonal matrix, orthogonal matrix. So it's things that we've seen for these special good matrices, orthogonal diagonal. The The new point is that we need two orthogonal matrices. A can be any matrix whatsoever. Any matrix whatsoever has this singular value decomposition. So a diagonal one in the middle, but I need two different, probably different, orthogonal matrices to to be able to do this.

Okay, and this factorization has jumped into importance and is properly, I think, maybe the bringing together of everything in this course. One thing we'll bring together is the the the good the very good family of matrices that we just studied, symmetric positive definite. Do you remember the story with those guys? Because they were symmetric, their eigenvectors were orthogonal. So I could produce an orthogonal matrix. This is my usual one. My usual one is the eigenvectors and eigenvalues. In the symmetric case, the eigenvectors are orthogonal. So I've got the good my my ordinary S has become a especially good Q.

And positive definite, my ordinary lambda has become a positive lambda. So this is that's the that's the singular value decomposition in case our matrix is symmetric positive definite. In that case, I don't need two U and a V. One matrix one orthogonal matrix will do for both sides. But it's So this would be no good in in general because usually the eigenvector matrix isn't orthogonal. So this is not what I'm That's not what I'm after. I'm looking for orthogonal times diagonal times orthogonal. And let me show you what that means and where it comes from. Okay. What does it mean? You remember the the picture of any linear transformation.

This was like the most important figure in 1806. And what am I looking for now? A typical vector in the row space typical vector, let me call it V1 gets taken over to some vector in the column space, say U1. So U1 is AV1. Okay. Now another vector gets taken over here somewhere. What am I looking for in this SVD, this singular value decomposition? What I'm looking for is an orthogonal basis here that gets knocked over into an orthogonal basis over there. That See that's pretty special to to have to have an orthogonal basis in the row space that goes over into an orthogonal basis. So this is like a right angle and this is a right angle into an orthogonal basis in the column space.

So that's our that's our goal. is to find Do you see how things are coming together? First of all, can I find an orthogonal basis for this row space? Of course. No No big deal to find an orthogonal basis. Gram-Schmidt tells me how to do it. Start with any old basis and use grind through Gram-Schmidt, out comes orthogonal basis. But then, if I just take any old orthogonal basis, then when I multiply by A, there's no reason why it should be orthogonal over here. So I'm looking for this special setup where A takes these basis vectors into orthogonal vectors over there. Now, you might have noticed that the null space, I didn't include.

Why don't I stick that stick that in? You remember our usual figure had a little null space and a little null space. And those are no problems. Those are null spaces are going to show up as zeros on the diagonal of sigma. So that's not what we're That That doesn't present any difficulty. Our difficulty is to find the So do you see what this will mean? This will mean that A times this these Vs, V1, V2 up to What's the dimension of this row space, VR? Sorry. That V a little smaller. Up to VR. So that's AV1 is going to be the first column. So let me Here's what I'm Here's what I'm achieving. Oh, I would like I'm not only have going to make these orthogonal, but why not make them orthonormal?

Make them unit vectors. So this Maybe the unit vector is here is the U1. And this might be a multiple of it. So really what's happening is AV1 is some multiple of U1, right? I'm going to I'm These guys will be unit vectors and they'll go over into multiples of unit vectors. And the multiple, I'm not going to call lambda anymore. I'm calling it sigma. So that's the number the the stretching number. And similarly, AV2 is sigma 2 U2. This is what This is my goal. And now I want to express that goal in matrix language. That's the the usual step. Think of what you want and then express it as a matrix multiplication.

So AV1 is sigma 1 U1. Actually, here we Here we go. Let me pull out these U1, U2 to UR and then a matrix with the sigmas. It's Everything now is going to be in this in that in that uh little part of the blackboard. Do you see that this equation says what I'm trying to do with my figure. A times the first basis vector should be sigma 1 times the times the other basis the other first basis vector. These are the basis vectors in the row space. These are the basis vectors in the column space and these are the multiplying factors. So AV2 is sigma 2 times U2. AVR is sigma R times UR. And then we've got a whole lot of zeros and maybe some zeros at the end.

But this is That's the heart of it. Now if I express that in as matrices, cuz you knew that was coming, that's what I have. So this is my goal. To find an orthogonal basis in the row space, orthonormal even, basis in the row space and an orthonormal basis in the column space so that I'm sort of diagonalized the matrix. The matrix A is like getting converted to this diagonal matrix sigma. And you notice that usually I have to do I have to allow myself two different bases. The my my little comment about symmetric positive definite was the one case where it's AQ = Q sigma, where V and U are the same Q.

But mostly, you know, I'm going to take a matrix like Let me take a matrix like 4 4 -3 3. Okay. There's a 2 by 2 matrix. It's invertible, so uh uh it has rank two. So I'm going to look for two vectors V1 and V2 in the in the row space and you So I'm going to look for V1, V2 in the row space, which of course is R2. And I'm going to look for U1, U2 in the column space, which of course is also R2. And I'm going to look for numbers sigma 1 and sigma 2 so that it all comes out right. So these guys are ortho orthonormal. These guys are orthonormal and these are the scaling factors. So I'll do that example as soon as I get the matrix picture straight.

Okay. Do you see that this expresses what I want? Can I just say two words about null spaces? If we have if there's some null space, then we've got we want to stick in a basis for those for that. So here comes a basis for the null space V R + 1 down to VN. So if if we only had an R dimensional row space and the other N - R dimensions were in the null space, okay, we'll take an orthogonal orthonormal basis there, no problem. And then we'll just get zeros. So actually those zeros will come out from the from the on the diagonal matrix. So I'll I'll complete that to uh to um orthonormal basis for the whole space RM.

I complete this to an orthonormal basis for the whole space RN and I complete that with zeros. Uh null spaces are no problem here. So really the true the true problem is in a matrix like that, which isn't symmetric, so I can't use its eigenvectors, they're not orthogonal. But somehow I have to get these orthogonal, in fact orthonormal, guys that make it work. I I have to find this these orthonormal guys, these orthonormal guys, and I want AV1 to be sigma 1 U1 and AV2 to be sigma 2 U2. Okay. That's my goal. Here's Here's the uh matrices that are going to get me there. Now these are orthogonal matrices.

I can put that if I multiply on both both sides by V inverse, I have A equals U sigma V inverse, and of course you know the other way I can write V inverse. This is one of those square orthogonal matrices, so it's the same as U sigma V transpose. Okay. Here's my problem. I've got two orthogonal matrices here. And I don't want to find them both at once. So I want to cook up some expression that will make the U's disappear. I would like to make the U's disappear and leave me only with the V's. And here's how to do it. It's it's the same combination that keeps showing up whenever we have a general rectangular matrix, then it's A transpose A, that's the great matrix.

That's the great matrix. That's the matrix that's symmetric. And in fact positive definite or at least positive semi-definite. This is the matrix with nice properties. So let's see what will it be? So if I took the transpose then, I would have A transpose A will be what? What do I have? If I transpose that, I have V sigma transpose U transpose. That's that's the A transpose. Now the A. And what have I got? Looks like worse because it's got six things now together, but it's going to collapse into something good. What does U transpose U collapse into? I, the identity. So that's the key point. This is the identity and we don't have U anymore.

And sigma transpose times sigma, those are diagonal matrices. So their product is just going to have sigma squareds on the diagonal. So do you see what we've got here? This is V times this easy matrix sigma 1 squared, sigma 2 squared times V transpose. This is this is the A transpose A. This is Let me copy down A transpose A is that. U's are out of the picture now. I'm only having to choose the V's. And what are these V's? And what are these sigmas? Do you know what the V's are? They're the eigenvectors. See this is a perfect eigenvector eigenvalue Q lambda Q transpose for the matrix A transpose A.

A itself is like nothing special. But A transpose A will be special. It'll be symmetric positive definite. So this will be its eigenvectors and this will be its eigenvalues. And the eigenvalues will be positive because this thing's positive definite. Can I just now So so this is my method. This tells me what the V's are. And how am I going to find the U's? Well, one way would be to look at A A transpose. Put multiply A by A transpose in the opposite order. That will stick the V's in the middle, knock them out, and leave me with the U's. So here's the overall picture then. The V's are the eigenvectors of A transpose A.

The U's are the eigenvectors of A A transpose, which are different. And the sigmas are the square roots of these. And the positive square roots, so we have positive sigmas. Let me do that for that example. This is this is really what you should know and be able to do for um the the SVD. Okay. Let me take that matrix. So what's my first step? Compute A transpose A. Because I want its eigenvectors. Okay, so I have to compute A transpose A. So A transpose is 4 4 -3 3. And A is 4 4 -3 3. And I do that multiplication and I get 16, I get 25, I get 16 -9. Is that 7? And it better come out symmetric. And oh, okay, and then it comes out 25.

Okay. So I want its eigenvectors and its eigenvalues. Its eigenvalues will be the V's. Its eigenvalues will be the squares of the sigmas. Okay. What are the eigenvalues and eigenvectors of this guy? Have you you have you seen that 2 by 2 example enough to recognize that the eigenvectors are that 1 1 is an eigenvector? So this is Here is A transpose A. I'm looking for its eigenvectors. So its eigenvectors I think are 1 1 and 1 -1. Because if I multiply that matrix by 1 1, what do I get? If I multiply that matrix by 1 1, I get 32 32. So which is 32 of 1 1. So there's the first eigenvector. And there's the eigenvalue for A transpose A.

So I'm going to take its square root in the um in the uh for sigma. Okay, what's the eigenvector that goes eigenvalue that goes with this one? If I do that multiplication, what do I get? I get some multiple of 1 -1. And what is that multiple? Looks like 18. Okay. So those are the two eigenvectors. But oh, just a moment, I didn't normalize them. To to make everything absolutely right, I ought to normalize these eigenvectors, divide by their length square root of two. So all these guys should be true unit vectors. And of course that normalization didn't change the 32 and the 18. Okay. So I'm happy with the V's.

Here are the V's. So, now let me put together the the the pieces here. Here's my A. Here's my A. Let me Let me write down A again. This should, if if life is right, we should get U, which I don't yet know. U I don't yet know. Sigma I do now know. What's Sigma? So, I'm looking for U Sigma V transpose. U the diagonal guy and V transpose. Okay. Let's just see that come out right. So, what's What are the What are the Sigmas? They're the square roots of these things. So, square root of 32 and square root of 18. 0 0. Okay. What are the V's? They're these two. And I have to transpose. Maybe that Maybe that just leaves me with ones with 1 over square root of 2 in that row.

And the other one is 1 over square root of 2 minus 1 over square root of 2. Now, finally, I've got to know the U's. Well, actually, one way to do, since I now know all the other pieces, I could put those together and figure out what the U's are. But, let me do it the AA transpose way. Okay, find the U's now. U1 and U2. And what are they? I look at AA transpose. So, A is supposed to be U Sigma V transpose. And then, when I transpose that, I get V Sigma transpose U transpose. So, I'm just doing it in the opposite order. A * A transpose. And what's the good part here? That in the middle, V transpose V is going to be the identity.

So, this is just U Sigma Sigma transpose. That's some diagonal matrix with Sigma squareds. And U transpose. So, what am I seeing here? I'm seeing here again a symmetric positive definite, or at least semi-definite, matrix. And I'm seeing its eigen vectors and its eigen values. So, if I compute AA transpose, its eigen vectors will be the things that go into U. Okay. So, I need to compute AA transpose. I guess I'm going to have to go Let me Can I Can I move that up just a little? Maybe a little more. And do AA transpose. So, what's A? 4 4 minus 3 and 3. And what's A transpose? 4 4 minus 3 and 3.

And when I do that multiplication, uh I get What do I get? 16 and 16, 32. Uh that one comes out zero. Oh, so this is a lucky case. And that one comes out 18. So, this is a like an accident that AA transpose happens to come out diagonal. So, we know easily its eigen vectors and eigen values. So, its eigen vectors are What's the first eigen vector for this AA transpose matrix? It's just 1 0. And when I do that multiplication, I get 32 * 1 0. And the other eigen vector is just 0 1. And when I multiply by that, I get 18. So, this is A A transpose. Multiplying that gives me the 32. AA transpose multiplying this guy gives me 18.

First of all, I got 32 and 18 again. Am I surprised? Yeah, it's clearly not an accident. The eigen values of AA transpose were exactly the same as the eigen values of This one was A transpose A. That's no surprise at all. The eigen values of AB are same as the eigen values of BA. The The order if I That's a very nice fact that eigen values just stay the same if I switch the order of multiplication. So, no surprise to see 32 and 18. What What I learned First, that checked that things were numerically correct. But, now I've learned these eigen vectors. And actually, they're about as nice as can be.

They're the best orthogonal matrix, just the identity. Okay. So, my claim is that it ought to all fit together. That this numer- This These numbers should come out right. The numbers should come out right because the the uh matrix multiplications use the properties that we want. Okay. So, we just check that. Here is the identity, so not doing anything. Square root of 32 is multiplying that row. So, that square root of 32 divided by square root of 2 means square root of 16, four. Correct? And square root of 18 is divided by square root of 2, so that leaves me square root of 9, which is three. But, now, Professor Strang, you see the problem.

Why is that? Okay, why am I getting minus 3 3 here? And here I'm getting 3 minus 3. Fooey. I don't know why. It shouldn't have happened, but it did. Now, okay, you could say, "Well, uh just uh uh that the eigen vector there could have I could have had the minus sign here for that eigen vector. But, I'm not happy happy about that. Hm. Okay. So, I realize there's a little catch here somewhere, and I'm not I may not see it until uh Wednesday, which then gives you a very important reason to come back on Wednesday to catch that sign difference. So, what did I do illegally? I think I put the eigen vectors in that matrix V transpose.

Okay, I'm going to have to think. Why did that come out uh with the with the opposite sign? So, you see, I mean, if I had a minus there, I would be all right, but I don't want that. I want positive entries down the uh diagonal of Sigma squared. Okay, it'll come to me, but uh I'm going to leave this example to to to finish. Okay. And the beauty of uh these sliding boards is I can make that go away. Um Can I uh Let me Let me not do it, though. Yeah, let me take a second example. Let me take a second example where the matrix is singular. So, rank one. Okay. So, let me take as a example two where my matrix A is going to be rectangular again.

Let me make Let me just make it 4 3 8 6. Okay, that's a rank one matrix. So, that has a null space. And only a one-dimensional row space and column space. So, actually, the the my my picture becomes easy for this matrix. Because what's my columns and my row space for this one? So, this is 2 by 2. So, my my pictures are both two-dimensional. My My row space is all multiples of the vector 4 3. So, the whole the row space is just a line, right? That's the row space. And the null space, of course, is the perpendicular line. So, the row space for this matrix is multiples of 4 3. Typical row. Okay. What's the column space?

The columns are all multiples of 4 8 3 6 1 2. The column space then goes in like this direction. So, the column space when I look at those columns, the column space is only one dimensional cuz the rank is one. It's multiples of of 4 8. Okay. And what's the null space of A transpose? It's the perpendicular guy. There's So, this was the null space of A. And this is the null space of A transpose. Okay. What I want to say here is that the the choosing these orthogonal bases for the row space and the column space is like no problem. They're only one dimensional. So, what should V be? V should be V1, but yeah, V1 rather.

V1 is supposed to be a unit vector. There's only one V1 to choose here, only one dimension in the row space. I just want to make it a unit vector. So, V1 will be It'll be this vector, but made into a unit vector. So, 4 0.8 0.6 4/5 3/5. And what will be U1? U1 will be the unit vector there. So, I want to turn 4 8 or 1 2 into a unit vector. So, U1 will be Uh let's see. If it's 1 2, then it's what multiple of 1 2 do I want? That has length square root of 5, so I have to divide by square root of 5. Let me complete the singular value decomposition for this matrix. So, this matrix 4 3 8 6 is So, I know what U1 Here's Here's A.

And I want to get U, the basis in the column space. And it has to start with uh this guy. 1/ √ 5 2/ √ 5 Then, I want the sigma. Okay. What are we expecting now for sigma? Where it This is only a This is only a rank one matrix. We're only expecting a sigma one, which I have to find. But, zeros here. Okay. So, what's sigma one? It's We should see it. It should be the Where Where did these sigmas come from? They came from A transpose A. So, I can I do that little calculation over here? A transpose A is 4 3 4 3 8 6 times 4 3 8 6. This had better This is a rank one matrix. This is going to be The whole thing will have rank one.

That's 16 and 64 is 80. 12 and 48 is 60. 12 and 48 is 60. 9 and 36 is 45. Okay. It's a rank one matrix. Of course. Every row is a multiple of 4 3. And what's the eigen What are the eigen values of that matrix? So, this is like the calculation This is like practicing now. What are the eigen values of this rank one matrix? Well, tell me one eigen value. Since the rank is only one, one eigen value is going to be zero. And then you know that the other eigen value is going to be 125. So, that's sigma squared, right? In A transpose A. So, this will be the square root of 125. And then finally, the V transpose the Vs will be There's V1.

And what's V2? What's V2 in the What's How do I make this into a orthonormal basis? Well, V2 is in the null space direction. It's It's perpendicular to that. So, 0.6 and minus 0.8. So, those are the Vs that go in here. 0.8 0.6 and 0.6 minus 0.8. Okay. And I guess I better finish this guy. So, this guy All I want is to complete the orthonormal basis. It'll be coming from there. It'll be a 2/ √ 5 and a minus 1/ √ 5. I could have take Let me take √ 5 out of that matrix to make it look better. So, 1/ √ 5 times 1 1 2 2 - 1. Okay. So, there I have including the square root of 5, I That's an orthogonal matrix.

That's an orthogonal matrix. That's a diagonal matrix. And its rank is only one. And now if I do that multiplication, I pray that it comes out right. The square root of 5 will cancel into that square root of 125 and leave me with the square root of 25, which is 5. And 5 will multiply these numbers, and I'll get whole numbers, and out will come A. Okay. That's a second like a second example showing how the null space guy. So, this This vector and the and and this one were multiplied by this zero. So, they they were easy to deal with. It was the key ones are the ones in the column space and the row space.

Do you see how I'm getting columns here, diagonal here, rows here coming together to produce A? Okay. That's the singular value decomposition. So, uh let let me think what I want to add to to complete this topic. So, what we're really doing So, that's two examples. And now let's think what we're really doing. We're We're choosing the right basis for the four subspaces of linear algebra. Let me Let me Let me write this down. So, V1 up to VR is an orthonormal basis for the row space. U1 up to UR is an orthonormal basis for the column space. And then I just finish those out by VR + 1 The rest up to VN is an orthonormal basis for the null space.

And finally, UR + 1 up to UM is an orthonormal basis for the null space of A transpose. Do you see that we finally got the bases right? They're right because they're orthonormal. And also, I mean, the Again, Gram-Schmidt would have done this in chapter four. Here we needed eigen values because these bases make the matrix diagonal. A times VI is a multiple of UI. So, I'll put and The matrix has been made diagonal. When we choose these bases, the the There's no coupling between Vs and no coupling between Us. Each A A times each V is in the direction of the corresponding U. So, it's exactly the right basis for the four fundamental subspaces.

And of course, their dimensions are what we know. The dimension of the row space is the rank R and so is the dimension of the column space. The dimension of the null space is n minus r. That's how many vectors we need and m minus r basis vectors for the left null space, the null space of a transpose. Okay. I'm going to stop there. I could develop further from the from the SVD but we'll see it again in the very last lectures of the course. There's the SVD. Thanks.