06. Singular Value Decomposition (SVD)
2.71M subscribers
SUBSCRIBED
MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning, Spring 2018 Instructor: Gilbert Strang View the complete course: https://ocw.mit.edu/18-065S18YouTube Playlist: https://www.youtube.com/playlist?list...Singular Value Decomposition (SVD) is the primary topic of this lecture. Professor Strang explains and illustrates how the SVD separates a matrix into rank one pieces, and that those pieces come in order of importance. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/termsMore courses at https://ocw.mit.edu
00:00
00:01
ANNOUNCER: The following content is provided under a Creative
00:03
Commons license.
00:05
Your support will help MIT Open Courseware
00:07
continue to offer high quality educational resources for free.
00:11
To make a donation or to view additional materials
00:14
from hundreds of MIT courses, visit
00:16
MITOpenCourseware@OCW.MIT.edu.
00:18
00:22
PROFESSOR: So this is a big day mathematically speaking,
00:25
because we come to this key idea, which is
00:32
a little bit like eigenvalues.
00:34
Well, a lot like eigenvalues, but different
00:36
because the matrix A now is more usually rectangular.
00:44
So for a rectangular matrix, the whole idea of eigenvalues
00:48
is shot because if I multiply A times a vector
00:54
x in n dimensions, out will come something in m dimensions
00:59
and it's not going to equal lambda x.
01:01
So Ax equal lambda x is not even possible if A is rectangular.
01:08
And even if A is square, what are the problems, just thinking
01:13
for a minute about eigenvalues?
01:16
The case I wrote up here is the great case
01:20
where I have a symmetric matrix and then it's
01:24
got a full set of eigenvalues and eigenvectors
01:28
and they're orthogonal, all good.
01:31
But for a general square matrix, either the eigenvectors
01:36
are complex--
01:38
eigenvalues are complex or the eigenvectors
01:42
are not orthogonal.
01:43
01:46
So we can't stay with eigenvalues forever.
01:50
That's what I'm saying.
01:52
And this is the right thing to do.
01:55
So what are these pieces?
01:57
So these are the left and these are the right singular vectors.
02:07
So this is the new word is singular.
02:10
02:16
And in between go the--
02:18
not the eigenvalues, but the singular values.
02:23
So we've got the whole point now.
02:25
You've got to pick up on this.
02:27
There are two sets of singular vectors, not one.
02:32
For eigenvectors, we just had one set, the Q's.
02:38
Now we have a rectangular matrix,
02:41
we've got one set of left eigenvectors in m dimensions,
02:47
and we've got another set of right eigenvectors
02:50
in n dimensions.
02:53
And numbers in between are not eigenvalues,
02:58
but singular values.
02:59
So these guys are--
03:00
03:03
let me write what that looks like.
03:05
This is, again, a diagonal matrix sigma 2 to sigma r,
03:11
let's say.
03:13
So it's again, a diagonal matrix in the middle.
03:17
But the numbers on the diagonal are all positive or 0.
03:26
And they're called singular values.
03:29
So it's just a different world.
03:31
So really, the first step by have to do, the math step,
03:35
is to show that any matrix can be
03:41
factored into u times sigma times v transpose.
03:47
So that's the parallel to the spectral theorem
03:51
that any symmetric matrix could be factored that way.
03:55
So you're good for that part.
03:58
We just have to do it to see what are u and sigma and v?
04:04
What are those vectors and those singular values?
04:08
Let's go.
04:09
So the key is that A transpose A is a great matrix.
04:16
So that's the key to the math is A transpose A. So
04:24
what are the properties of A transpose A?
04:26
A is rectangular again.
04:28
So maybe m by n A transpose.
04:34
So this was m by n.
04:36
And this was n by m.
04:39
So we get a result that's n by n.
04:44
And what else can you tell me about A transpose A?
04:48
It's a metric.
04:49
That's a big deal.
04:51
And it's square.
04:53
And well yeah, you can tell me more now,
04:55
because we talked about something,
04:58
a topic that's a little more than symmetric last time.
05:04
The matrix A transpose A will be positive, definite.
05:09
It's eigenvalues are greater or equal to 0.
05:13
And that will mean that we can take their square roots.
05:18
And that's what we will do.
05:19
So A transpose A we'll have a factorization.
05:23
It's symmetric.
05:24
It'll have a like, a Q lambda Q transpose, but I'm
05:29
going to call it V lambda--
05:31
no, yeah, lambda-- I'll still call it lambda V transpose.
05:36
So these V's-- what do we know about eigenvectors of these
05:39
V's or eigenvectors of this guy?
05:43
Square, symmetric, positive, definite matrix.
05:46
So we're in good shape.
05:47
And what do we know about the eigenvalues of A transpose A?
05:52
They are all positive.
05:55
So the eigenvalues are-- well, or equal to 0.
05:59
And these guys are orthogonal.
06:02
And these guys are greater or equal to there.
06:04
06:07
So that's good.
06:09
That's one of our--
06:12
We'll depend a lot on that.
06:14
But also, you've got to recognize that A,
06:17
A transpose is a different guy, A, A transpose.
06:24
So what's the shape of A, A transpose?
06:28
How big is that?
06:30
Now I've got-- what do I have?
06:33
M by n times n by m.
06:35
So this will be what size?
06:37
N by m.
06:38
Different shape but with the same eigenvalues--
06:44
the same eigenvalues.
06:45
So it's going to have some other eigenvectors, u-- of course,
06:48
I'm going to call them u, because I'm
06:49
going to go in over there.
06:51
They'll be the same.
06:53
Well, they're saying yeah, let me--
06:56
I shouldn't-- I have to say when I say the same,
07:02
I can't quite literally mean the very same,
07:05
because this has got n eigenvalues and this has m
07:10
eigenvalues.
07:12
But the missing guys, the ones that are in one of them
07:16
and not in the other, depending on the sizes, are zeros.
07:21
So really, the heart of the thing, the non-zero eigenvalues
07:25
are the same.
07:26
07:29
Well actually, I've pretty much revealed
07:34
what the SVD is going to use.
07:38
It's going to use the U's from here and the V's from here.
07:43
But that's the story.
07:45
You've got to see that story.
07:48
So fresh start on the singular value decomposition.
07:52
What are we looking for?
07:54
Well, as a factorization--
07:56
so we're looking for--
07:58
08:03
we want A. We want vectors v, so that when I multiply by v--
08:12
so if it was an eigenvector, it would be Av equal lambda v.
08:17
But now for A, it's rectangular.
08:20
It hasn't got eigenvectors.
08:22
So Av is sigma, that the new singular value times u.
08:31
That's the first guy and the second guy and the rth guy.
08:38
I'll stop at r, the rank.
08:42
Oh, yeah.
08:43
08:46
Is that what I want?
08:46
08:50
A-- let me just see.
08:53
Av is sigma u.
08:56
Yeah, that's good.
08:58
So this is what takes the place of Ax equal lambda x.
09:02
A times one set of singular vectors
09:06
gives me a number of times the other set of singular vectors.
09:09
And why did I stop at r the rank?
09:13
Because after that, the sigmas are 0.
09:15
So after that, I could have some more guys,
09:19
but they'll be in the null space 0 on down to of Vn.
09:29
So these are the important ones.
09:32
So that's what I'm looking for.
09:35
Let me say it now in words.
09:38
I'm looking for a bunch of orthogonal vectors v
09:43
so that when I multiply them by A
09:46
I get a bunch of orthogonal vectors u.
09:49
That is not so clearly possible.
09:53
But it is possible.
09:56
It does happen.
09:57
I'm looking for one set of orthogonal vectors
09:59
v in the input space, you could say,
10:02
so that the Av's in the output space are also orthogonal.
10:07
10:11
In our picture of the fundamental--
10:14
the big picture of linear algebra,
10:18
we have v's in this space, and then stuff in the null space.
10:27
And we have u's over here in the columns space
10:34
and some stuff in the null space over there.
10:38
And the idea is that I have orthogonal v's here.
10:42
And when I multiply by A--
10:44
so multiply by A--
10:48
then I get orthogonal u's over here, orthogonal to orthogonal.
10:54
That's what makes the V's and they u's special.
11:00
Right?
11:01
That's the property.
11:03
And then when we write down-- well,
11:04
let me write down what that would mean.
11:07
So I've just drawn a picture to go with this--
11:11
those equations.
11:13
That picture just goes with these equations.
11:16
And let me just write down what it means.
11:18
It means in matrix-- so I've written it.
11:23
Oh yeah, I've written it here in vectors one at a time.
11:28
But of course, you, know I'm going
11:30
to put those vectors into the columns of a matrix.
11:33
So A times v1 up to let's say vr will equal--
11:44
oh yeah.
11:45
It equals sigma as times u.
11:47
So this is what I'm after is u1 up to ur
11:53
multiplied by sigma 1 along to sigma r.
11:58
12:01
What I'm doing now is just to say I'm
12:05
converting these individual singular
12:10
vectors, each v going into a u to putting them
12:14
all together into a matrix.
12:16
And of course, what I've written here is Av equals u sigma,
12:21
Av equals u sigma.
12:25
12:28
That's what that amounts to.
12:32
Well, then I'm going to put a v transpose on this side.
12:38
And I'm going to get to A equals u sigma v transpose,
12:44
multiplying both sides there by v transpose.
12:48
I'm kind of writing the same thing in different forms,
12:51
matrix form, vector at a time form.
12:55
12:57
And now we have to find them.
13:01
Now I've used up boards saying what we're after,
13:06
but now we've got to get there.
13:08
So what are the v's and what are the u's?
13:10
13:15
Well, the cool idea is to think of A transpose A.
13:20
So you're with me what we're for.
13:23
And now think about A transpose A.
13:26
So if this is what I'm hoping for,
13:29
what will A transpose A turn out to be?
13:33
13:36
So big moment that's going to reveal what the v's are.
13:41
So if I form A transpose A--
13:46
so A transpose-- so I got to transpose this guy.
13:50
So A transpose is V sigma transpose U transpose, right?
13:57
And then comes A, which is this, U sigma V transpose.
14:04
So why did I do that?
14:08
Why is it that A transpose A is the cool thing to look at
14:12
to make the problem simpler?
14:14
Well, what becomes simpler in that line just written?
14:20
U transpose U is the identity, because I'm looking
14:25
for orthogonal, in fact orthonormal U's.
14:29
So that's the identity.
14:31
So this is V sigma transpose sigma V transpose.
14:38
And I'll put parentheses around that because that's
14:42
a diagonal matrix.
14:43
14:48
What does that tell me?
14:50
What does that tell all of us?
14:53
A transpose A has this form.
14:55
Now we've seen that form before.
14:57
We know that this is a symmetric matrix, symmetric
15:01
and even positive definite.
15:03
So what are the v's?
15:06
The v's are the eigenvectors of A transpose A.
15:13
This is the Q lambda Q transpose for that symmetric matrix.
15:20
So we know the v's are the eigenvectors,
15:24
v is the eigenvectors of A transpose A.
15:32
I guess we're also going to get the singular values.
15:35
So the sigma transpose sigma, which will be the sigma squared
15:41
are the eigenvalues of A transpose A. Good!
15:51
15:55
Sort of by looking for the correct thing, U sigma V
15:58
transpose and then just using the U transpose U
16:01
equal identity, we got it back to something
16:04
we perfectly recognize.
16:07
A transpose A has that form.
16:09
So now we know what the V's are.
16:11
And if I do it the other way, which, what's the other way?
16:17
Instead of A transpose A, the other way
16:20
is to look at A, A transpose.
16:23
And if I write all that down, that a
16:26
is the U sigma V transpose, and the A transpose is the V sigma
16:32
transpose U transpose.
16:35
And again, this stuff goes away and leaves me
16:39
with U sigma, sigma transpose U transpose.
16:45
So I know what the U's are too.
16:47
They are eigenvectors of A, A transpose.
16:53
17:00
Isn't that a beautiful symmetry?
17:03
You just-- A transpose A and A, A transpose
17:06
are two different guys now.
17:08
So each has its own eigenvectors and we use both.
17:13
It's just right.
17:15
And I just have to take the final step,
17:19
and we've established the SVD.
17:23
So the final step is to remember what I'm going for here.
17:26
17:29
A times a v is supposed to be a sigma times a u.
17:33
17:36
See, what I have to deal with now
17:37
is I haven't quite finished.
17:41
It's just perfect as far as it goes,
17:44
but it hasn't gone to the end yet because we
17:48
could have double eigenvalues and triple eigenvalues,
17:51
and all those horrible possibilities.
17:56
And if I have triple eigenvalues or double eigenvalues,
18:01
then what's the deal with eigenvectors
18:04
if I have double eigenvalues?
18:05
Suppose a matrix has a symmetric matrix,
18:10
has a double eigenvalue.
18:12
Let me just take an example.
18:14
So symmetric matrix like say, 1, 1, 5, make it.
18:20
Why not?
18:23
What's the deal with eigenvectors
18:25
for that matrix 1, 1, 5?
18:29
So 5 has got an eigenvector.
18:31
You can see what it is, 0, 0, 1.
18:35
What about eigenvectors that go with lambda equal 1
18:39
for that matrix?
18:42
What's up?
18:43
What would be eigenvectors for a lambda equal 1?
18:48
Unfortunately, there was a whole plane of them.
18:52
Any vector of the form x, y, 0.
18:56
Any vector in the x, y plane would produce x, y, 0.
19:04
So I have a whole plane of eigenvectors.
19:06
And I've got to pick two that are orthogonal, which I can do.
19:11
And then they have to be--
19:12
in the SVD those two orthogonal guys
19:15
have to go to two orthogonal guys.
19:18
In other words, it's a little bit of detail here,
19:23
a little getting into this exactly what is--
19:28
well, actually, let me tell you the steps.
19:38
So I use this to conclude that the V's the singular vectors
19:44
should be eigenvalues.
19:46
I concluded those guys from this step.
19:49
Now I'm not going to use this step so much.
19:52
Of course, it's in the back of my mind but I'm not using it.
19:57
I'm going to get the u's from here.
20:00
So u1 is A v1 over sigma 1 ur is Avr over sigma r.
20:17
You see what I'm doing here?
20:20
I'm picking in a possible plane of things the one I want,
20:28
the u's I want.
20:29
So I've chosen the v's.
20:31
I've chosen the sigmas.
20:33
They were fixed for A transpose A.
20:37
The eigenvectors are v's, the things--
20:40
the eigenvalues are sigma squared.
20:44
And now then this is the u I want.
20:49
Are you with me?
20:50
So I want to get these u's correct.
20:56
And if I have a whole plane of possibilities,
20:59
I got to pick the right one.
21:01
And now finally, I have to show that it's the right one.
21:05
So what is left to show?
21:08
I should show that these u's are eigenvectors of A, A transpose.
21:14
21:16
And I should show that they're orthogonal.
21:21
That's the key.
21:22
I would like to show that these are orthogonal.
21:27
And that's what goes in this picture.
21:30
The v's-- I've got orthogonal, guys,
21:32
because they're the eigenvectors of a symmetric matrix.
21:36
Pick them orthogonal.
21:37
But now I'm multiplying by A, so I'm
21:40
getting the u which is Av over sigma for the basis vectors.
21:46
And I have to show they're orthogonal.
21:48
So this is like the final moment.
21:52
Does everything come together right?
21:54
21:57
If I've picked the v's as the eigenvectors of A transpose A,
22:02
and then I take these for the u, are they orthogonal?
22:09
So I would like to think that we can check that fact
22:12
and that it will come out.
22:15
Could you just help me through this one?
22:18
I'll never ask for anything again, just get the SVD one.
22:23
22:31
So I would like to show that u1--
22:37
so let me put up what I'm doing.
22:40
I'm trying to show that u1 transpose u2 is 0.
22:47
They're orthogonal.
22:49
So u1 is A v1 over sigma 1.
22:57
That's transpose.
22:59
That's u1.
23:00
And u2 is A v2 over sigma 2.
23:06
And I want to get 0.
23:08
The whole conversation is ending right here.
23:13
Why is that thing 0?
23:16
The v's are orthogonal.
23:19
We know the v's are orthogonal.
23:21
They're orthogonal eigenvectors of A transpose A.
23:25
Let me repeat that.
23:26
The v's are orthogonal eigenvectors of A transpose A,
23:36
which I know we can find them.
23:40
Then I chose the u's to be this.
23:42
And I want to get the answer 0.
23:44
Are you ready to do it?
23:48
We want to compute that and get 0.
23:53
So what do I get?
23:56
We just have to do it.
23:57
So I can see that the denominator is that.
24:02
So is it v1 transpose A transpose times A v2.
24:09
24:14
And I'm hoping to get 0.
24:17
Do I get 0 here?
24:21
You hope so.
24:23
v1 is orthogonal v2.
24:25
But I've got A transpose A stuck in the middle there.
24:28
So what happens here?
24:33
How do I look at that?
24:34
24:37
v2 is an eigenvector of A transpose A. Terrific!
24:44
24:47
So this is v1 transpose.
24:50
And this is the matrix times v2.
24:54
So that's sigma 2 transpose v2, isn't it?
25:00
It's the eigenvector with eigenvalue sigma
25:04
2 squared times v2.
25:07
Yeah, divided by sigma 1 sigma 2.
25:10
25:16
So the A's are out of there now.
25:18
25:21
So I've just got these numbers, sigma 2 squared.
25:25
So that would be sigma 2 over sigma 1--
25:28
I've accounted for these numbers here-- times v1 transpose v2.
25:34
And now what's up?
25:40
They're orthonormal.
25:43
We got it.
25:44
That's 0.
25:45
That is 0 there, yeah.
25:49
So not only are the v's orthogonal to each other,
25:53
but because they're eigenvectors of A transpose A, when
25:57
I do this, I discover that the Av's
26:00
are orthogonal to each other over in the column space.
26:06
So orthogonal v's in the row space, orthogonal Av's
26:11
over in column space.
26:13
That was discovered late-- much long after eigenvectors.
26:19
And it's a interesting history.
26:22
And it just comes out right.
26:26
And then it was discovered, but not much used, for oh,
26:30
100 years probably.
26:32
And then people saw that it was exactly the right thing,
26:38
and data matrices became important, which
26:41
are large rectangular matrices.
26:47
And we have not--
26:48
oh, I better say a word, just a word here about actually
26:52
computing the v's and sigmas and the u's
26:58
So how would you actually find them?
27:02
What I most want to say is you would not
27:05
go this A transpose A route.
27:09
27:14
Why is it like it?
27:15
Is that a big mistake?
27:18
If you have a matrix A, say 5,000 by 10,000,
27:24
why is it a mistake to actually use
27:27
A transpose A in the computation?
27:29
We used it heavily in the proof.
27:33
And we could find another proof that wouldn't use it so much.
27:37
But why would I not multiply these two together?
27:45
It's very big, very expensive.
27:48
It adds in a whole lot of round off--
27:55
you have a matrix that's now--
27:57
its vulnerability to round off errors is squared--
28:02
that's called its condition number-- gets squared.
28:05
And you just don't go there.
28:07
So the actual computational methods are quite different.
28:12
And we'll talk about those.
28:14
But the A transpose A, because it's
28:18
symmetric positive definite, made the proof so nice.
28:24
You've seen the nicest proof, I'd say, of the--
28:30
Now I should think about the geometry.
28:33
So what does A equal A for u sigma?
28:38
Maybe I take another board, but it will fill it.
28:45
But it's a good U sigma V transpose.
28:49
28:52
So it's got three factors there.
28:55
And I would like then each factor
28:57
is kind of a special matrix.
28:59
U and V are orthogonal matrix.
29:01
So I think of those as rotations.
29:05
Sigma is a diagonal matrix.
29:07
I think of it as stretching.
29:09
So now I'm just going to draw the picture.
29:11
So here's unit vectors.
29:14
29:17
And the first thing-- so if I multiply by x,
29:22
this is the first thing that happens.
29:24
So that rotates.
29:26
So here's x's.
29:28
Then V transpose x's.
29:31
That's still a circle length and change
29:35
for those, when I multiply by an orthogonal matrix.
29:39
But the vectors turned.
29:43
It's a rotation.
29:46
Could be a reflection, but let's keep it as a rotation.
29:49
Now what does sigma do?
29:52
So I have this unit circle.
29:55
I'm in 2D.
29:56
29:59
So I'm drawing a picture of the vectors.
30:03
These are the unit vectors in 2D, x,y.
30:08
They got turned by the orthogonal matrix.
30:12
What does sigma do to that picture?
30:17
It stretches, because sigma multiplies
30:20
by sigma 1 in the first component,
30:22
sigma 2 in the second.
30:24
So it stretches these guys.
30:26
And let's suppose this is number 1 and this is number 2,
30:30
this is number 1 and number 2.
30:32
So sigma 1, our convention is sigma 1--
30:36
we always take sigma 1 greater or equal to sigma 2,
30:39
greater or equal whatever, greater equal, sigma rank.
30:43
And they're all positive.
30:46
30:49
And the rest are 0.
30:51
So sigma 1 will be bigger than sigma 2.
30:53
So I'm expecting a circle goes to an ellipse
30:58
when you stretch--
30:59
31:02
I didn't get it quite perfect, but not bad.
31:07
So this would be sigma 2 v2, sigma 1 v1,
31:15
and this would be sigma 2 v2.
31:17
And we now have an ellipse.
31:19
31:22
So we started with x is in a circle.
31:25
We rotated.
31:26
We stretched.
31:27
And now the final step is take these guys
31:31
and multiply them by u.
31:33
So this was the sigma V transpose x.
31:38
And now I'm ready for the u part which comes last
31:42
because it's at the left.
31:44
And what happens?
31:45
What's the picture now?
31:46
31:50
What does u do to the ellipse?
31:52
It rotates it.
31:54
It's another orthogonal matrix.
31:56
It rotates it somewhere, maybe there.
31:59
32:03
And now we see the u's, u2 and u1.
32:11
32:20
Well, let me think about that.
32:23
Basically, that's not that's right.
32:26
32:29
So this SVD is telling us something quite remarkable
32:34
that every linear transformation,
32:36
every matrix multiplication factors
32:40
into a rotation times a stretch times a different rotation,
32:46
but possibly different.
32:50
Actually, when would the u be the same as a v?
32:55
Here's a good question.
32:56
When is u the same as v when are the two singular
33:00
vectors just the same?
33:02
AUDIENCE: A square.
33:03
PROFESSOR: Because A would have to be square.
33:06
And we want this to be the same as Q lambda Q
33:12
transpose if they're the same.
33:15
So the U's would be the same as the V's
33:18
when the matrix is symmetric.
33:22
And actually we need it to be positive definite.
33:26
Why is that?
33:27
Because our convention is these guys are greater or equal to 0.
33:33
It's going to be the same, then--
33:36
so far a positive definite symmetric matrix,
33:42
the S that we started with is the same
33:47
as the A on the next line.
33:50
Yeah, the Q is the U, the Q transpose is the V transpose,
33:55
the lambda is the sigma.
33:57
So those are the good matrices.
33:59
And they're the ones that you can't improve basically.
34:02
They're so good you can't make a positive definite symmetric
34:06
matrix better than it is.
34:08
Well, maybe diagonalize it or something, but OK.
34:14
Now I think of like, one question here
34:18
that helps me anyway to keep this figure straight,
34:26
how I want to count the parameters
34:32
in this factorization.
34:38
So I am 2 by 2.
34:40
I'm 2 by 2.
34:43
So A has four numbers, a, b, c, d.
34:48
34:52
Then I guess I feel that four numbers should
34:55
appear on the right hand side.
34:59
Somehow the U and the sigma and the V transpose
35:03
should use up a total of four numbers.
35:06
So we have a counting match between the left side
35:10
that's got four numbers a, b, c, d, and the right side
35:14
that's got four numbers buried in there somewhere.
35:18
So how can we dig them out?
35:21
How many numbers in sigma?
35:23
That's pretty clear.
35:24
35:28
Two, sigma 1 and sigma 2.
35:31
The two eigenvalues.
35:34
How many numbers in this rotation?
35:36
35:39
So if I had a different color chalk,
35:42
I would put 2 for the number of things I counted for by sigma.
35:47
How many parameters does a two by two rotation require?
35:53
One.
35:54
And what's a good word for that one?
35:56
35:59
Is that one parameter?
36:02
It's like I have our cos theta, sine theta,
36:05
minus sine theta, cos theta.
36:07
There's a number theta.
36:09
It's the angle it rotates.
36:12
So that's one guy to tell the rotation angle, two guys
36:18
to tell the stretchings, and one more to tell the rotation
36:25
from you, adding up to four.
36:29
So those count-- that was a match up
36:31
with the four numbers, a, b, c, d that we start with.
36:35
Of course, it's a complicated relation between those four
36:39
numbers and rotations and stretches,
36:43
but it's four equals four anyway.
36:45
36:48
And I guess if you did three by threes--
36:51
oh, three by threes.
36:54
What would happen then?
36:56
So let me take three.
36:57
Do you want to care for three by threes?
37:01
Just, it's sort of satisfying to get four equal four.
37:04
But now what do we get three by three?
37:07
37:10
We got how many numbers here?
37:13
Nine.
37:13
37:17
So where are those nine numbers?
37:18
37:23
How many here?
37:24
That's usually the easy--
37:26
three.
37:28
So what's your guess for the how many in a rotation?
37:33
And a 3D rotation, you take a sphere and you rotate it.
37:38
How many how many numbers to tell you what's what--
37:42
to tell you what you did?
37:44
Three.
37:44
We hope three.
37:45
Yeah, it's going to be three, three, and three for the three
37:51
dimensional world that we live in.
37:53
So people who do rotations for a living understand that rotation
38:00
in 3D, but how do you see this?
38:02
AUDIENCE: Roll, pitch, and yaw.
38:03
PROFESSOR: Sorry?
38:04
AUDIENCE: Roll, pitch and yaw.
38:05
PROFESSOR: Roll, pitch, and yaw.
38:06
That sounds good.
38:07
I mean, it's three words and we've got it, right?
38:11
OK, yeah.
38:11
Roll, pitch and yaw.
38:13
Yeah, I guess a pilot hopefully, knows about those three.
38:19
Yeah, yeah, yeah.
38:21
Which is roll?
38:22
When you are like forward and back?
38:24
38:26
Does anybody, anybody?
38:29
Roll, pitch, and yaw?
38:30
38:33
AUDIENCE: Pitch is the up and down one.
38:35
PROFESSOR: Pitch is the up and down one.
38:37
OK.
38:37
AUDIENCE: Roll is like, think of a barrel roll.
38:41
And yaw is your side-to-side motion.
38:43
PROFESSOR: Oh, yaw, you stay in a plane and you--
38:46
OK, beautiful.
38:48
Right, right.
38:50
And that leads us to our four-- four dimensions.
38:54
What's your guess on 4D?
38:57
Well, we could do the count again.
38:59
If it was 4 by 4, we would have 16 numbers there.
39:02
And in the middle, we always have an easy time with that.
39:06
That would be 4.
39:07
So we've got 12 left to share out.
39:10
So six somehow-- six--
39:13
six angles in four dimensions.
39:17
Well, we'll leave it there.
39:19
Yeah, yeah, yeah.
39:21
OK.
39:23
So there is the SVD but without an example.
39:27
Examples, you know, I would have to compute A transpose A
39:30
and find it.
39:32
So the text will do that--
39:35
does it for a particular matrix.
39:37
Oh!
39:39
Yeah, the text does it for a matrix 3, 4, 0,
39:43
5 that came out pretty well.
39:48
A few facts we could learn though.
39:50
So if I multiply all the eigenvalues together
39:54
for a matrix A, what do I get?
39:58
I get the determinant.
39:59
What if I multiply the singular values together?
40:04
Well again, I get the determinant.
40:06
You can see it right away from the big formula.
40:10
Take determinant-- take determinant.
40:15
Well, assuming the matrix A is square.
40:17
So it's got a determinant.
40:18
Then I take determinant of this product.
40:21
I can take the separate determinants.
40:24
That has determinant equal to one.
40:29
An orthogonal matrix, the determinant is one.
40:39
And similarly, here.
40:40
So the product of the sigmas is also the determinant.
40:45
Yeah.
40:46
Yeah, so the product of the sigmas is also the determinant.
40:49
The product of the sigmas here will be 15.
40:52
But you'll find that sigma one is smaller than lambda 1.
40:59
So here are the eigenvalues, lambda 1
41:02
less or equal to lambda 2, say.
41:06
But the singular values are outside them.
41:12
Yeah.
41:13
But they still multiply.
41:14
Sigma 1 times sigma 2 will still be 15.
41:19
And that's the same as lambda 1 times lambda 2.
41:22
Yeah.
41:23
41:26
But overall, computing the examples of the SVD
41:31
take more time because--
41:35
well, yeah, you just compute A transpose A and you've got
41:40
the v's.
41:40
And you're on your way.
41:42
And you have to take the square root of the eigenvalues.
41:47
So that's the SVD as a piece of pure math.
41:54
But of course, what we'll do next time starting right away
41:58
is use SVD.
42:01
And let me tell you even today, the most--
42:04
yeah, yeah most important pieces of the SVD.
42:11
So what do I mean by pieces of the SVD?
42:14
I've got one more blackboard still to write on.
42:16
So here we go.
42:18
42:20
So let me write out A is the u's times the sigmas--
42:30
sigmas 1 to r times the v's--
42:35
v transpose v1 transpose down to vr transpose.
42:39
So those are across.
42:43
Yeah.
42:43
Actually what I've written here--
42:48
42:52
so you could say there is a big economies.
42:57
There is a smaller size SVD that has the real stuff that
43:01
really counts.
43:02
And then there's a larger SVD that has a whole lot of zeros.
43:07
So this it would be the smaller one, m by r.
43:10
43:13
This would be r by r.
43:15
And these would all be positive.
43:17
And this would be r by n.
43:19
43:24
So that's only using the r non-zeros.
43:29
All these guys are greater than zero.
43:33
Then the other one we could fill out
43:37
to get a square orthogonal matrix,
43:43
the sigmas and square v's v1 transpose to vn transpose.
43:52
So what are the shapes now?
43:54
This shape is m by m.
43:57
It's a proper orthogonal matrix.
43:59
This one also n by n.
44:01
So this guy has to be-- this is the sigma now.
44:04
So it has to be what size?
44:07
m by m.
44:08
That's the remaining space.
44:10
So it starts with the sigmas, and then it's all zeros,
44:17
accounting for null space stuff.
44:19
44:23
Yeah.
44:23
So you should really see that these two are possible.
44:29
That all these zeros when you multiply out,
44:34
just give nothing, so that really the only thing
44:37
that non-zero is in these bits.
44:41
But there is a complete one.
44:43
So what are these extra u's that are in the null space of A,
44:49
A transpose or A transpose A?
44:51
Yeah, so two sizes, the large size and the small size.
44:57
But then the things that count are all in there.
45:03
OK.
45:05
So I was going to do one more thing.
45:09
Let me see what it was.
45:13
45:17
So this is section 1.8 of the notes.
45:21
And you'll see examples there.
45:25
And you'll see a second approach to the finding the u's
45:33
and v's and sigmas.
45:36
I can tell you what that is.
45:38
But maybe with just do something nice at the end,
45:47
let me tell you about another factorization of A that's
45:57
famous in engineering, and it's famous in geometry.
46:09
So this is NEA is a U sigma V transpose.
46:12
We've got that.
46:14
Now the other one that I'm thinking of,
46:17
I'll tell you its name.
46:18
It's called the polar decomposition of a matrix.
46:23
46:26
And all I want you to see is that it's virtually here.
46:31
So a polar means--
46:33
what's polar in-- for a complex number,
46:37
what's the polar form of a complex number?
46:40
AUDIENCE: e to the i theta.
46:42
PROFESSOR: Yeah, it's e to the i theta times r.
46:44
Yeah.
46:46
A real guy-- so the real guy r will
46:49
translate into a symmetric guy.
46:52
And the e to the i theta will translate into--
46:55
46:58
what kind of a matrix reminds you of e to the i theta?
47:02
47:02
AUDIENCE: Orthogonal.
47:03
PROFESSOR: Orthogonal, size 1.
47:06
So orthogonal.
47:08
47:10
So that's a very, very kind of nice.
47:14
Every matrix factors into a symmetric matrix
47:18
times an orthogonal matrix.
47:20
And I of course, describe these as the most important classes
47:26
of matrices.
47:27
And here, we're saying every matrix is a S times a Q.
47:33
And I'm also saying that I can get that quickly out
47:37
of the SVD.
47:39
So I'm just want to do it.
47:43
So I want to find an S and find a Q out of this.
47:47
So to get an S--
47:49
So let me just start it.
47:50
U sigma-- but now I'm looking for an S.
47:55
So what shall I put in now?
47:59
I better put in--
48:02
if I've got to U sigma something,
48:04
and I want it to be a symmetric, I
48:06
should put in U transpose would do it.
48:13
But then if I put it in U transpose,
48:15
I've got to put it in U. So now I've got U sigma.
48:20
U transpose U is the identity.
48:22
Then I've got to get V transpose.
48:26
And have I got what the polar decomposition
48:30
is asking for in this line?
48:35
So, yeah.
48:36
What have I got here?
48:38
Where's the where's the S in this?
48:41
So you see, I took the SVD and I just put the identity in there,
48:46
just shifted things a little.
48:48
And now where's the S that I can read off?
48:50
48:55
For three, that's an S. That's a symmetric matrix.
49:01
And where's the Q?
49:02
Well, I guess we can see where the Q has to be.
49:06
It's here, yeah.
49:11
Yeah, so just by sticking U transpose U
49:14
and putting the parentheses right,
49:17
I recover that decomposition of a matrix, which
49:23
in mechanical engineering language, is language
49:27
tells me that any strain can be--
49:32
which is like stretching of elastic thing,
49:36
has a symmetric kind of a stretch and a internal twist.
49:48
Yeah.
49:50
So that's good.
49:51
Well, this was a 3, 6, 9 boards filled with matrices.
50:00
Well, it is 18 0, 6, 5.
50:02
So maybe that's all right.
50:04
But the idea is to use them on a matrix of data.
50:11
And I'll just tell you the key fact.
50:16
The key fact-- if I have a big matrix of data, A,
50:27
and if I want to pull out of that matrix
50:30
the important part, so that's what
50:33
data science has to be doing.
50:36
Out of a big matrix, some part of it is noise, some part of it
50:42
is signal.
50:43
I'm looking for the most important part of the signal
50:46
here.
50:46
So I'm looking for the most important part of the matrix.
50:49
50:52
In a way, the biggest numbers, but of course,
50:57
I don't look at individual numbers.
51:00
So what's the biggest part of the matrix?
51:04
What are the principal components?
51:06
Now we're really getting in--
51:08
51:11
it could be data.
51:13
And we want to do statistics, or we
51:15
want to see what has high variance, what
51:18
has low variance, we'll do these connections with statistics.
51:24
But what's the important part of the matrix?
51:26
Well, let me look at U sigma V transpose.
51:33
Here, yeah, let me look at it.
51:37
So what's the one most important part of that matrix?
51:43
The right one?
51:44
It's a rank one piece.
51:46
So when I say a part, of course it's going to be a matrix part.
51:50
So the simple matrix building block
51:52
is like a rank one matrix, a something, something transpose.
51:57
And what should I pull out of that
52:00
as being the most important rank one
52:02
matrix that's in that product?
52:06
So I'll erase the 1.8 while you think
52:09
what do I do to pick out the big deal, the thing that the data
52:16
is telling me first.
52:19
Well, these are orthonormal.
52:24
No one is bigger than another one.
52:26
These are orthonormal, no one is bigger than another one.
52:29
But here, I look here, which is the most important number?
52:35
Sigma 1.
52:37
Sigma 1.
52:37
So the part I pick out is this biggest number times
52:41
it's row times it's column.
52:45
So it's u 1 sigma 1 v1 transpose is the top principal part
52:55
of the matrix A. It's the leading
52:57
part of the matrix A. It's the biggest rank one
53:01
part of the matrix is there.
53:04
So computing those three guys is the first step
53:07
to understanding the data.
53:10
Yeah.
53:10
So that's what's coming next is--
53:12
and I guess tomorrow, since they moved--
53:17
MIT declared Tuesday to be Monday.
53:24
They didn't change Wednesday.
53:25
So I'll see you tomorrow for the principal components.
53:32
Good.
English - CC (English)
###