Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Singular value decomposition

by , PhD

The singular value decomposition (SVD) of a matrix allows us to decompose any (not necessarily square) matrix into a product of three terms:

  1. a unitary matrix;

  2. a matrix having positive entries on its main diagonal and zero entries elsewhere;

  3. another unitary matrix.

Easily recognizable subsets of the columns of the two unitary matrices involved in the decomposition have the remarkable property of being orthonormal bases for the column space and the null space of the original matrix.

The singular value decomposition is derived by using results about the diagonalization of a positive definite matrix. We therefore recommend to revise the lecture on positive definite matrices before reading this one.

Table of Contents

The decomposition

Here is the decomposition.

Proposition Let A be a $K imes L$ matrix. Then, there exist a $K imes K$ unitary matrix $U$ and an $L imes L$ unitary matrix V such that[eq1]where $V^{ast }$ denotes the conjugate transpose of V, Sigma is a $K imes L$ matrix such that $Sigma _{ij}geq 0$ if $i=j$ and $Sigma _{ij}=0$ if $i eq j$.

Proof

We start by observing that the matrix[eq2]is Hermitian (i.e., equal to its conjugate transpose), hence normal and unitarily diagonalizable (i.e., unitarily similar to a diagonal matrix). Moreover, for any $L imes 1$ vector x, we have [eq3]As a consequence $A^{ast }A$ is positive semi-definite, which implies that its eigenvalues are real non-negative numbers. Thus, we can diagonalize $A^{st }A$ as [eq4]where V is a unitary matrix and $D$ is a diagonal matrix such that its diagonal entries are real non-negative numbers. When we diagonalize a matrix, we can arbitrarily choose the order in which the eigenvalues appear on the diagonal of $D$. Therefore, we can perform the diagonalization in such a manner that[eq5]where the block $D_{1}$ is a diagonal matrix having all the strictly positive eigenvalues of $A^{ast }A$ on its main diagonal. Suppose that there are $r$ strictly positive eigenvalues, that is, $D_{1}$ is $r imes r$. Partition V into two blocks:[eq6]where $V_{1}$ is $L imes r$. By using the rules for the multiplication of block matrices, we obtain[eq7]Note that[eq8]and the last equation implies[eq9]As a consequence, the squared norms of the columns of $AV_{2}$ (which are on the main diagonal of the matrix on the left-hand side of the equation) are all zero. Hence, [eq10]by the positive definiteness of the norm. Define the $K imes r$ matrix[eq11]where $D_{1}^{1/2}$ is a diagonal matrix whose diagonal entries are equal to the square roots of the diagonal entries of $D_{1}$. Note that [eq12]so that the columns of $U_{1}$ are orthonormal. Find any [eq13] matrix $U_{2}$ having orthonormal columns and such that[eq14]In other words, the columns of $U_{2}$ are chosen so as to "complete the orthonormal basis", that is, so as to form an orthonormal basis together with the columns of $U_{1}$. Stated differently, the columns of $U_{2}$ span the orthogonal complement of the span of the columns of $U_{1}$. Define[eq15]Thus, $U$ is a unitary matrix. Then,[eq16]By pre-multiplying both sides by $U$ and post-multiplying both sides by $V^{ast }$, we obtain[eq17]

The diagonal entries of Sigma (i.e., the entries $Sigma _{ii}$ for [eq18]) are called singular values of A.

Example If[eq19]then the singular values are $2$, $5$ and 1.

Example Let[eq20]Then, the singular values are 1, 1 and 0.

Example If[eq21]then the singular values are $4$, $4$ and $3$.

Uniqueness

As shown in the proof above, the singular value decomposition of A is obtained from the diagonalization of $A^{ast }A$. But the diagonalization is not unique (as discussed in the lecture on diagonalization). Therefore, also the SVD is not unique.

Compact SVD

A more compact form of the SVD, called compact SVD, can be obtained as follows.

Proposition Let A be a $K imes L$ matrix. Let $r$ be the rank of A. Then, there exist a $K imes r$ matrix $U_{1}$ and an $L imes r$ matrix $V_{1}$, both having orthonormal columns, such that[eq22]where $V_{1}^{ast }$ denotes the conjugate transpose of $V_{1}$ and $Sigma _{1}$ is an $r imes r$ diagonal matrix with strictly positive entries on its main diagonal.

Proof

In this proof we use all the matrices defined in the above proof of the non-compact SVD. Note that $r$ (i.e., the number of non-zero singular values) is the rank of $D$ and, as a consequence, also the rank of A (because multiplication by the full-rank matrices $U$ and $V^{ast }$ does not change the rank of Sigma). We have [eq23]where we have defined [eq24].

The real case

If the matrix A is real (i.e., all its entries are real numbers), then the SVD is[eq25]where $U$ and V are real orthogonal matrices (we just need to replace conjugate transposition with simple transposition in the proof of the SVD).

Column space

Let A be a $K imes L$ matrix and let $S$ be the space of all $L imes 1$ column vectors.

Remember that the column space [eq26] is the span of the columns of A:[eq27]

Proposition Let A be a $K imes L$ matrix. Let $r$ be the rank of A. Let[eq28]be an SVD of A such that the $r$ non-negative singular values of A are the first $r$ entries on the main diagonal of Sigma. Let $U_{1}$ be the block formed by the first $r$ columns of $U$. Then,[eq29]where [eq30] is the span of the columns of A and [eq31] is the span of the columns of $U_{1}$.

Proof

The proof of this proposition is in Solved Exercise 1 below.

Note that $U_{1}$ is the matrix appearing in the compact SVD above.

Since the columns of $U_{1}$ are orthonormal, they are also linearly independent. Thus, the matrix $U_{1}$ in the compact SVD exposes an orthonormal basis for the column space of A.

Null space

Remember that the null space [eq32] is the kernel of the linear transformation defined by A:[eq33]

Proposition Let A be a $K imes L$ matrix. Let $r$ be the rank of A. Let[eq28]be an SVD of A such that the $r$ non-negative singular values of A are the first $r$ entries on the main diagonal of Sigma. Let $V_{2}$ be the block formed by the last $L-r$ columns of V. Then,[eq35]where [eq36] is the null space of A and [eq37] is the span of the columns of $V_{2}$.

Proof

The proof of this proposition is in Solved Exercise 2 below.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Prove the above proposition about the column space of A.

Solution

Suppose that [eq38]. Then, there exists an $L imes 1$ vector $s$ such that[eq39]where we have used the compact SVD of A. Thus, [eq40] and[eq41]where [eq42] is the span of the columns of $U_{1}$ (i.e., the column space of $U_{1}$). Now, suppose that [eq43]. Then, there exists an $r imes 1$ vector $s_{r}$ such that[eq44]where again we have used the compact SVD of A. Hence, [eq45] and [eq46]But (1) and (2) imply[eq47]

Exercise 2

Prove the above proposition about the null space of A.

Solution

Suppose that [eq48]. The columns of $V_{1}$ and those of $V_{2}$ together form a basis for the space of $L imes 1$ vectors. As a consequence, there exist an $r imes 1$ vector $s_{1}$ and an [eq49] vector $s_{2}$ such that[eq50]We can write the equation as[eq51]By pre-multiplying both sides of the equation by A, we obtain[eq52]because [eq53] and $AV_{2}=0$, as previously demonstrated. But [eq54]Thus, we have[eq55]Since $U_{1}$ and $Sigma _{1}$ are both full-rank, the last equation implies[eq56]which in turn implies[eq57]Thus, [eq58]. We have just demonstrated that[eq59]Now, suppose that [eq58]. Hence, there exists a [eq61] vector $s_{2}$ such that [eq57]By pre-multiplying both sides of the equation by A, we get[eq63]which implies that [eq53]. Thus,[eq65]But (1) and (2) imply[eq66]

How to cite

Please cite as:

Taboga, Marco (2021). "Singular value decomposition", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/singular-value-decomposition.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.