Singular Value Decomposition

We have a variety of recent ideas that are limited in scope (to square and/or symmetric matrices):

Eigenstuff for square matrices.
Diagonalization for square matrices.
Orthogonal diagonalization for symmetric matrices.

We can do quite a lot with these things, but the matrices we encounter in data are typically not square (let alone symmetric). That makes diagonalization limited in scope. We will see today the antidote: an analogue of eigenvalues and diagonalization that applies to any matrix!

Spectral Decomposition of $\large A$

In Lab 6, we learned about the Spectral Theorem for Symmetrix Matrices:

If $\large A$ is symmetric, then:

$\large A$ has only real eigenvalues.
The eigenvectors for different eigenvalues are orthogonal.
$\large A$ is orthogonally diagonalizable, meaning $\large A=PDP^T$ for an orthogonal matrix $\large P$. Remember that for an orthogonal matrix $\large P$, we have $\large PP^T=I$ and that the columns of an orthogonal matrix form an orthonormal set.

The orthogonal diagonalization of $\large A$ is here, where the $\large \vec{u}$ vectors are mutually orthonormal:

$$\large A=PDP^T, \quad P = \begin{bmatrix} \vdots & \vdots & \dots & \vdots \\ \vec{u}_1 & \vec{u}_2 & \dots & \vec{u}_n \\ \vdots & \vdots & \dots & \vdots \end{bmatrix}, \quad D = \begin{bmatrix} \lambda_1 & 0 & \dots & 0 \\ 0 & \lambda_2 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & \lambda_n \end{bmatrix}$$

With this factorization, we can break up A in a way called a spectral decomposition:

$$\large A = \lambda_1\vec{u}_1\vec{u}_1^T+\lambda_2\vec{u}_2\vec{u}_2^T+\dots+\lambda_n\vec{u}_n\vec{u}_n^T$$

Note

Since $\large \vec{u}$ is $\large n\times 1$, the product $\large \vec{u}\vec{u}^T$ is an $\large n\times n$ matrix (a symmetric one, at that).

Let's see an example of this. The video shows the spectral decomposition of the matrix:

$$\large A = \begin{bmatrix} 7 & 2 \\ 2 & 4\\ \end{bmatrix} $$

This decomposition breaks up $\large A$ according to its eigenvalues. The $\large\vec{u}\vec{u}^T$ matrices project any vector onto the eigendirection of the eigenvector $\large \vec{u}$. The $\large \lambda$'s are scaling factors that show how important each eigendirection is to the overall makeup of $\large A$.

Note

This decomposition is almost useful. If we could just do this for all matrices instead of only square, symmetric matrices, we'd make data science very happy.

The SVD

We have a problem: our decomposition (and eigenvalues/vectors in general) is not possible for general matrices. Data in particular rarely comes in square, symmetric matrices. What do we do? There is a matrix factorization called the Singular Value Decomposition (or SVD) which comes to the rescue.

Singular Values

Let $\large A$ be an $\large m\times n$ matrix. Since $\large A$ is not square, it has no eigenvalues or eigenvectors. Since it's not symmetric (only square matrices can be symmetric!), it has no orthogonal diagonalization.

But look at $\large A^TA$. This is an $\large n\times n$, symmetric matrix, so it is orthogonally diagonalizable. In other words, we can write:

$$\large A^TA=PDP^T$$

The columns of $\large P$ are an orthonormal basis of $\large \mathbb{R}^n$ consisting of the eigenvectors of $\large A^TA$, and $\large D$ is a diagonal matrix with the eigenvalues $\large \lambda_1, \lambda_2,\dots,\lambda_n$ of $\large A^TA$ along the diagonal.

Fact: The eigenvalues $\large \lambda_i$ are all nonnegative.

We can prove this, and it's clever and cool, so let's prove it in the video:

Definition: The singular values $\large \sigma_i$ of $\large A$ are the square roots of the eigenvalues of $\large A^TA$:

$$ \large \sigma_i=\sqrt{\lambda_i}$$

Let's see an example. Find the singular values of $\large A$:

$$\large A = \begin{bmatrix} 4 & 11 & 14\\ 8 & 7 & -2\\ \end{bmatrix} $$

The solution is in the video:

Note

We're just going to emphasize again that, unlike eigenvalues for square matrices, any matrix of any size has singular values!

The Singular Value Decomposition

With this background, we can state today's main result:

Theorem: If $\large A$ has $\large r$ singular values, then $\large \text{rank}(A)=r$, and $\large A = U\Sigma V^T$, where $\large U$ is an $\large m\times m$ orthogonal matrix, $\large \Sigma$ is a matrix that is mostly diagonal (padded with some rows and columns of zeros), and $\large V$ is an $\large n\times n$ orthogonal matrix. This factorization of $\large A$ is called the Singular Value Decomposition (SVD).

The matrix $\large \Sigma$ in the SVD has the form:

$$\large \Sigma = \begin{bmatrix} \sigma_1 & 0 & \dots & 0 & 0 & 0 \\ 0 & \sigma_2 & \dots & 0 & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & 0 & 0\\ 0 & 0 & \dots & \sigma_r & 0 & 0\\ 0 & 0 & \dots & 0 & 0 & 0\\ 0 & 0 & \dots & 0 & 0 & 0\\ 0 & 0 & \dots & 0 & 0 & 0\\ \end{bmatrix} $$

This is a diagonal matrix in the upper left (with the singular values in the diagonal) with rows and columns of zeros padded on the bottom and right. There are $\large m-r$ rows of 0's at the bottom and $\large n-r$ columns of 0's on the right.

Note

$\large A = U\Sigma V^T$ in sizes is: $\large (m\times n) = (m\times m)(m\times n)(n\times n)$. All we need to remember is that $\large A$ and $\large \Sigma$ are the same size, and then we can easily get the sizes for $\large U$ and $\large V$.

Definition: The columns of $\large U$ are called the left singular vectors of $\large A$. The columns of $\large V$ are called the right singular vectors of $\large A$. Since $\large U$ and $\large V$ are orthogonal matrices, the left/right singular vectors form orthonormal sets.

Important

The singular values and singular vectors of $\large A$ are the rectangular analogues of eigenvalues and eigenvectors for a square matrix, and the SVD is analogous to orthogonal diagonalization.

Computing the SVD

We will not outline the steps for computing the SVD by hand. They get messy, they are hard to remember, and they often involve Gram-Schmidt orthogonalization. Furthermore, we can only do it by hand for small matrices, but the real uses of the SVD are almost always for large matrices.

No one should be computing these by hand! Instead, we will use Python to compute SVDs. But we will show a completed example here. For the matrix we were working with earlier, the SVD is:

$$\large A = \begin{bmatrix} 4 & 11 & 14\\ 8 & 7 & -2\\ \end{bmatrix}=\begin{bmatrix} \frac{18}{\sqrt{360}} & \frac{3}{\sqrt{90}}\\ \frac{6}{\sqrt{360}} & -\frac{9}{\sqrt{90}}\\ \end{bmatrix}\begin{bmatrix} \sqrt{360} & 0 & 0\\ 0 & \sqrt{90} & 0 \\ \end{bmatrix}\begin{bmatrix} \frac{1}{3} & \frac{2}{3} & \frac{2}{3}\\ -\frac{2}{3} & -\frac{1}{3} & \frac{2}{3}\\ \frac{2}{3} & -\frac{2}{3} & \frac{1}{3}\\ \end{bmatrix} $$

Take a quick look at $\large U$ and $\large V$ in the example (remember, what we see above is not $\large V$, it's $\large V^T$). Verify that the columns are orthogonal to each other. Verify that they are unit vectors.
Take a quick look at $\large \Sigma$. We see the singular values we computed earlier. We see the extra column of 0's that is necessary to make $\large \Sigma$ the same size as $\large A$.
Note that $\large \text{rank}(A)=2$ since $\large A$ has two nonzero singular values.

Note

We learned to find the rank of a matrix at the very beginning of class, using Gaussian elimination. Turns out, when we use the built-in rank command in Python, it uses the SVD rather than Gaussian elimination!

Another form for the Decomposition

Recall from the beginning of this lesson that we can break a symmetric matrix down into its spectral decomposition. We now have something similar for rectangular and other non-symmetric matrices. The singular value decomposition of $\large A$ is:

$$\large A=\sum_{k=1}^{r}\sigma_k\vec{u}_k\vec{v}_k^T=\sigma_1\vec{u}_1\vec{v}_1^T+\sigma_2\vec{u}_2\vec{v}_2^T+\dots+\sigma_r\vec{u}_r\vec{v}_r^T$$

Here we break $\large A$ down into a sum of rank 1 matrices. In our next lesson, we will look at applications of the SVD, and we will focus on this form of the SVD.

Find the singular value decomposition for:

$$\large A = \begin{bmatrix} 4 & 11 & 14\\ 8 & 7 & -2\\ \end{bmatrix} $$

The solution is in the video:

Again, today we are just introducing this big new thing. Tomorrow, we will take a look at why this is so useful when dealing with data.

Section Outcomes

I can:

Find the spectral decomposition of a symmetric matrix.
Find the singular values of any matrix by finding the eigenvalues of $\large A^TA$.
Find the rank of a matrix using the singular values or the SVD.
Find the singular values of a matrix from the SVD.
From the SVD of $\large A$, write $\large A$ as a sum of rank 1 matrices.