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
cross reference.
Since this is mainly about the solving process,
Wikipedia provides
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 AAT and
ATA. One unique property to note is that the eigenvalues of ATA and AAT
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 ATA or AAT
Using the eigenvalues determined, find the eigenvectors of ATA and AAT.
Normalize the both of the eigenvectors determined in the previous step -
making sure to put them into matrices U and V respectively. (Note that
there exists a shortcut in the form AVi=σiUi for finding the U's
that may be used as well).
Place the i-th eigenvalue into Σii for each eigenvalue.
Make sure that the i-th eigenvector in matrix U and V correspond to the
i-th eigenvector in Σ. If not, rearrange them.
Done, you can put the matrices in the form A=UΣVT.
Worked Example
Find the Singular Value Decomposition of A.
A=[5−157]
Standard Method
The key to finding the SVD is through the eigenvalues and eigenvectors of AAT
and ATA. In fact, these two matrices correspond to U and V 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 AAT are the same as
ATA. Since both ATA and AAT are guranteed to be
definite symmetric matrices,
I usually chose to solve for the one with lower dimension.
ATA=[26181874]
We can then solve for the eigenvalues and eigenvectors respectively using
standard methods. Recall that this equates to solving
det([26−λ181874−λ])=0
In this example, λ1=80 and λ2=20. The eigenvectors then are
[13] and [−31]
respectively. If we normalize these two vectors, then we get
V=[101103−103101]
Next, we calculate AAT
AAT=[50303050]
Recall that since the nonzero eigenvalues are the same for both ATA and
AAT, we can skip the calculation of those and directly find the eigenvectors
of AAT.
The eigenvector matrix of AAT then, is equivalent to the nullspaces of
[50−80303050−80]=[−303030−30]
and
[50−20303050−20]=[30303030]
The eigenvector matrix of AAT then, is
[11−11]
which again corresponds to the eigenvalues λ1=80,λ2=20
respectively.
Afterwards, this gets gets normalized to
U=[2121−2121]
That's it! All that's left are the σ's, which we happen to have already
solved for, since σi=λi. Since all our eigenvalues are
positive (and will always be positive), it's very easy to take the square root
of λi
Remember that it's important to "line-up" the values of σi with the
appropriate eigenvectors such that the i-th column of V and U correspond
to σi. In my calculations, this has already been kept track of, so we
find
Σ=[800020]=[450025]
All that's left now is to plug them into our initial equation, where we get