Introduction

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:

• MIT Eigenvalues and Eigenvectors
• MIT Lecture from Gilbert Strang
• A visualization by 3blue1brown

Method

The method that is about to be presented is fairly algorithmic, and involves solving for the eigenvalues and eigenvectors of two special matrices $AA^T$ and $A^TA$. One unique property to note is that the eigenvalues of $A^TA$ and $AA^T$ remain the same; we only need to solve for the eigenvalues once, thus making computation much faster. The steps are as follows:

1. Find the eigenvalues of either $A^TA$ or $AA^T$
2. Using the eigenvalues determined, find the eigenvectors of $A^TA$ and $AA^T$.
3. 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 $AV_i=\sigma_i U_i$ for finding the $U$'s that may be used as well).
4. Place the $i$-th eigenvalue into $\Sigma_{ii}$ for each eigenvalue.
5. Make sure that the $i$-th eigenvector in matrix $U$ and $V$ correspond to the $i$-th eigenvector in $\Sigma$. If not, rearrange them.
6. Done, you can put the matrices in the form $A = U\Sigma V^T$.

Worked Example

Find the Singular Value Decomposition of $A$.

Standard Method

The key to finding the SVD is through the eigenvalues and eigenvectors of $AA^T$ and $A^TA$. 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 $AA^T$ are the same as $A^TA$. Since both $A^TA$ and $AA^T$ 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, $\lambda_1 = 80$ and $\lambda_2=20$. The eigenvectors then are $\begin{bmatrix}1 \\ 3\end{bmatrix}$ and $\begin{bmatrix}-3\\1 \end{bmatrix}$ respectively. If we normalize these two vectors, then we get

Next, we calculate $AA^T$

Recall that since the nonzero eigenvalues are the same for both $A^TA$ and $AA^T$, we can skip the calculation of those and directly find the eigenvectors of $AA^T$.

The eigenvector matrix of $AA^T$ then, is equivalent to the nullspaces of

and

The eigenvector matrix of $AA^T$ then, is

which again corresponds to the eigenvalues $\lambda_1 = 80, \lambda_2 = 20$ respectively.

Afterwards, this gets gets normalized to

That's it! All that's left are the $\sigma$'s, which we happen to have already solved for, since $\sigma_i=\sqrt{\lambda_i}$. Since all our eigenvalues are positive (and will always be positive), it's very easy to take the square root of $\lambda_i$

Remember that it's important to "line-up" the values of $\sigma_i$ with the appropriate eigenvectors such that the $i$-th column of $V$ and $U$ correspond to $\sigma_i$. 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

or

We can verify our answer as correct using Wolfram Alpha's SVD tool as well as expanding it directly.

Shortcut Method

Recall that for step 3, we can use the shortcut $AV_i=\sigma_i U_i$ to calculate our values of $U$. 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

or

We can verify this through expansion as well as noting that the columns of $U$ are orthonormal to each other.