Singular value decomposition, or SVD for short, is what many mathematicians agree to be the highlight of linear algebra. In this guide, we will go over the theory (including a rigorous proof 😺) behind this remarkable technique. In the next guide, we will apply SVD to perform data compression - trust me, the elegance of SVD will blow your mind 🤯.

Before we divide into the theory of SVD, let's first prove the following theorem that will be useful later.

Proof. By theoremlink, we know that $\boldsymbol{A}^T\boldsymbol{A}$ is symmetric. This means that the eigenvalues of $\boldsymbol{A}^T\boldsymbol{A}$ are all real by propertylink. Great, we're half done!

Let's now show that the eigenvalues of $\boldsymbol{A}^T\boldsymbol{A}$ are non-negative. Suppose $\lambda$ is an eigenvalue of $\boldsymbol{A}^T\boldsymbol{A}$ with an eigenvector of $\boldsymbol{v}$. By definitionlink of eigenvalues and eigenvectors, the following equation holds:

Now, the squared magnitude of $\boldsymbol{Av}$ can be expressed as:

Here:

• the 1st equality holds by theoremlink.

• the 2nd equality holds by propertylink of transpose.

• the 4th equality holds by substituting \eqref{eq:WgjFuYwXGMjRhEdgy66}.

• the last equality holds again by theoremlink.

Now, rearranging \eqref{eq:IoKMQwz3N3snBKWh1lF} to make $\lambda$ the subject gives:

Note the following:

• the numerator is non-negative because $\boldsymbol{Av}$ could equal the zero vector, in which case the numerator becomes zero and thus $\lambda=0$.

• the denominator cannot be zero because $\boldsymbol{v}\ne\boldsymbol{0}$ by definitionlink of eigenvector.

Therefore, we conclude that $\lambda\ge0$. This completes the proof.

Unlike other matrix decomposition techniques such as eigen-decompositionlink, QR and LU factorization, SVD works for matrices of any shape - not just for square matrices. The downside is that SVD is quite complicated and introduces new concepts such as singular values and singular matrices. Don't worry too much about them for now - we will go over them in the proof and also go through an example of actually computing them later!

Proof. Let $\boldsymbol{A}$ be an $m\times{n}$ matrix. By theoremlink, $\boldsymbol{A}^T\boldsymbol{A}$ is symmetric, which means that by the principal axis theoremlink, $\boldsymbol{A}^T\boldsymbol{A}$ can be orthogonally diagonalized as:

Where:

• $\boldsymbol{V}$ is an $n\times{n}$ orthogonal matrix whose column vectors are the eigenvectors $\boldsymbol{v}_1$, $\boldsymbol{v}_2$, $\cdots$, $\boldsymbol{v}_n$ of $\boldsymbol{A}^T\boldsymbol{A}$.

• $\boldsymbol{D}$ is an $n\times{n}$ diagonal matrix whose diagonal entries are the eigenvalues $\lambda_1$, $\lambda_2$, $\cdots$, $\lambda_n$ of $\boldsymbol{A}^T\boldsymbol{A}$. These eigenvalues are real and non-negative by propertylink.

Now, let's assign the variable names such that:

While the rest of the eigenvalues are zero:

For instance, suppose $\boldsymbol{A}^T\boldsymbol{A}$ has three eigenvalues $5$, $0$ and $8$. In this case, we will assign $\lambda_1=8$, $\lambda_2=5$ and $\lambda_3=0$, while the value of $r$ would be $2$.

Relationship between rank of matrix and eigenvalues

We will now show that the value of $r$ is equal to the ranklink of $\boldsymbol{A}$. Suppose $\lambda_i$ and $\lambda_j$ are eigenvalues of $\boldsymbol{A}$ with associated eigenvectors $\boldsymbol{v}_i$ and $\boldsymbol{v}_j$ respectively. By definitionlink of eigenvalues and eigenvectors, we have that:

Now, the dot product of $\boldsymbol{Av}_i$ and $\boldsymbol{Av}_j$ is:

Here:

• the 1st equality holds by propertylink.

• the 2nd equality holds by propertylink of matrix transpose.

• the 4th equality holds by \eqref{eq:KSjlGyJitkTnUxpHltU}.

We now consider two cases - when $i=j$ and $i\ne{j}$. When $i=j$, \eqref{eq:WnMilyxYTWTJFNMJXbk} becomes:

Here:

• the 2nd equality holds by theoremlink.

• the 3rd equality holds because $\boldsymbol{v}_i$ is a unit vector.

Since eigenvalues $\lambda_i=0$ for $i\gt{r}$ by \eqref{eq:RFQFFJxhYVO0VbmOC1k}, we have that \eqref{eq:i2OnmX79bDTac17OpXD} becomes:

To summarize, in the case when $i=j$, we have:

We now consider the case when $i\ne{j}$. Because $\{\boldsymbol{v}_1, \boldsymbol{v}_2,\cdots,\boldsymbol{v}_n\}$ is an orthonormal set, \eqref{eq:WnMilyxYTWTJFNMJXbk} becomes:

Because every pair of $\boldsymbol{Av}_i$ and $\boldsymbol{Av}_j$ where $i\ne{j}$ is perpendicular, we have the following:

Recall that $\{\boldsymbol{v}_1,\boldsymbol{v}_2, \cdots,\boldsymbol{v}_n\}$ is an orthogonal set and is therefore a basislink for $\mathbb{R}^n$. This means that we can express any vector $\boldsymbol{x}$ in $\mathbb{R}^n$ using a linear combination of these orthogonal vectors:

Where $c_1$, $c_2$, $\cdots$, $c_n$ are scalar coefficients. Multiplying both sides of \eqref{eq:tN3giIYOyd8F0yp5Gok} by $\boldsymbol{A}$ gives:

By \eqref{eq:FNbXxNbL1tZ4IR2PotZ}, we have that $\boldsymbol{Av}_i=\boldsymbol{0}$ for $i\gt{r}$. Therefore, \eqref{eq:ZGPPmu4lCwoPLgmCfiC} becomes:

This means that any vector generated by $\boldsymbol{Ax}$ can be expressed as a linear combination of the vectors $\boldsymbol{Av}_1$, $\boldsymbol{Av}_2$, $\cdots$, $\boldsymbol{Av}_r$. This means that $\{\boldsymbol{Av}_1, \boldsymbol{Av}_2, \cdots,\boldsymbol{Av}_r\}$ is a basis for the column spacelink of $\boldsymbol{A}$. Now, recall that the ranklink of $\boldsymbol{A}$ is defined as the dimensionlink of the column space of $\boldsymbol{A}$, that is, the number of basis vectors for the column space of $\boldsymbol{A}$. Since the column space of $\boldsymbol{A}$ has $r$ basis vectors, the rank of $\boldsymbol{A}$ is $\boldsymbol{r}$.

Let's now define the so-called singular values.

In our case, the singular values of $\boldsymbol{A}$ would also be:

Remember that the eigenvalues of $\boldsymbol{A}^T\boldsymbol{A}$ have been rearranged such that:

Since the function $f(x)=\sqrt{x}$ is monotonically increasing, taking the square root of the eigenvalues will not change the inequality \eqref{eq:JpNrPF3PbBF7Ofd8jEc}. This means that the singular values will have the following ordering:

Now, recall from \eqref{eq:P7Eg1JUr76KH2L9RVwJ} the following:

Taking the square root of both sides and making $\sqrt{\lambda_i}$ the subject gives:

Remember, $\lambda_i$ is non-negative so we are allowed to take its square root here. Using the definition of singular values \eqref{eq:Sjf1KMk4qGwHx7AgCU2}, we can write \eqref{eq:Cim4aRi3GxTLo9LVX9j} as:

By \eqref{eq:GpOVpGoLvwRm2xIK8Tm}, we have that $\sigma_i=0$ for $i\gt{r}$. Let's summarize our result:

We now define the so-called singular matrix.

Now, recall from \eqref{eq:Zb2WQDDVVHYSvKHRLXB} that $\{\boldsymbol{Av}_1,\boldsymbol{Av}_2,\cdots,\boldsymbol{Av}_r\}$ is an orthogonal setlink. We can convert each vector into a unit vector by methodlink to obtain the orthonormal setlink $\{\boldsymbol{u}_1,\boldsymbol{u}_2, \cdots,\boldsymbol{u}_r\}$ where:

We now extend this set by methodlink such that $\{\boldsymbol{u}_1,\boldsymbol{u}_2, \cdots,\boldsymbol{u}_r, \boldsymbol{u}_{r+1}, \cdots,\boldsymbol{u}_m\}$ becomes an orthonormal basislink for $\mathbb{R}^m$.

We now define an $m\times{m}$ orthogonal matrix $\boldsymbol{U}$ such that:

Recall from \eqref{eq:WpNcxedNGzx7R6RkhNn} that:

Multiplying both sides of the top equation by $\boldsymbol{u}_i$ gives:

Now, if we multiply both sides of \eqref{eq:a4Ekl1HkJcaSL9jGZ0y} by $\Vert\boldsymbol{Av}_i\Vert$, we get:

Substituting \eqref{eq:OVHV9f2yTu44jdbRKDW} into \eqref{eq:vmO3KfLfrAyzizbdMl7} and making $\boldsymbol{Av}_i$ the subject gives:

Recalling all the way back to \eqref{eq:P7Eg1JUr76KH2L9RVwJ}, we have that:

Let's summarize \eqref{eq:xEkZKEaLdhb7rzU4vqm} and \eqref{eq:B8RBJYWVYSEl3ljqapZ} as:

Now, using theoremlink and \eqref{eq:RvMbvxleHxW8j8jJnDL}, we can express the matrix product $\boldsymbol{AV}$ as:

By \eqref{eq:xEkZKEaLdhb7rzU4vqm} and \eqref{eq:B8RBJYWVYSEl3ljqapZ}, we can express the columns of $\boldsymbol{AV}$ as:

Now, consider the matrix product $\boldsymbol{U}\boldsymbol{\Sigma}$ where $\boldsymbol{\Sigma}$ is the singular matrixlink of $\boldsymbol{A}$ defined earlier:

Here, the second equality holds by a similar logic to that of the propertylink of diagonal matrices. Amazingly, \eqref{eq:eAtcXAwjLqeefFE3XXh} matches \eqref{eq:yq1WwOcMw0iWRvuVHFe}, which means:

By propertylink, since $\boldsymbol{V}$ is an orthogonal matrix, $\boldsymbol{V}$ is invertible and $\boldsymbol{V}^{-1}=\boldsymbol{V}^T$. Therefore, \eqref{eq:PgmN8RDyxJjeHavKhPb} becomes:

This completes the proof.

We typically wouldn't compute the SVD of a matrix by hand because of how tedious the calculations are. Instead, most numerical programming libraries offer a method to find the SVD of any matrix efficiently. Nonetheless, we will still demonstrate how to perform SVD by hand for learning purposes!

Solution. To find the singular value decomposition of $\boldsymbol{A}$, we must find three matrices $\boldsymbol{U}$, $\boldsymbol{\Sigma}$ and $\boldsymbol{V}$. We typically find these matrices in the following order:

1. $\boldsymbol{\Sigma}$ can be found by obtaining the eigenvalues of $\boldsymbol{A}^T\boldsymbol{A}$.

2. $\boldsymbol{V}$ can be found by obtaining the unit eigenvectors of $\boldsymbol{A}^T\boldsymbol{A}$.

3. $\boldsymbol{U}$ can be found by using the column vectors of $\boldsymbol{V}$.

Finding the singular values of A

Let's start by finding the singular valueslink of $\boldsymbol{A}$, which are equal to the square root of the eigenvalues of $\boldsymbol{A}^T\boldsymbol{A}$. Firstly, the matrix $\boldsymbol{A}^T\boldsymbol{A}$ is:

The characteristic polynomiallink of $\boldsymbol{A}^T\boldsymbol{A}$ is:

Therefore, the eigenvalues of $\boldsymbol{A}^T\boldsymbol{A}$ are $\lambda_1=3$ and $\lambda_2=1$. Note that singular value decomposition requires that we assign the larger eigenvalue for $\lambda_1$, so setting $\lambda_1=1$ and $\lambda_2=3$ will be incorrect here.

The singular values of $\boldsymbol{A}$ are therefore:

Finding the singular matrix of A

With the singular values computed, we can now easily find the $3\times2$ singular matrixlink $\boldsymbol{\Sigma}$ of $\boldsymbol{A}$ like so:

Finding the orthogonal matrix V

The matrix $\boldsymbol{V}$ orthogonally diagonalizeslink $\boldsymbol{A}^T\boldsymbol{A}$, which means that the column vectors of $\boldsymbol{V}$ are the (unit) eigenvectors of $\boldsymbol{A}^T\boldsymbol{A}$. We've already found the eigenvalues of $\boldsymbol{A}^T\boldsymbol{A}$ - they are $\lambda_1=3$ and $\lambda_2=1$, so let's now find the corresponding eigenvectors!

For your reference, here's $\boldsymbol{A}^T\boldsymbol{A}$ again:

To get an eigenvector associated with $\lambda_1=3$, we solve the following:

Here, $v_{12}$ is a free variablelink so let $v_{12}=t$ where $t$ is any scalar. The first row then yields $v_{11}=t$. Therefore, an eigenvector corresponding to $\lambda_1=3$ can be expressed as:

For simplicity, we can let $t=1$. Since $\boldsymbol{V}$ is an orthogonal matrix whose columns are unit eigenvectors, we need to convert $\boldsymbol{v}_1$ into a unit vector:

We now need to repeat the same process for $\lambda_2=1$ by solving:

Here, $v_{22}$ is a free variablelink so let $v_{22}=t$ where $t$ is any scalar. The first row then yields $v_{21}=-t$. Therefore, an eigenvector associated with $\lambda_2=1$ can be expressed as:

Again, we can let $t=1$ for simplicity. We then convert $\boldsymbol{v}_2$ into a unit eigenvector:

Great, we've now managed to find $\boldsymbol{V}$ as below:

Finding the orthogonal matrix U

Let's now move on to finding the $3\times3$ orthogonal matrix $\boldsymbol{U}$. The first two column vectors $\boldsymbol{u}_1$ and $\boldsymbol{u}_2$ are computed by:

Where $\boldsymbol{v}_1$ and $\boldsymbol{v}_2$ are given by \eqref{eq:HapfPURNLkxYe31TtoQ} and \eqref{eq:f5YcLVz0suU2EaAtms4} respectively. Let's first work out $\boldsymbol{Av}_1$ and $\boldsymbol{Av}_2$ like so:

The magnitudes of $\boldsymbol{Av}_1$ and $\boldsymbol{Av}_2$ are:

We can now compute the unit column vectors $\boldsymbol{u}_1$ and $\boldsymbol{u}_2$ using \eqref{eq:Tle0jXlo6zq2thkLdtd} to get:

Remember, the theory of SVD guarantees that $\boldsymbol{u}_1$ and $\boldsymbol{u}_2$ are orthogonal.

We now must find a vector $\boldsymbol{u}_3$ that is orthogonal to both $\boldsymbol{u}_1$ and $\boldsymbol{u}_2$. Instead of using unit vectors, let's multiply $\boldsymbol{u}_1$ by $\sqrt6$ and $\boldsymbol{u}_2$ by $\sqrt2$ so that we can remove the fractions:

Note that multiplying vectors by scalars does not change their direction, so a vector that is orthogonal to these simplified vectors $\boldsymbol{u}'_1$ and $\boldsymbol{u}'_2$ will also be orthogonal to the original $\boldsymbol{u}_1$ and $\boldsymbol{u}_2$.

We can use methodlink to find a vector that is orthogonal to both $\boldsymbol{u}_1'$ and $\boldsymbol{u}_2'$. This involves solving the following homogeneous linear system:

Let's use Gaussian elimination to solve the system:

If we let $x_3=t$ where $t$ is any scalar, then:

• the second row gives us $x_2=-t$.

• the first row gives us $x_1=t$.

Therefore, the solution of the homogenous linear system can be expressed as:

For simplicity, let's pick $t=1$. Remember, this vector is orthogonal to $\boldsymbol{u}_1$ and $\boldsymbol{u}_2$. We convert this vector into a unit vector to obtain $\boldsymbol{u}_3$ like so:

We now have an orthonormal setlink $\{\boldsymbol{u}_1,\boldsymbol{u}_2,\boldsymbol{u}_3\}$ which forms the column vectors of orthogonal matrix $\boldsymbol{U}$, that is:

We now have all the factors $\boldsymbol{U}$, $\boldsymbol{\Sigma}$ and $\boldsymbol{V}$ as \eqref{eq:E7TMPcrLQZTZ4Gwvh4l}, \eqref{eq:UMDfNzrY9ipxYWqfkF4} and \eqref{eq:DKLgvGWs4ckCDnFExOi} respectively. The singular value decomposition of $\boldsymbol{A}$ is therefore:

We can verify that the decomposition is correct by explicitly multiplying the three matrices.