Singular Value Decomposition (SVD) Tutorial PDF Print E-mail
Article Index
Singular Value Decomposition (SVD) Tutorial
How does SVD work?
Extending the SVD with More Factors
All Pages
When you browse standard web sources like Singular Value Decomposition (SVD) on Wikipedia, you find many equations, but not an intuitive explanation of what it is or how it works. Singular Value Decomposition is a way of factoring matrices into a series of linear approximations that expose the underlying structure of the matrix.

SVD is extraordinarily useful and has many applications such as data analysis, signal processing, pattern recognition, image compression, weather prediction, and Latent Semantic Analysis or LSA (also referred to as Latent Semantic Indexing or LSI).

How does SVD work?

As a simple example, let's look at golf scores. Suppose Phil, Tiger, and Vijay play together for 9 holes and they each make par on every hole. Their scorecard, which can also be viewed as a (hole x player) matrix might look like this.

Hole Par Phil Tiger Vijay
1 4 4 4 4
2 5 5 5 5
3 3 3 3 3
4 4 4 4 4
5 4 4 4 4
6 4 4 4 4
7 4 4 4 4
8 3 3 3 3
9 5 5 5 5

Let's look at the problem of trying to predict what score each player will make on a given hole. One idea is give each hole a HoleDifficulty factor, and each player a PlayerAbility factor. The actual score is predicted by multiplying these two factors together.

PredictedScore = HoleDifficulty * PlayerAbility

For the first attempt, let's make the HoleDifficulty be the par score for the hole, and let's make the player ability equal to 1. So on the first hole, which is par 4, we would expect a player of ability 1 to get a score of 4.

PredictedScore = HoleDifficulty * PlayerAbility = 4 * 1 = 4

For our entire scorecard or matrix, all we have to do is multiply the PlayerAbility (assumed to be 1 for all players) by the HoleDifficulty (ranges from par 3 to par 5) and we can exactly predict all the scores in our example.

In fact, this is the one dimensional (1-D) SVD factorization of the scorecard. We can represent our scorecard or matrix as the product of two vectors, the HoleDifficulty vector and the PlayerAbility vector. To predict any score, simply multiply the appropriate HoleDifficulty factor by the appropriate PlayerAbility factor. Following normal vector multiplication rules, we can generate the matrix of scores by multiplying the HoleDifficulty vector by the PlayerAbility vector, according to the following equation.


Phil Tiger Vijay
4 4 4
5 5 5
3 3 3
4 4 4
4 4 4
4 4 4
4 4 4
3 3 3
5 5 5
=
HoleDifficulty
4
5
3
4
4
4
4
3
5
*
PlayerAbility
Phil Tiger Vijay
1 1 1

Mathematicians like to keep everything orderly, so the convention is that all vectors should be scaled so they have length 1. For example, the PlayerAbility vector is modified so that the sum of the squares of its elements add to 1, instead of the current 12 + 12 + 12 = 3. To do this, we have to divide each element by the square root of 3, so that when we square it, it becomes 1/3 and the three elements add to 1. Similarly, we have to divide each HoleDifficulty element by the square root of 148. The square root of 3 times the square root of 148 is our scaling factor 21.07. The complete 1-D SVD factorization (to 2 decimal places) is:


Phil Tiger Vijay
4 4 4
5 5 5
3 3 3
4 4 4
4 4 4
4 4 4
4 4 4
3 3 3
5 5 5
=

HoleDifficulty
0.33
0.41
0.25
0.33
0.33
0.33
0.33
0.25
0.41
*

ScaleFactor
21.07
*

PlayerAbility
Phil Tiger Vijay
0.58 0.58 0.58

Our HoleDifficulty vector, that starts with 0.33, is called the Left Singular Vector. The ScaleFactor is the Singular Value, and our PlayerAbility vector, that starts with 0.58 is the Right Singular Vector. If we represent these 3 parts exactly, and multiply them together, we get the exact original scores. This means our matrix is a rank 1 matrix, another way of saying it has a simple and predictable pattern.



 
Joomla Templates by Joomlashack