Computing the Singular Value Decomposition | MIT 18.06SC Linear Algebra, Fall 2011
Articles,  Blog

Computing the Singular Value Decomposition | MIT 18.06SC Linear Algebra, Fall 2011


PROFESSOR: Hey, we’re back. Today we’re going to do a
singular value decomposition question. The problem is really
simple to state: find the singular value
decomposition of this matrix C equals [5, 5; -1, 7]. Hit pause, try it yourself,
I’ll be back in a minute and we can do it together. All right, we’re back,
now let’s do it together. Now, I know Professor
Strang has done a couple of these in lecture,
but as he pointed out there, it’s really easy
to make a mistake, so you can never do enough
examples of finding the SVD. So, what does the SVD look like? What do we want to end up with? Well, we want a decomposition
C equals U sigma V transpose. U and V are going to be
orthogonal matrices, that is, their columns
are orthonormal sets. Sigma is going to
be a diagonal matrix with non-negative entries. OK, good. So now, how do we find
this decomposition? Well, we need two equations, OK? One is C transpose C is equal
to V, sigma transpose, sigma, V transpose. And you get this just by
plugging in C transpose C here and noticing that U
transpose U is 1, since U is an orthogonal matrix. Okay. And the second equation is just
noticing that V transpose is V inverse, and moving it to the
other side of the equation, which is C*V equals U*sigma. OK, so these are
the two equations we need to use to find
V, sigma, and U. OK, so let’s start
with the first one. Let’s compute C transpose
C. So C transpose C is that– Well, if
you compute, we’ll get a 26, an 18, an
18, and a 74, great. Now, what you notice
about this equation is this is just a
diagonalization of C transpose C. So we need to find
the eigenvalues– those will be the entries
of sigma transpose sigma– and the
eigenvectors which will be the columns of a V. Okay, good. So how do we find those? Well, we look at the determinant
of C transpose C minus lambda times the identity,
which is the determinant of 26 minus lambda, 18, 18,
and 74– 74 minus lambda, thank you. Good, OK, and what
is that polynomial? Well, we get a lambda squared,
now the 26 plus 74 is 100, so minus 100*lambda. And I’ll let you do 26 times 74
minus 18 squared on your own, but you’ll see you get 1,600,
and this easily factors as lambda minus 20
times lambda minus 80. So the eigenvalues
are 20 and 80. Now what are the eigenvectors? Well, you take C transpose C
minus 20 times the identity, and you get 6, 18, 18 and 54. To find the eigenvector
with eigenvalue 20, we need to find a vector in
the null space of this matrix. Note that the second
column is three times the first column, so our
first vector, v_1, we can just take that to be, well, we
could take it to be [-3, 1], but we’d like it to be
a unit vector, right? Remember the columns of
v should be unit vectors because they’re orthonormal. So 3 squared plus
1 squared is 10, we have to divide by
the square root of 10. OK, similarly, we do C transpose
C minus 80 times the identity, we’ll get -54, 18; 18,
and -6, and similarly we can find that v_2 will
be 1 over square root of 10, 3 over the square root of 10. Great, OK, so what
information do we have now? we have our V matrix, which
is just made up of these two columns, and we actually
have our sigma matrix too, because the squares of the
diagonal entries of sigma are 20 and 80. Good, so let’s write those
down, write down what we have. So we have V– I just
add these vectors and make them the
columns of my matrix. Square root of 10, 1
over square root of 10; 1 over square root of 10,
3 over square root of 10. And sigma, this is just the
square roots of 20 and 80, which is just 2 root 5 and
4 root 5 along the diagonal. Squeezing it in here, I hope
you all can see these two. Good, so these are two of the
three parts of my singular value decomposition. The last thing I
need to find is u, and for that I need to use this
second equation right here. So you need to multiply
C times V, okay so So c is [5, 5; -1, 7],
let’s multiply it by V, 1 over root 10, 3 over
square root of 10. What do we get? Well, I’ll let you
work out the details, but it’s not hard here. You get -10 over root 10, which
is just negative square root of 10 here. Then I just get 2 square
root of 10, and then I get– 1 is 2 square root of 10 and– I think I made an error here. Give me a second to look
through my computation again. AUDIENCE: [INAUDIBLE] PROFESSOR: The (2, 1) entry
should be– oh, yes, thank you. The (2, 1) entry should
be the square root of 10. Good, yes, that’s what I was
hoping, yes, because we get– Yes, I did it in
the wrong order, right, so your recitation
instructor should know how to multiply matrices,
great, yes, thank you. You multiply this first, then
this, then this, and then this, and if you do it correctly
you will get this matrix here. Good, great. So now I’d like this
to be my U matrix, but it’s actually U times sigma,
so I need to make these entries unit length. OK, so I get -1 over root 2, 1
over root 2, 1 over root 2, 1 over root 2, times
my sigma matrix here, which is, remember,
2 square root of 5, 4 square root of 5,
and these constants are just what I needed to
divide these columns by in order to make them unit vectors. So now, here’s my U matrix,
1 over square root of 2, -1 over square root of 2;
1 over square root of 2, 1 over square root of 2, good. So now I have all three
matrices, U, V, and sigma and despite some little
errors here and there, I think this is actually right. You should go check it
yourself, because if you’re at all like me, you’ve screwed
up several times by now. But anyway, this is
a good illustration of how to find the singular
value decomposition. Recall that you’re
looking for U sigma V transpose where u and v
are orthogonal matrices, and sigma is diagonal
with non-negative entries. And you find it using
these two equations, you compute C transpose C,
that’s V sigma transpose sigma times V transpose, and you
also have C*V is U*sigma. I hope this was a
helpful illustration.

100 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *