This morning, I had just taken a Linear Algebra test. In the post-mortem
discussion of the test, realized that Singular Value Decomposition had most
likely been the most missed topic. The previous evening, I was quite confused on
the topic, though it was through several Youtube videos and quite a bit of
lecture notes that I was able to realize the simple algorithm for computing
singular value decomposition. Interestingly enough, not many of them covered the
method that I'm about to write about.
As usual, explanations often make the most sense with an example, so I will
provide one below. Note that this is the same example as
this MIT OCW Example, just in case you want to
Since this is mainly about the solving process,
a fairly detailed explanation on what the matrix is being decomposed to.
If you are not yet familiar with solving for eigenvectors, eigenvalues, and
such, I would recommend checking out the following resources:
The method that is about to be presented is fairly algorithmic, and involves
solving for the eigenvalues and eigenvectors of two special matrices and
. One unique property to note is that the eigenvalues of and
remain the same; we only need to solve for the eigenvalues once, thus making
computation much faster. The steps are as follows:
- Find the eigenvalues of either or
- Using the eigenvalues determined, find the eigenvectors of and .
- Normalize the both of the eigenvectors determined in the previous step -
making sure to put them into matrices and respectively. (Note that
there exists a shortcut in the form for finding the 's
that may be used as well).
- Place the -th eigenvalue into for each eigenvalue.
- Make sure that the -th eigenvector in matrix and correspond to the
-th eigenvector in . If not, rearrange them.
- Done, you can put the matrices in the form .
Find the Singular Value Decomposition of .
The key to finding the SVD is through the eigenvalues and eigenvectors of
and . In fact, these two matrices correspond to and respectively,
although they must be normalized first. What's even nicer is that you only have
to solve for the eigenvalues once; the eigenvalues of are the same as
. Since both and are guranteed to be
definite symmetric matrices,
I usually chose to solve for the one with lower dimension.
We can then solve for the eigenvalues and eigenvectors respectively using
standard methods. Recall that this equates to solving
In this example, and . The eigenvectors then are
respectively. If we normalize these two vectors, then we get
Next, we calculate
Recall that since the nonzero eigenvalues are the same for both and
, we can skip the calculation of those and directly find the eigenvectors
The eigenvector matrix of then, is equivalent to the nullspaces of
The eigenvector matrix of then, is
which again corresponds to the eigenvalues
Afterwards, this gets gets normalized to
That's it! All that's left are the 's, which we happen to have already
solved for, since . Since all our eigenvalues are
positive (and will always be positive), it's very easy to take the square root
Remember that it's important to "line-up" the values of with the
appropriate eigenvectors such that the -th column of and correspond
to . In my calculations, this has already been kept track of, so we
All that's left now is to plug them into our initial equation, where we get
We can verify our answer as correct using
Wolfram Alpha's SVD tool
as well as
expanding it directly.
Recall that for step 3, we can use the shortcut to calculate
our values of . Let's see if this works.
so using our shortcut, we get the following expansions:
which produces the matrix
which also produces another valid SVD of
We can verify this through
as well as noting that the columns of are orthonormal to each other.