I. Introduction
Hello, everyone! How was your week? As we announced last week, in this post we will start talking about SVD. Are we done with recap on linear algebra? If not, read our last posting, especially, the parts on eigen value decomposition.
SVD is actually nothing very new. It is just some works done by fairy godmother on Eigen decomposition. 🌈 Eigen decomposition has its limit in that it can only be applied to symmetric matrix A.
SVD is just a little touch to eigen decomposition. From now on, matrix A is no longer a symmetric matrix. Rather, (mxn) matrix.
Although A is not a symmetric matrix, AᵀA and AAᵀ are symmetric (nxn and mxm). So why don’t we decompose AᵀA or AAᵀ first? Then our aim or hope is to retrieve A from the decomposed AᵀA and AAᵀ.
II. AAᵀ and AᵀA
With some simple hand writing calculation, we can derive some features of AAᵀ and AᵀA .
1. symmetric matrices
- both have orthogonal eigenvectors (from eigen decomposition)
with full set of eigenvalues that are real numbers.
2. Square mxm and nxn dimensions respectively.
3. At least positive semi definite
- Note that the components are summation of squares: components are at least larger or equal to zero
- resulting non-negative eigenvalues
4. rank of A=r and rank of AAᵀ and AᵀA=r.
4. AᵀA and AAᵀ share the same non-negative eigenvalues and their eigenvectors are very much related. More specifically they both have the same r number of non-negative eigenvalues; λ1,λ2,…λr.
- From simple polar decomposition, we have A=QS then,
- From the facts from similarity transformation we can conclude that AAᵀ(mxm) and AᵀA(nxn) have the same eigenvalues with highly related eigenvectors.
If you are confused with similarity transformation or polar decomposition consult our last posting.
I warn you that we are just using the facts from polar decomposition not actually proving it at this level.
4. From now on we will denote eigenvectors of AAᵀ as ui and AᵀA as vi. And the set of ui’s and vi’s will be denoted as u and v calling ‘Singular Vectors’.
This can be written
Also, since AAᵀ and AᵀA have orthogonal eigenvectors; UᵀU=I and VᵀV=I.
III. Singular Value Decomposition: A=USVᵀ
Now we are ready for SVD; A=USVᵀ.
We know U and V, but what is S?
S is square root of diagonal vector of eigenvalues, however, for the matrix multiplication to be satisfied S should have dimension of mxn.
Warning here, we have r number of eigenvalues, we will have rxr matrix where r is smaller or equal to m or n(whichever smaller). So, we will be putting zeros to make mxn matrix of S.
Also, we will order the eigenvalues so that
and we will be rewriting.
Then the singular value decomposition will be written in a matrix form like the following;
IV. Prove the equality of A=USVᵀ
Starting from A=USVᵀ, we are back with equations (1) and (2). Or, it can be rewritten as following.
For me, it seemed the proof is redundant to what we have been doing somewhat upside down.
However, what we are doing is to prove the equivalence by showing that from USVᵀ we can come back to A that satisfies its original features, while assuming A → USVᵀ remains and the features of U and V are maintained.
V. Change the format of SVD
Let’s see this component by component.
Then,
In generalization,
Or, we can see this equation according to A.
If this is confusing for you I recommend you write down all the components on a board or a note and do simple calculations. Once we invest some time although it seems stupid, we become confident and smart. 😁
So, this is basically all about SVD. In the next post, as usual, we will show how to do SVD in python with a codebook.
Thank you and stay tuned!
Have a pleasant day! ☃️
