Singular Value Decomposition (SVD) — Working Example

Recently, I started looking into recommender systems and collaborative filtering in particular in which the input matrix of users-ratings is broken down into 3 matrices of user-features, features-features and item-features matrices using a technique called Singular Value Decomposition (SVD). Before, I applied this, I wanted to get an intuitive understanding of the math behind and thus started my week-long journey in the world of matrix decomposition. Well, I was not one of those math heads at school so I ended up lost in a lot of the tutorials for SVD because they missed some of the steps like computing row-echelon form, null space of a matrix. etc. So, I set out learning and diving deeper into how SVD actually works and how these three matrices are formed a.k.a how is a given input matrix decomposed to these three matrices. In this story, I will be working through an example of SVD and breakdown the entire process mathematically. So, let’s go!

According to the formula for SVD,

SVD Formula

1. A is the input matrix
2. U are the left singular vectors,
3. sigma are the diagonal/eigenvalues
4. V are the right singular vectors.

The shape of these three matrices will be

1. A — m x n matrix
2. U — m x k matrix
3. Sigma — k x k matrix
4. V — n x k matrix

Step 1

So, as the first step, we need to find eigenvalues (watch the video provided below to get an understanding of eigenvalues and eigenvectors) of matrix A and as A can be a rectangular matrix, we need to convert it to a square matrix by multiplying A with its transpose. Here, for easier computation I have taken A as a 2 x 2 matrix.

Step 2

Now, that we have a square matrix, we can calculate the eigenvalues of A(transpose) A. We, can do so by calculating the determinant of A(transpose)A — (lambda)I where lambda are the two eigenvalues.

Solving the equation, we get

Eigenvalues

Step 3

Once we have calculated the eigenvalues, it’s time to calculate the two eigenvectors for each eigenvalue. So, let’s start by calculating the eigenvector for 10.

Step 3.1

We plug the value of lambda in the A(transpose)A — (lambda)I matrix.

In order to find the eigenvector, we need to find the null space of a matrix where AB = 0. In other words,

Null Space Formula

Next, we need to reduce this matrix to the Row-Echelon Form so that we can easily solve the equation. Let’s talk about Row-Echelon for a moment here.

Row-Echelon Form

A matrix is said to be in row-echelon form if the following rules are satisfied.

1. All the leading entries in each row of the matrix is 1
2. If a column contains a leading entry then all the entries below the leading entry should be zero
3. If any two consecutive non-zero rows, the leading entry in the upper row should occur to the left of the leading entry in the lower row.
4. All rows which consist only of zeros should occur in the bottom of the matrix

We need to perform some operations on the rows to reduce the matrix. These operations are called elementary row operations and there are a certain rules to follow for these operations as given below,

https://en.wikibooks.org/wiki/Linear_Algebra/Row_Reduction_and_Echelon_Forms

Armed with the above rules, lets start reducing the matrix in Step 3.1 to row-echelon form.

Row-Echelon Form for matrix mentioned in Step 3.1

Now, we can solve for null space as below to find the eigenvector for eigenvalue 10

Once we get this vector, we need to convert it to a unit vector . The way we do that is by taking the columnar values and dividing them by taking the square root of the sum of squares of the values. So, in this case we do the following,

Denominator

So the final eigenvector for eigenvalue is

We do the similar steps to get the eigenvector for eigenvalue 40

Matrix for computation

Row-Echelon Form

EigenVector for 40

Now that we have got both the eigenvectors, let’s put it together.

Note that the diagonal values in sigma are always in the descending order and so the vectors are also placed in that corresponding order. If you are familiar with PCA, the principal components correspond to the top k diagonal element which captures the most variance. The higher the value, the more important the component is and the more variance they describe.

Step 4

Now that we have our V and Sigma matrices, now it’s time to find U. We can just multiply the equation by sigma(inverse) and V on both sides to get the equation for U. In this case, as V is an orthogonal matrix, the transpose and inverse of V are the same, therefore, V(transpose) multiplied by V becomes an identity matrix. Same goes, for the diagonal matrix as well.

Note: On the left hand side, it is sigma(inverse) and not transpose as mentioned in the slide below

Computing A x V

Next up, we need to convert this to unit vectors using the steps described above.

AV as unit vectors

Next up we multiply this matrix with Sigma (transpose) which is sigma in itself because its a diagonal matrix.

AV x sigma (transpose)

Now, we need to convert this to unit vectors to get the final U matrix.

U

So, there you go, we have calculated U, sigma and V and decomposed the matrix A into three matrices as given below.

SVD

You can verify this by going to this nice little tool and performing the matrix multiplications.

Closing Notes:

Understanding how to calculate SVD and also the theoretical understanding has helped me gain a more intuitive understanding of its applications like PCA, collaborative filtering. etc. You can also decompose a matrix using Eigen decomposition but the advantage of SVD over Eigen Decomposition is that SVD works even for rectangular matrices.

Note : Math heads comment in the section below if there is a mistake and I will do my best to rectify it. The purpose of this story was to give an understanding of the calculation and give people who are new to linear algebra and learning SVD a one-stop shop for all the different components.

Thank you for reading.

References

1. Row Echelon Form — https://www.youtube.com/watch?v=biW3S9EdE4w
2. Null Space — https://www.cliffsnotes.com/study-guides/algebra/linear-algebra/real-euclidean-vector-spaces/the-nullspace-of-a-matrix
3. Calculating null space — http://www.math.odu.edu/~bogacki/cgi-bin/lat.cgi
4. Mining Of Massive Datasets — https://www.youtube.com/watch?v=UyAfmAZU_WI
5. Determinants — https://www.youtube.com/watch?v=Ip3X9LOh2dk&t=157s
6. EigenValues and EigenVectors — https://www.youtube.com/watch?v=PFDu9oVAE-g
7. Matrix Multiplication — https://matrix.reshish.com/multiplication.php
8. Test SVD — https://keisan.casio.com/exec/system/15076953160460
9. Matrix used in this story — https://atozmath.com/example/MatrixEv.aspx?he=e&q=svd
10. SVD — https://www.youtube.com/watch?v=mBcLRGuAFUk