Single Value Decomposition

1. Definite Matrices

Let and . We say:

• is positive semi-definite iff . This means all its eigenvalues are non-negative.
• is positive definite iff . This means all its eigenvalues are strictly positive.

For any arbitrary matrix , the matrices and are always symmetric and positive semi-definite.

2. Singular Value Decomposition

The Singular Value Decomposition (SVD) of is the decomposition of into the 3 matrices , where is orthogonal, is orthogonal, and is diagonal with and . These are the sigular values of .

If is the rank of then has positive singular values and singular values equal to .

Then, if and , we have .

Let , where :

• , is orthogonal, .
• , is orthogonal, .
• , where , , , and .

2.1 Construction of SVD

1. Suppose the SVD for as above exists.
2. .
3. Hence where .
4. is a diagonal matrix, thus giving the spectral composition of the positive semi-definite matrix .
5. Hence is the matrix of orthonormal eigenvectors of , and are the eigenvalues of .
6. As , . Thus, for .
7. Hence, can be found using gram-schmidt between and .

(!) Example

Let .

1. We will work with because it is smaller.
2. . Now, we must find the spectral decomposition of this matrix.
3. . So, .
4. We can find the singular values . and .
5. The first eigenvector of : . So .
6. The second eigenvector of : . So .
7. Since , . So . This only works up until .
8. Now, we must find where and .
9. We can easily pick an orthogonal as .
10. can be found with a cross product, .

2.2 Properties of SVD

• The singular values of are . .
• . Since the first term here is most important, we can approximate .

3. Principal Component Analysis

If is the SVD of , then the columns of , are the principal axes of . The first principal axis is , the second is , and so on.

The principle components of are the columns of . The first principle component is , the second is , and so on.

If , then the data contained in can be compressed by projecting in the direction of the principle component: .

This is called data compression, principle component analysis and is an example of a dimensionality reduction algorithm.