The singular value decomposition

In this article, I will prove that every matrix has a singular value decomposition. The singular value decomposition has numerous applications. It can be used to compute the pseudoinverse of a matrix, to perform principal component analysis, and it can be used to approximate a matrix by a low-rank approximation .

Theorem: Any matrix of rank has a decomposition

where and are semi-unitary matrices, and is a diagonal matrix with positive elements on the diagonal.

Proof: If , we can look at the singular value decomposition of the conjugate transpose of . Using , we find the singular value decomposition of . So we can assume without loss of generality.

Now consider the matrix , which is Hermitian. Using the spectral theorem for Hermitian matrices, we have

where is a unitary matrix with orthonormal eigenvectors of , and is a diagonal matrix, where the th element on the diagonal is the eigenvalue of . According to the first lemma, all the are nonnegative.

We can assume that . If this is not the case, we can simply permute the columns of and so that this condition holds. Since all the eigenvectors are orthogonal, and the rank of is by the second lemma, the eigenvalues are positive, and are zero.

Now define

for

Let be the matrix with , let be the matrix with as columns, and let be the diagonal matrix with on the diagonal.

For , we have that . So . On the other hand, if , we have , so . It follows that for . Since the vectors are orthonormal, they form a basis basis of . By linearity, it follows that for any . So we must have

It remains to show that is a diagonal matrix with positive diagonal elements, and that and are semi-unitary. The first fact is obvious since we have defined to have the values on the diagonal.

To show that is semi-unitary we need to show that . Consider that the elements are given by for . This expression reduces to 1 if and to 0 otherwise (by the orthogonality of the vectors . So , which means that is semi-unitary.

is an matrix with orthonormal columns. It follows that , so is semi-unitary.

Lemma: has only real, nonnegative eigenvalues.

Proof: Let be any eigenvector of and be the corresponding eigenvalue, so that . We have . Rearranging for , we get , which is obviously real and nonnegative.

Lemma: Let be the rank of a complex matrix . Then has rank as well.

Proof: For a matrix we have , so it suffices to show that , since this implies that the null spaces are the same.

From it follows that . It is a property of the norm that implies . So implies .

The theorem proves the existence of a variant of the singular value decomposition that is also known as the compact singular value decomposition. The existence of the 'full' singular value decomposition and other variants follows from the existence of the compact singular value decomposition, since we can just add extra zeroes to the diagonal, and add more orthonormal columns to and , without changing the product .