This morning, I had just taken a Linear Algebra test, which in the post-mortem discussion of the test, realized that Singular Value Decomposition had most likely been the most missed topic. In fact, people even chose to skip questions that simply contained the wrongly-accursed words of "Singular Value Decomposition." The previous evening, I experienced a similar feeling, 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 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 and 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 of .
The eigenvector matrix of then, is equivalent to the nullspaces of
The eigenvector matrix of then, is
which again corresponds to the eigenvalues respectively.
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 of
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 find
All that's left now is to plug them into our initial equation, where we get
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 expansion as well as noting that the columns of are orthonormal to each other.