Simple Explanation of Singular Value Decomposition with Examples
Looking back over the notes of my Computation Techniques course I realized that it wasn’t fully clear to me how to get the singular value decomposition of a matrix. Nor was the mathematical reasoning behind it very clear or intuitive. After a quick look online I realized most of the available resources were equally unhelpful in providing a strong understanding of singular value decomposition.
If you are reading this, there is a good chance that you too are also looking to properly understand singular value decomposition. My hope is that, after reading this, the math behind singular value decomposition will become abundantly clear and will allow you to remember how to get the singular value decomposition of a matrix without having to memorize anything.
If you learn better from example, feel free to skip straight to the examples. I have made it so that the example is detailed enough that you might be able to understand the math behind everything without reading any of the theory. But obviously, feel free to read the theory if anything is unclear or even comment below.
The Theory
Let C be the matrix we want to find the singular value decomposition of.
What we want to end up with is a way to write C as the products of three matrices — a rectangular diagonal matrix with non-negative real numbers on the diagonal, which is multiplied by an orthogonal matrix on each side.
What We Want
Put simply, we want to find the matrices U, Σ, and V such that
Where Σ is a rectangular diagonal matrix of same dimensions as C and U and V are orthogonal matrices (this will come in useful in a bit).
Key Insight
The key insight of singular value decomposition comes from two equations.
Before we give these two equations, let me remind you that U and V are orthogonal matrices which means that we have UᵀU = UUᵀ = I and similarly for V. This means that Vᵀ is the inverse of V so we have V⁻ ¹=Vᵀ
Now let us give the two key equations to singular value decomposition:
From these two equations, we will be able to derive Σ, V, and U.
Finding Σ and V
If you have done a bit a linear algebra before, you might be able to see that the first equation is essentially a matrix diagonalization problem (A = SDS⁻¹), where A=CᵀC, S = V, and D=ΣᵀΣ.
You might also remember that solving this problem involves finding the eigenvalues and respective eigenvectors of the matrix CᵀC. Once you have those, we can construct V to be the matrix composed of the eigenvectors of CᵀC, and ΣᵀΣ to be the diagonal matrix constructed from the corresponding eigenvalues.
So what we want to do is find the eigenvalues λ₁, λ₂, … λn of CᵀC and their corresponding normalized eigenvectors, respectively, v₁, v₂, … vn. Which allows us to get V and ΣᵀΣ, as shown below. It is important for the eigenvectors to be normalized as V should be an orthogonal matrix.
That’s all and good, but we want Σ, not ΣᵀΣ. That’s ok — we can deduce Σ from ΣᵀΣ. We know that knowing that Σ is a rectangular diagonal matrix. You should be able to convince yourself that because Σ is a rectangular diagonal matrix with diagonal elements σ₁, σ₂, … σn, that we have the following:
We can now clearly see that σ₁² = λ₁, σ₂² = λ₂, … σn² = λn. This means that
where Σii represents the ith element on the diagonal of Σ.
Finding U
Now that we have both Σ and V, we can find U using the second equation.
Since Σ is a rectangular diagonal matrix you should be able to convince yourself that the equation below follows from the equation above. Writing out an example rectangular diagonal matrix Σ and matrix U, and working out UΣ might help you convince yourself that the following is true.
This means that the jth column of U is simple the jth column of CV divided by the jth diagonal element of Σ.
So now we can construct fully construct U knowing both C and V.
Putting it All Together
And that’s it. Now that we have U, V, and Σ we can simply put it all together to get UΣVᵀ which is the singular value decomposition of C.
Here is a recap of what to do to get the singular value decomposition of a matrix C:
- Find the eigenvalues of CᵀC and their respective normalized eigenvectors.
- Let V = [ v₁, v₂, … vn ], and Σ = [ σ₁, σ₂, … σn ] where σ is the square root of λ.
- Let U = [ cv₁/σ₁, cv₂/σ₂, … cvn/σn] where cvn is the nth column of CV.
- Double check that C = UΣVᵀ.
Hopefully, you now understand why these steps make sense in finding the singular value decomposition of a matrix from the explanations above. Feel free to leave any comments below with any questions and try out the examples below.
Convenient Trick
If the matrix C you want to find the singular value decomposition of is an m×n matrix where m<n. Then CᵀC will be an n×n matrix whereas CCᵀ will be an m×m matrix which is smaller and more convenient to work with.
If you have properly understood what has been explained above, you should be able to see that we can use similar tricks to figure out U, Σ, and V using CCᵀ instead of CᵀC.
In particular, we get the following equations:
And again the first equation is just a matrix diagonalization problem, where ΣΣᵀ is the diagonal matrix with the normalized eigenvalues of CCᵀ on its diagonal and U is an orthogonal matrix with the respective eigenvectors for its columns.
We can find Σ from ΣΣᵀ in the same way as previously. With Σ being an m×n rectangular diagonal matrix with the square roots of the previously found eigenvalues as the diagonal elements.
We can now also Vᵀ using the second equation in the same way as previously done.
And there you go, you now have the singular value decomposition of C which you got with slightly less effort.
Examples
Simple Detailed Example
Let’s try and find the singular value decomposition of
Slightly More Complex Example
Using the Trick
Let’s now try and find the singular value decomposition of the following matrix:
Here C is an m×n where m < n so it would be more convenient to work with CCᵀ instead of with CᵀC. So let’s do that!
Video Recommendation
I recommend watching this video https://www.youtube.com/watch?v=cOUTpqlX-Xs by MIT OpenCourseWare on YouTube of another well-explained example of linear decomposition.
Website Recommendation
This is a great website for you to practice and check your singular value decomposition abilities: http://atozmath.com/MatrixEv.aspx?q=svd
