SVD Decomposition
We begin this section with an important definition.
Singular Value Decomposition (SVD) can be thought of as a generalization of orthogonal diagonalization of a symmetric matrix to an arbitrary matrix. This decomposition is the focus of this section.
The following is a useful result that will help when computing the SVD of matrices.
- Proof
- Suppose is an matrix, and suppose that is a nonzero eigenvalue of . Then
there exists a nonzero vector such that
Multiplying both sides of this equation by yields: Since and , , and thus by equation (nonzero), ; thus , implying that .
Therefore is an eigenvector of corresponding to eigenvalue . An analogous argument can be used to show that every nonzero eigenvalue of is an eigenvalue of , thus completing the proof.
Given an matrix , we will see how to express as a product where
- is an orthogonal matrix whose columns are eigenvectors of .
- is an orthogonal matrix whose columns are eigenvectors of .
- is an matrix whose only nonzero values lie on its main diagonal, and are the singular values of .
How can we find such a decomposition? We are aiming to decompose in the following form:
where is a block matrix of the form Thus and it follows that and so Similarly, Therefore, you would find an orthonormal basis of eigenvectors for make them the columns of a matrix such that the corresponding eigenvalues are decreasing. This gives You could then do the same for to get .We formalize this discussion in the following theorem.
- Proof
- There exists an orthonormal basis, such that where for and equals zero if Thus for because
For define by
Thus Now This means that when and when . Thus is an orthonormal set of vectors in Also, Now, using Gram-Schmidt, extend to an orthonormal basis for all of and let while Thus is the matrix which has the as columns and is defined as the matrix which has the as columns. Then where is given in the statement of the theorem.
The SVD has as an immediate corollary which is given in the following interesting result.
Let’s compute the SVD of a simple matrix.
Since is while is , and and have the same nonzero eigenvalues (by Lemma lem:samenonzeroeigenvalues), we compute the characteristic polynomial (because it is easier to compute than ).
The eigenvalues of are , , and , and the singular values of are and . By convention, we list the eigenvalues (and corresponding singular values) in non increasing order (i.e., from largest to smallest).
To find the matrix :
To construct the matrix we need to find eigenvectors for . Since the eigenvalues of are distinct, the corresponding eigenvectors are orthogonal, and we need only normalize them.
: solve .
: solve .
: solve . Let Then Also, and we use , , and to find . Since is orthogonal and , it follows that . Let , and let , where and are the two columns of . Then we have
Here is another example.
Thus has eigenvalue , and the eigenvalues of are , , and . Furthermore, has only one singular value, .
To find the matrix : To do so we find an eigenvector for and normalize it. In this case, finding a unit eigenvector is trivial: , and Also, , and we use , , and to find .
Now , with , and , where , , and are the columns of . Thus
The vectors and are eigenvectors of corresponding to the eigenvalue . Instead of solving the system and then using the Gram-Schmidt process on the resulting set of two basic eigenvectors, the following approach may be used.
Find vectors and by first extending to a basis of , then using the Gram-Schmidt algorithm to orthogonalize the basis, and finally normalizing the vectors.
Starting with instead of makes the arithmetic a bit easier. It is easy to verify that
is a basis of . Set
and apply the Gram-Schmidt algorithm to . This gives us
Therefore, and Finally,
Consider another example.
This illustrates that if you have a good way to find the eigenvectors and eigenvalues for a Hermitian matrix which has nonnegative eigenvalues, then you also have a good way to find the SVD of an arbitrary matrix.
Text Source
This section was adapted from Section 8.11 of Keith Nicholson’s Linear Algebra with Applications. (CC-BY-NC-SA)
W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition.