05 - Singular Values and Singular Vectors
2.7M subscribers
SUBSCRIBED
MIT A 2020 Vision of Linear Algebra, Spring 2020 Instructor: Gilbert Strang View the complete course: https://ocw.mit.edu/2020-visionYouTube Playlist: https://www.youtube.com/playlist?list...Data matrices in machine learning are not square, so they require a step beyond eigenvalues: The Singular Value Decomposition (SVD) expresses every matrix by its singular values and vectors. License: Creative Commons BY-NC-SA More information at https://ocw.mit.edu/termsMore courses at https://ocw.mit.edu
00:00
00:13
GILBERT STRANG: OK, so I was speaking
00:16
about eigenvalues and eigenvectors
00:19
for a square matrix.
00:21
And then I said for data for many other applications,
00:25
the matrices are not square.
00:27
We need something that replaces eigenvalues and eigenvectors.
00:31
And what they are--
00:32
and it's perfect-- is singular values and singular vectors.
00:37
So may I explain singular values and singular vectors?
00:41
This slide shows a lot of them.
00:45
The point is that there will be--
00:51
now I don't say eigenvectors-- two-- different left singular
00:54
vectors.
00:55
They will go into this matrix u.
00:58
Right singular vectors will go into v.
01:01
It was the other case that was so special.
01:03
When the matrix was symmetric, then the left
01:06
equals left eigenvector.
01:08
They're the same as the right one.
01:10
That's sort of sensible.
01:12
But a general matrix and certainly
01:14
a rectangular matrix--
01:16
01:19
well, we don't call them eigenvectors,
01:21
because that would be confusing-- we
01:22
call them singular vectors.
01:24
And then, inbetween are not eigenvalues,
01:28
but singular values.
01:31
Oh, right.
01:32
Oh, hiding over here is a key.
01:34
A times the v's gives sigma times the u's.
01:40
So that's the replacement for ax equal lambda
01:43
x, which had x on both sides.
01:45
OK, now we've got two.
01:48
But the beauty is now we've got two of those to work with.
01:51
We can make all the u's orthogonal to each other--
01:57
all the v's orthogonal to each other.
02:01
We can do what only symmetric matrices
02:03
could do for eigenvectors.
02:06
We can do it now for all matrices,
02:08
not even squares, just this is where life is, OK.
02:13
And these numbers instead of the lambdas
02:15
are called singular values.
02:17
And we use the letter sigma for those.
02:20
And here is a picture of the geometry in 2 by 2
02:24
if we had a 2 by 2 matrix.
02:26
So you remember, factorization breaks
02:29
up a matrix into separate small parts,
02:33
each doing its own thing.
02:36
So if I multiply by vector x, the first thing
02:39
that's going to hit it is v transpose.
02:42
V transpose is an orthogonal matrix.
02:45
Remember, I said we can make these singular vectors
02:48
perpendicular.
02:50
That's what an orthogonal matrix-- so it's just
02:52
like a rotation that you see.
02:54
So the v transpose is just turns the vector to get here
03:00
to get to the second one.
03:01
Then I'm multiplying by the lambdas.
03:04
But they're not lambdas now.
03:05
They're sigma.
03:07
The matrix, so that's capital sigma.
03:10
So there is sigma 1 and sigma 2.
03:12
What they do is stretch the circle.
03:16
It's a diagonal matrix.
03:17
So it doesn't turn things.
03:20
But it stretches the circle to an ellipse
03:23
because it gets the two different singular values
03:26
in-- sigma 1 and sigma 2.
03:28
And then the last guy, the u is going to hit last.
03:34
It takes the ellipse and turns out again.
03:36
It's again a rotation--
03:38
rotation, stretch, rotation.
03:41
I'll say it again--
03:42
rotation, stretch, rotation.
03:45
That's what singular values and singular
03:47
vectors do, the singular value decomposition.
03:51
And it's got the best of all worlds here.
03:56
It's got the rotations, the orthogonal matrices.
04:01
And it's got the stretches, the diagonal matrices.
04:06
Compared to those two, those are the greatest.
04:07
Triangular matrices were good when we were young an hour ago.
04:13
Now, we're seeing the best.
04:15
OK, now let me just show you where they come from.
04:20
Oh, so how to find these v's.
04:23
Well, the answer is, if I'm looking for orthogonal vectors,
04:27
the great idea is find a symmetric matrix
04:32
and with those eigenvectors.
04:35
So these v's that I want for A are actually eigenvectors
04:40
of this symmetric matrix A transpose times
04:43
A. That's just nice.
04:45
So we can find those singular vectors
04:48
just as fast as we can find eigenvectors
04:51
for a symmetric matrix.
04:52
And we know there, because A transpose A is symmetric.
04:56
We know the eigenvectors are perpendicular
04:59
to each other orthonormal.
05:01
OK, and now what about the other ones because remember,
05:04
we have two sets.
05:06
The u's-- well, we just multiply by A. And we've got the u's.
05:13
Well, and divide by sigmas, because these vectors u's
05:16
and v's are unit vectors, length one.
05:19
So we have to scale them properly.
05:22
And this was a little key bit of algebra to check that,
05:27
not only the v's were orthogonal,
05:29
but the u's are orthogonal.
05:31
Yeah, it just comes out--
05:33
comes out.
05:34
So this singular value decomposition,
05:36
which is maybe, well, say 100 years old, maybe a bit more.
05:41
But it's really in the last 20, 30 years that singular values
05:48
have become so important.
05:50
This is the best factorization of them all.
05:54
And that's not always reflected in linear algebra courses.
05:57
So part of my goal today is to say get to singular values.
06:04
If you've done symmetric matrices and their eigenvalues,
06:08
then you can do singular values.
06:11
And I think that's absolutely worth doing, OK, yeah,
06:17
so and remembering down here that capital Sigma stands
06:22
for the diagonal matrix of these positive numbers, sigma 1,
06:27
sigma 2 down to sigma r there.
06:30
The rank, which came way back in the first slides,
06:34
tells you how many there are.
06:36
Good, good.
06:40
Oh, here's an example.
06:43
So I took a small matrix because I'm
06:45
doing this by pencil and paper and actually showing you
06:49
that the singular value.
06:52
So there is my matrix, 2 by 2.
06:55
Here are the u's.
06:56
Do you see that those are orthogonal--
06:58
1, 3 against minus 3, 1?
07:01
Take the dot product, and you get 0.
07:03
The v's are orthogonal.
07:04
The sigma is diagonal.
07:06
And then the pieces from that add back to the matrix.
07:11
So it's really, it's broken my matrix
07:14
into a couple of pieces--
07:16
one for the first singular value in vector,
07:20
and the other for the second singular value in vector.
07:23
And that's what data science wants.
07:26
Data science wants to know what's important in the matrix?
07:30
Well, what's important is sigma 1, the big guy.
07:34
Sigma 2, you see.
07:36
Well, it was 3 times smaller--
07:38
3/2 versus 1/2.
07:40
So if I had a 100 by 100 matrix or 100 by 1,000,
07:45
I'd have 100 singular values and maybe the first five I'd keep.
07:51
If I'm in the financial market, those guys,
07:54
those first numbers are telling me
07:57
maybe what bond prices are going to do over time.
08:00
And it's a mixture of a few features,
08:06
but not all 1,000 features, right.
08:09
So this is singular value decomposition
08:13
picks out the important part of a data matrix.
08:17
And you cannot ask for a more than that.
08:19
08:22
Here's what you do with a matrix is just totally enormous--
08:25
too big to multiply--
08:27
too big to compute.
08:29
Then you randomly sample it.
08:37
Yeah, maybe the next slide even mentions
08:39
that word randomized numerical linear algebra.
08:42
So this, I'll go back to this.
08:46
So the singular value decomposition--
08:48
this, what we just talked about with the u's and the v's
08:52
and the sigmas.
08:54
Sigma 1 is the biggest.
08:56
Sigma r is the smallest.
08:59
So in data science, you very often
09:01
keep just these first ones, maybe the first k, the k
09:06
largest ones.
09:08
And then you've got the matrix that
09:10
has rank only k, because you're only working with k vectors.
09:14
And it turns out that's the closest one to the big matrix
09:19
A. So this singular value is among other things
09:23
is picking out, putting in order of importance
09:27
the little pieces of the matrix.
09:30
And then you can just pick a few pieces to work with.
09:34
Yeah, yeah.
09:36
And the idea of norms is how to measure the size of a matrix.
09:40
Yeah, but I'll leave that for the future.
09:46
And randomized linear algebra I just want to mention.
09:50
Seems a little crazy that by just randomly sampling
09:53
a matrix, we could learn anything about it.
09:58
But typically data is sort of organized.
10:02
It's not just totally random stuff.
10:05
So if we want to know like, my friend in the Broad Institute
10:09
was doing the ancient history of man.
10:14
So data from thousands of years ago.
10:18
So he had a giant matrix--
10:20
a lot of data-- too much data.
10:22
And he said, how can we find the singular value decomposition?
10:27
Pick out the important thing.
10:29
So you had to sample the data.
10:33
Statistics is a beautiful important subject.
10:36
And it leans on linear algebra.
10:40
Data science leans on linear algebra.
10:44
You are seeing the tool.
10:46
Calculus would be functions would be continuous curves.
10:52
Linear algebra is about vectors.
10:54
This is just n components.
10:57
And that's where you compute.
10:59
And that's where you understand.
11:01
OK.
11:03
Oh, this is maybe the last slide to just
11:07
help orient you in the courses.
11:10
So at MIT 18.06 is the Linear Algebra Course.
11:14
And maybe you know 18.06 and also
11:17
18.06 Scholar, SC, on OpenCourseWare.
11:23
And then this is the new course with the new book, 18.065.
11:30
So its numbers sort of indicating a second course
11:34
in linear algebra.
11:35
That's when I'm actually teaching now,
11:36
Monday, Wednesday, Friday.
11:40
And so that starts with linear algebra,
11:42
but it's mostly about deep learning--
11:44
learning from data.
11:45
So you need statistics.
11:47
You need optimization, minimizing.
11:50
Big functions of calculus comes into it.
11:53
So that's a lot of fun to teach and to learn.
11:58
And, of course, it's tremendously
12:01
important in industry now.
12:03
And Google and Facebook and ever so many companies
12:06
need people who understand this.
12:09
And, oh, and then I am repeating 18.06
12:12
because there is this new book coming, I hope.
12:16
Did some more this morning.
12:19
Linear Algebra for Everyone.
12:20
So I have optimistically put 2021.
12:23
And you're the first people that know about it.
12:27
So these are the websites for the two that we have.
12:30
That's the website for the linear algebra
12:32
book, math.mit.edu.
12:35
And this is the website for the Learning from Data book.
12:39
So you see there the table of contents and all and solutions
12:43
to problems-- lots of things.
12:47
Thanks for listening to this is--
12:50
what-- maybe four or five pieces in this 2020 vision
12:56
to update the videos that have been watched
13:03
so much on OpenCourseWare.
13:07
Thank you.
13:09
English - CC (English)