Announcements¶

• Homework:
  • Optional bonus homework out, due Friday
    • Will replace your lowest homework score
• Final exam: Monday, May 8 from 12-2pm
• Upcoming office hours:
  • Today: Prof McDonald from 4:30-6pm in CCDS 1341
  • Tomorrow: Peer tutor Rohan Anand from 1:30-3pm in CCDS 16th floor
• Reading
  • Aggarwal Sections 8.1-8.2

Lecture 33: SVD and Principal Component Analysis¶

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

Recap from last lecture¶

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

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.

We talked about constructing the singular value decomposition using the properties of $A^{\top }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$.

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.)

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

This creates a full decomposition:

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

Dimensionality Reduction¶

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.

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$.

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:

33.1 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+512)/512*512 = 80/512 = 16% 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]

Social Media Activity.

Here, the matrices are

1. Number of Yelp reviews: Timebins $\times$ Users
2. Number of Yelp reviews: Users $\times$ Yelp Categories
3. Number of Tweets: Users $\times$ Topic Categories

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

Summary¶

The reduced singular value decomposition of a rank-$r$ matrix $A$ has the form:

where

1. $U$ is $m\times r$
2. The columns of $U$ are mutually orthogonal and unit length, ie., $U^{T}U=I$.
3. $V$ is $n\times r$.
4. The columns of $V$ are mutually orthogonal and unit length, ie., $V^{T}V=I$.
5. The matrix $\Sigma$ is an $r\times r$ diagonal matrix, whose diagonal values are ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0$.

33.2 Interpretations of Low Effective Rank¶

How can we understand the low-effective-rank phenomenon in general?

There are two helpful interpretations:

1. Common Patterns
2. Latent Factors

Low Rank Implies Common Patterns¶

The first interpretation of low-rank behavior is in answering the question:

"What is the strongest pattern in the data?"

Using the SVD we form the low-rank approximation as

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

with $$A\approx U^{\prime }{\Sigma }^{\prime }(V^{\prime }{)}^T$$

In this interpretation, we think of each column of $A$ as a combination of the columns of $U^{\prime }$.

How can this be helpful?

Consider the set of network traffic traces. There are clearly some common patterns. How can we find them?

Let's use as our example $a_1,$ the first column of $A$.

This happens to be the ATLA-CHIN flow.

The equation above tells us that

In other words, $u_1$ (the first column of $U$) is the "strongest" pattern occurring in $A$, and its strength is measured by ${\sigma }_1$.

Here is an view of the first 2 columns of $U\Sigma$ for the traffic matrix data.

These are the strongest patterns occurring across all of the 121 traces.

Low Rank Defines Latent Factors¶

The next interpretation of low-rank behavior is that it exposes "latent factors" that describe the data.

Returning to the low-rank decomposition:

In this interpretation, we think of each element of $A$ as the inner product of a row of $U^{\prime }{\Sigma }^{\prime }$ and a row of $V^{\prime }$.

Let's say we are working with a matrix of users and items.

In particular, let the items be movies and matrix entries be ratings, as in the Netflix prize.

Recall the structure from a previous slide:

Then the rating that a user gives a movie is the inner product of a $k$ element vector that corresponds to the user, and a $k$ element vector that corresponds to the movie.

In other words:

We can therefore think of user $i$'s preferences as being captured by $u_i$, ie., a point in $R^k$.

We have described everything we need to know to predict user $i$'s ratings via a $k$-element vector.

The $k$-element vector is called a latent factor.

Likewise, we can think of $v_j$ as a "description" of movie $j$ (another latent factor).

The value in using latent factors comes from the summarization of user preferences, and the predictive power one obtains.

For example, the winning entry in the Netflix prize competition modeled user preferences with a 20-element latent factor.

The remarkable thing is that a person's preferences for all 18,000 movies can be reasonably well captured in a 20-element vector!

Here is a figure from the paper that described the winning strategy in the Netflix prize.

It shows a hypothetical latent space in which each user, and each movie, is represented by a latent vector.

In practice, this is perhaps a 20- or 40-dimensional space.

Here are some representations of movies in that space (reduced to 2-D).

Notice how the space seems to capture similarity among movies!

In summary:

• When we are working with data matrices, it is valuable to consider the effective rank
• Many (many) datasets in real life show low effective rank.
• This property can be explored precisely using the Singular Value Decomposition of the matrix.
• When low effective rank is present,
  • the matrix can be compressed with only small loss of accuracy
  • we can extract the "strongest" patterns in the data
  • we can describe each data item in terms of the inner product of latent factors.