Announcements¶

• Homework:
  • Homework 8 due today, 4/14 at 8pm
  • Optional bonus homework out tonight, due next Friday
• Final exam: Monday, May 8 from 12-2pm
• Upcoming office hours:
  • Today: Peer tutor Daniel Cho from 12:30-3:30pm in CCDS 16th floor
  • Today: Abhishek Tiwari from 4-5pm on CCDS 13th floor
• Reading
  • Aggarwal Sections 7.1-7.4
  • Further reading: Deisenroth, Faisel, Ong Chapter 4.5

Lecture 32: Reduced SVD¶

[This lecture is based on Prof. Crovella's CS 132 and CS 506 lecture notes.]

Recap from last lecture¶

Last time, we began our investigation into singular value decomposition, the last and most powerful matrix factorization we will consider in this course.

SVD applies to any matrix $M$, no matter its size, (a)symmetry, invertibility, or diagonalizability.

Using SVD, we can "compress" a matrix of real-world messy data (exactly or approximately) into matrices of smaller dimension.

Geometrically, SVD says that the linear transformation corresponding to $M$ can be decomposed into a sequence of three steps.

1. Rotation within $R^n$, without scaling (i.e., rotating from the standard basis to another orthonormal basis).

2. Scaling each dimension $i$ by a constant ${\sigma }_i$, called a singular value.

   • If $m\ne n$, then the space is also transformed from $R^n$ to $R^m$ at the same time. Some dimensions might be projected away.
   • Some dimensions might also have such a small value of ${\sigma }_i$ that they might as well be projected away. That is, we might choose to remove them with little impact on the accuracy of the result.

3. Rotation within $R^m$.

   Note that this is not the inverse of step 1: the rotation might be by a different angle, across a different axis, and in a space of different dimension.

Algebraically, SVD is based on a very simple question:

Among all unit vectors, what is the vector $x$ that maximizes $\parallel Ax\parallel$?

In other words, in which direction does $A$ create the largest output vector from a unit input?

Unfortunately, the eigenvalues and eigenvectors of $A$ don't directly answer this question.

Eigenvectors have the property that they get mapped by $A$ to a scalar multiple of themselves. They don't get mapped to the farthest points on the ellipse.

The largest value of $\parallel Ax\parallel$ is the long axis of the ellipse. Clearly there is some $x$ that is mapped to that point by $A$. That $x$ is what we want to find.

Equivalently, we can maximize $$\parallel Ax{\parallel }^2=x^T\left(A^{T}A\right)x$$ Note that:

• $A^{\top }A$ is a symmmetric matrix.
• This is a quadratic form!
• Its maximum value, subject to the constraint that $\parallel x\parallel =1$, is the largest eigenvalue of $A^{\top }A$.

The eigenvector corresponding to the largest eigenvalue of $A^{T}A$ indeed shows us where $\parallel Ax\parallel$ is maximized -- where the ellipse is longest.

Also, the other eigenvector of $A^{T}A$ shows us where the ellipse is narrowest.

This matrix $A^{\top }A$ has many special properties, which help us in the singular value decomposition of $A$.

Definition. The singular values of $A$ are the square roots of the eigenvalues of $A^{\top }A$. They are denoted by ${\sigma }_1=\sqrt{{\lambda }_1}$, $\dots$, ${\sigma }_n=\sqrt{{\lambda }_n}$, and they are arranged in decreasing order ${\sigma }_1\ge {\sigma }_2\ge \cdots {\sigma }_n\ge 0$.

And the normalized orthogonal set of eigenvectors of $A^{T}A$, $v_1,\dots ,v_n$, are the right singular values of $A$.

The Eigenvectors of $A^{T}A$ Lead To an Orthogonal Basis for $\mathrm{Col}A$¶

Now: we know that vectors $v_1,\dots ,v_n$ can be an orthogonal set because they are eigenvectors of the symmetric matrix $A^{T}A$.

However, it's also the case that $A{v}_1,\dots ,A{v}_n$ are an orthogonal set.

This fact is key to the SVD.

Another way to look at this is to consider that $A{v}_i={\sigma }_i{u}_i$. By definition, $U$ is also orthonormal. In other words, we've found a set of vectors $v_1,\dots ,v_n$ that, when transformed with $A$, preserves orthognonality.

Theorem. Suppose $\{v_1,\dots ,v_n\}$ is an orthonormal basis of $R^n$ consisting of eigenvectors of $A^{T}A$, arranged so that the corresponding eigenvalues of $A^{T}A$ satisfy ${\lambda }_1\ge \cdots \ge {\lambda }_n,$ and suppose $A$ has $r$ nonzero singular values.

Then $\{A{v}_1,\dots ,A{v}_r\}$ is an orthogonal basis for $\mathrm{Col}A,$ and rank $A=r$.

Note how surprising this is: while $\{v_1,\dots ,v_n\}$ are a basis for $R^n$, $\mathrm{Col}A$ is a subspace of $R^m$.

Nonetheless,

• two eigenvectors $v_i$ and $v_j\in R^n$ are orthogonal, and
• their images $A{v}_i$ and $A{v}_j\in R^m$ are also orthogonal.

Proof. What we need to do is establish that $\{A{v}_1,\dots ,A{v}_r\}$ is an orthogonal linearly independent set whose span is $\mathrm{Col}A$.

Because $v_i$ and $v_j$ are orthogonal for $i\ne j$,

So $\{A{v}_1,\dots ,A{v}_n\}$ is an orthogonal set.

Furthermore, since the lengths of the vectors $A{v}_1,\dots ,A{v}_n$ are the singular values of $A$, and since there are $r$ nonzero singular values, $A{v}_i\ne 0$ if and only if $1\le i\le r.$

So $A{v}_1,\dots ,A{v}_r$ are a linearly independent set (because they are orthogonal and all nonzero), and clearly they are each in $\mathrm{Col}A$.

Finally, we just need to show that $\mathrm{Span}\{A{v}_1,\dots ,A{v}_r\}=\mathrm{Col}A$.

To do this we'll show that for any $y$ in $\mathrm{Col}A$, we can write $y$ in terms of $\{A{v}_1,\dots ,A{v}_r\}$:

Say $y=Ax.$

Because $\{v_1,\dots ,v_n\}$ is a basis for $R^n$, we can write $x=c_1{v}_1+\cdots +c_n{v}_n,$ so

(because $A{v}_i=0$ for $i>r$).

In summary: $\{A{v}_1,\dots ,A{v}_n\}$ is an (orthogonal) linearly independent set whose span is $\mathrm{Col}A$, so it is an (orthogonal) basis for $\mathrm{Col}A$.

Notice that we have also proved that rank $A=\dim \mathrm{Col}A=r.$

In other words, if $A$ has $r$ nonzero singular values, $A$ has rank $r$.

32.1 The Singular Value Decomposition¶

What we have just proved is that the eigenvectors of $A^{T}A$ are rather special.

Note that, thinking of $A$ as a linear operator:

• its domain is $R^n$, and
• its range is $\mathrm{Col}A.$

So we have just proved that

• the set $\left\{v_i\right\}$ is an orthogonal basis for the domain of $A$, and
• the set $\left\{A{v}_i\right\}$ is an orthogonal basis for the range of $A$.

Now we can return to the definition of the SVD.

Theorem. Let $A$ be an $m\times n$ matrix with rank $r$. Then there exists an $m\times n$ matrix $\Sigma$ whose diagonal entries are the first $r$ singular values of $A$, ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0,$ and there exists an $m\times m$ orthogonal matrix $U$ and an $n\times n$ orthogonal matrix $V$ such that

The right singular vectors of $A$ are the corresponding eigenvectors $v_1,\dots ,v_n$ of $A^{\top }A$, normalized to be of unit length.

The left singular vectors of $A$ are the vectors $u_i=\frac{1}{{\sigma }_i}A{v}_i$: that is, take $A$ times each of the right singular values and normalize them. (If ${\sigma }_i=0$, then pick any vector $u_i$ that is orthogonal to all of the previous left singular vectors.)

Any factorization $A=U\Sigma V^T,$ with $U$ and $V$ orthogonal and $\Sigma$ a diagonal matrix is called a singular value decomposition (SVD) of $A$.

The columns of $U$ are called the left singular vectors and the columns of $V$ are called the right singular vectors of $A$.

Aside: regarding the "Rolls Royce" property, consider how elegant this structure is.

In particular:

• $A$ is an arbitrary matrix
• $U$ and $V$ are both orthonormal matrices
• $\Sigma$ is a diagonal matrix
• all singular values are positive or zero
• there are as many positive singular values as the rank of $A$
  • (not part of the theorem but we'll see it is true)

Proof of SVD¶

We have built up enough tools now that the proof is quite straightforward.

Let $\left\{{\lambda }_i\right\}$ and $\left\{v_i\right\}$ be the eigenvalues and eigenvectors of $A^{T}A$, and ${\sigma }_i=\sqrt{{\lambda }_i}$.

The starting point is to use the fact that we just proved:

$\{A{v}_1,\dots ,A{v}_r\}$ is an orthogonal basis for $\mathrm{Col}A.$

Next, let us normalize each $A{v}_i$ to obtain an orthonormal basis $\{u_1,\dots ,u_r\}$, where

Then

Now the rank of $A$ (which is $r$) may be less than $m$.

In that case, add additional orthonormal vectors $\{u_{r+1}\dots u_m\}$ to the set so that they span $R^m$.

Now collect the vectors into matrices.

and

Recall that these matrices are orthogonal because the $\left\{v_i\right\}$ are orthonormal and the $\left\{A{v}_i\right\}$ are orthonormal, as we previously proved.

So

So

Now, $V$ is an orthogonal matrix, so multiplying both sides on the right by $V^T$:

21.1 Reduced SVD¶

Let's generalize this idea to get a better sense of how the SVD decomposes a matrix.

For the moment, let's consider an $m\times n$ matrix $A$ with $m<n$. (The situation when $m>n$ follows similarly).

The SVD looks like this, with singular values on the diagonal of $\Sigma$:

Now, let's assume that the number of nonzero singular values $r$ is less than $m$. (In the picture below, $r=2$.)

Again, other cases would be similar.

In many cases we are only concerned with representing $A$. In this case, we don't need the entirety of $U$ or $V$.

To compute $A$, we only need the $r$ leftmost columns of $U$, and the $r$ upper rows of $V^{\top }$.

That's because all the other values on the diagonal of $\Sigma$ are zero, so they don't contribute anything to $A$. So we might as well zeroize the corresponding columns of $U$ and rows of $V^{\top }$.

So we often work with the reduced SVD of $A$:

Note that in the reduced SVD, $\Sigma$ has all nonzero entries on its diagonal, so it can be inverted.

However, we still have that $A=U\Sigma V^T$.

32.2 Dimensionality Reduction¶

(Reduced) SVD is useful in a variety of data science applications.

One application that we will discuss today is the low-rank approximation of a matrix.

Recall that the rank of a matrix $A$ is the largest number of linearly independent columns of $A$.

Or, equivalently, the dimension of $\mathrm{Col}A$.

Let's define the rank-$k$ approximation to $A$:

When $k<\mathrm{Rank}A$, the rank-$k$ approximation to $A$ is the closest rank-$k$ matrix to $A$, i.e.,

where the Frobenius norm of a matrix $\parallel M{\parallel }_F=\sqrt{{\sum }_{i=1}^m{\sum }_{j=1}^n|m_{i,j}{|}^2}$ is the matrix equivalent to the Euclidean norm of a vector.

Why is a rank-$k$ approximation valuable?

The reason is that a rank-$k$ matrix may take up much less space than the original $A$.

$m\{\begin{array}{c}\\ \\ \\ \\ \end{array}\stackrel{n}{\stackrel{}{\left[\begin{array}{cccc}\begin{array}{c}⋮\\ ⋮\\ a_1\\ ⋮\\ ⋮\end{array}& \begin{array}{c}⋮\\ ⋮\\ a_2\\ ⋮\\ ⋮\end{array}& \dots & \begin{array}{c}⋮\\ ⋮\\ a_n\\ ⋮\\ ⋮\end{array}\end{array}\right]}}=\stackrel{k}{\stackrel{}{\left[\begin{array}{cc}⋮& ⋮\\ ⋮& ⋮\\ {\sigma }_1{u}_1& {\sigma }_k{u}_k\\ ⋮& ⋮\\ ⋮& ⋮\end{array}\right]}}\times \left[\begin{array}{ccccc}\dots & \dots & v_1& \dots & \dots \\ \dots & \dots & v_k& \dots & \dots \end{array}\right]$

The rank-$k$ approximation takes up space $(m+n)k$ while $A$ itself takes space $mn$.

For example, if $k=10$ and $m=n=1000$, then the rank-$k$ approximation takes space $20000/1000000=2\%$ of $A$.

The key to using the SVD for matrix approximation is as follows:

The best rank-$k$ approximation to any matrix can be found via the SVD.

How do we use SVD to find the best rank-$k$ approximation to $A$?

In terms of the singular value decomposition,

the best rank-$k$ approximation to $A$ is formed by taking

• $U^{\prime }=$ the $k$ leftmost columns of $U$,
• ${\Sigma }^{\prime }=$ the $k\times k$ upper left submatrix of $\Sigma$, and
• $(V^{\prime }{)}^T=$ the $k$ upper rows of $V^T$,

and constructing

Furthermore, the distance (in Frobenius norm) of the best rank-$k$ approximation $A^{\left(k\right)}$ from $A$ is equal to $\sqrt{{\sum }_{i=k+1}^r{\sigma }_i^2}$.

That is, if you construct $A^{\left(k\right)}$ as shown above, then:

32.3 Empirical Examples of SVD¶

Let's see how low-rank approximations via SVD can be used in practice, and investigate some real data.

Image compression¶

Image data often shows low effective rank, meaning that it can be simplified to a low-rank approximation with only a small loss.

For example, here is an original photo:

We can think of this as a $512\times 512$ matrix $A$ whose entries are 1-byte grayscale values (numbers between 0 and 255).

This image is 512 $\times$ 512 pixels in size. As a matrix, it has rank of 512.

But its effective rank is low. To see why, let's look at the spectrum of this image matrix:

Based on the plot above, its effective rank is perhaps 40. In fact, the error when we approximate $A$ by a rank 40 matrix is only around 10%.

Let's find the closest rank-40 matrix and view it.

Let's find the closest rank-40 matrix to $A$ and view it.

We can do this quite easily using the SVD.

We simply construct our approximation of $A$ using only the first 40 columns of $U$ and top 40 rows of $V^T$.

Note that the rank-40 boat takes up only 40/512 = 8% of the space of the original image!

This general principle is what makes image, video, and sound compression effective.

When you

• watch HDTV, or
• listen to an MP3, or
• look at a JPEG image,

these signals have been compressed using the fact that they are effectively low-rank matrices.

One interesting side effect of dimensionality reduction is that it often reduces the amount of noise in the data. Noise often shows up in the lower-order components of SVD, and dimensionality reduction sometimes removes it.

Networks¶

We'll look at data traffic on the Abilene network:

Source: Internet2, circa 2005

As we would expect, our traffic matrix has rank 121:

However -- perhaps it has low effective rank.

The numpy routine for computing SVD is np.linalg.svd:

Now let's look at the singular values of Atraf to see if it can be usefully approximated as a low-rank matrix:

This classic, sharp-elbow tells us that a few singular values are very large, and most singular values are quite small.

Zooming in for just small $k$ values, we can see that the elbow is around 4 - 6 singular values:

This pattern of singular values suggests low effective rank.

Let's compute the relative error of a rank-$k$ approximation to $A$ by measuring the Frobenius norm $\parallel A-A^{\left(k\right)}{\parallel }_F$ (which basically treats the matrix as a vector):

Remarkably, we are down to 9% relative error using only a rank 20 approximation to $A$.

So instead of storing

• $mn=$ (1008 $\cdot$ 121) = 121,968 values,

we only need to store

• $k(m+n)$ = 20 $\cdot$ (1008 + 121) = 22,580 values,

which is a 81% reduction in size.

Low Effective Rank is Common¶

In practice many datasets have low effective rank.

Here are some more examples.

User preferences over items.

Example: the Netflix prize worked with partially-observed matrices like this:

Where the rows correspond to users, the columns to movies, and the entries are ratings.

Although the problem matrix was of size 500,000 $\times$ 18,000, the winning approach modeled the matrix as having rank 20 to 40.

Source: [Koren et al, IEEE Computer, 2009]

Likes on Facebook.

Here, the matrices are

1. Number of likes: Timebins $\times$ Users
2. Number of likes: Users $\times$ Page Categories
3. Entropy of likes across categories: Timebins $\times$ Users

Source: [Viswanath et al., Usenix Security, 2014]