We've seen that any $\large m\times n$ matrix can be factored into a Singular Value Decomposition (SVD):

$$\large \begin{split} A &= U\Sigma V^T \\ &= \sum_{i=1}^{r}\sigma_i\vec{u}_i\vec{v}_i^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 \\ \end{split} $$

The pieces and facts of the SVD we discussed in the previous lesson are summarized here:

• $\large \sigma_i$ are the singular values of $\large A$; $\large \sigma_i=\sqrt{\lambda_i}$ where $\large \lambda_i$ are the eigenvalues of $\large A^TA$. These are all nonnegative. We rank them from largest $\large \sigma_1$ to smallest $\large \sigma_r$.
• $\large r$ is the number of positive singular values. It is also the rank of A, the number of linearly independent rows or columns of $\large A$, a measure of how much information in $\large A$ is not redundant.
• $\large U$ and $\large V$ are orthogonal matrices (the columns form an orthonormal set of vectors, $\large U^TU=I$).
• $\large \Sigma$ is a matrix with the singular values along the diagonal. It has $\large m-r$ rows of zeros at the bottom and $\large n-r$ columns of zeros on the right.
• $\large \vec{u}_i\vec{v}_i^T$ is an $\large m\times n$ matrix with rank 1.
• $\large A$ and $\large \Sigma$ are both $\large m\times n$.
• The $\large \sigma_i$ are the rectangular analogue of eigenvalues. The SVD is more general version of the orthogonal diagonalization we can do for a symmetric matrix.

Let's look more closely at the following form of the SVD:

$$\large A=\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 $$

On the left, we have a rank $\large r$ matrix $\large A$. On the right, we have the sum of $\large r$ rank 1 matrices, arranged in an order from largest coefficient $\large \sigma_1$ to smallest coefficient $\large \sigma_r$.

Here's the fact that will make the SVD useful for us:

Theorem: The best rank $\large k$ approximation to $\large A$ is $\large \displaystyle \sum_{i=1}^k \sigma_i\vec{u}_i\vec{v}_i^T$.

• $\large \sigma_1\vec{u}_1\vec{v}_1^T$ is the best possible rank 1 approximation to $\large A$.
• $\large \sigma_1\vec{u}_1\vec{v}_1^T+\sigma_2\vec{u}_2\vec{v}_2^T$ is the best possible rank 2 approximation to $\large A$.

This is about dimension reduction in our data. Our dataset, $\large A$, is large, but we can approximate it well with a lower rank dataset. The SVD gives us a way to keep the most important data (or the most important directions for our data).

The following image is a matrix of size $\large 1192\times 1253$.

The maximum rank of such a matrix is 1192 (why is that?). The rank of this particular matrix is indeed 1192 (this makes sense, it's unlikely that any of the columns in an image are linearly dependent).

Let's approximate $\large A$ in the following way:

$$\large A\approx\sigma_1\vec{u}_1\vec{v}_1^T+\sigma_2\vec{u}_2\vec{v}_2^T+\dots+\sigma_k\vec{u}_k\vec{v}_k^T$$

Let's use our approximation with various values for $\large k$ and see the results:

It works pretty well! This will work best on images where the $\large \sigma_i$ get small quickly. Here's a plot of the singular values for our image:

We see a sharp drop until around rank 150, giving us confidence that a rank 200 approximation will capture the image well. And we see that it does!

Little, random fluctuations in data are called noise. Noisy data can obscure what we actually want to evaluate. The SVD can be used for noise reduction. The idea is that noise consists of small details that will get lost if we keep only the most significant features captured by the large singular values.

Here's a surface with some noisy data:

If we look at the singular values for the plotted data, we see that they drop sharply after just a few values:

In other words, a low rank approximation of our data should capture most of the structure. Here's the low rank approximation if we take just 3 singular values (so, a rank 3 approximation):

A natural follow up to the SVD is a technique known as Principal Component Analysis (PCA). PCA is often the first step in data analysis. It uses the ideas of the SVD to identify the directions in the data that are responsible for the most variation in the data. This allows us to identify combinations of features that describe the data well (it's another form of dimension reduction). We do not have more room in MATH332 to include PCA! It's the next thing we'd include if we had more time. We wanted to highlight it, though, for any who would like to investigate on their own.

I can:

• Use the SVD to generate a low rank approximation to $\large A$.
• Interpret a low rank approximation.
• Use a plot of singular values to anticipate the necessary rank in a low rank approximation.