How to compute SVD and conquer the world before breakfast?

17 March, 2008 11:00

Digg, Face Book and My Space all rolled into one.

Imagine you a serial entrepreneur and would like to conquer the world with a new, kicking ass web application. Digg, Face Book and My Space all rolled into one. You are going to a build perfect tool that will discover a relevant content for you and your friends all over the whooooooole web. It will be based on your intentions and intentions of your community. Your idea is great!!!. You can already see yourself on the cover of Wired magazine. You will be more popular than David Heinemaier Hanson, Britney Spears and David Beckham all together. You will be a super star. You ARE a super star!!!

You open you machine, start coding, implement the first pages of your application and then… Boom, bang, boom! The first problem crops up. How to group web sites, blog posts based on their content? How to retrieve semantics from them? How to cluster all this stuff? You google for the solution and after a while you find out that sth called Singular Value Decomposition may help. Old uncle Google says it definitely sounds like a good “candidate” to investigate. Unfortunately, you have to refresh your knowledge about linear algebra. It is awful but if you want to reach for the stars… No pain no gain!

Linear algebra comes with help - SVD

Today I would like to continue with a linear algebra refresher and introduce matrix decomposition with SVD.

Singular Value Decomposition is one of the cluster analysis and noise reduction technique introduced in 1965 by G. Golub and W. Raman. When we compute the SVD of a matrix the goal is to reduce matrix dimensionality by its decomposition into three components and keeping first k singular values. It will give us an approximated representation of the original matrix. A kind of compressed version of the matrix.

There are a lot of practical areas where SVD can be applied. In one of the next posts I would like to present the application of SVD in Information Retrieval where it is used in the process of Latent Semantic Indexing in order to search for documents that meet given query. It is one of the methods that can help in the analysis of text collections. For instance, blog post or other web content exposed to your next generation web application.

Before I share with you code to do all the stuff please grab your pencil plus a notebook and let me share with you in the next few lines how is singular values decomposition computed and approximation of the matrix built.

SVD decomposes matrix into three components: A = USV^T

• U - matrix whose columns are the eigenvectors of the AA^T matrix - called the left eigenvectors
• S - matrix whose diagonal elements are the singular values of A. Please note it is diagonal matrix so its all non-diagonal elements are zero
• V - matrix whose column are the eigenvectors of the A^TA matrix - called the right eigenvectors

Okey-doke… nice definition but how does it work? Let’s say we have matrix A

The first step is to compute a A^T. If you would like to refresh your memory about matrices and matters related to them please have a look at Matrix cookbook Part 1 and 2. All you have to know is how to transpose matrix and multiply two matrices.

As soon as we have A^T and A^TA the next step is to obtain singular values of the matrix. In order to do it we have to compute the eigen values of A^TA, sort absolute values of them in descending order and just after that place them on the diagonal of S matrix. Don’t worry, it is easy. Actually, all you need to do is to solve a polynomial equation. Let’s have a look at all the calculations.

Singular values of the matrix are computed. We can construct S matrix.

Fresh coffe on the table and now we are ready to compute V

We will use eigen values of the A^TA matrix we have just computed and construct eigen vectors.

Let’s do it for x = 13.32

Let’s repeat the exercise but this time for x = 0.67

There we go… We are almost done. Now we have to place eigenvectors on V matrix and transpose it.

At this point we have to the same calculation but for AA^T matrix and compute U matrix.

…time for U2

Here we go. Matrix reloaded

We have computed U, S and V^T. Now we have to write unit test… hmm… Please grab your pencil again and check with me if USV^T is the approximation of matrix A.

It looks good. We have decomposed matrix A into three matrices. But… why do it? How can we benefit from it? We will benefit from it as soon as we built compressed version of the matrix A. In our simple example the matrix is 2-dimensional. Imagine you deal with a matrix with huge dimensionality. Imagine “gazillions” of dimensions and a lot of noise there. It is a situation where you definitely would prefer to deal with approximated version. Fortunately, building an approximation of the original matrix is piece of cake. It is done by truncating the three matrices obtained from a full SVD. All we keep are the first k columns of U, the first k rows of V^T and the first k rows and columns of S. As soon as we have done it, we get a compressed version of the matrix A.

There is more to come…

In the next post I will share with you how to apply SVD in the process of Latent Semantic Indexing. You won’t even need a pencil or a notebook. This time we will write some code. Let’s apply theory in practice.

I also plan to continue an idea of building the next generation web content filter and focus on data mining techniques that can be useful on the way.

Stay tuned. There is more to come.

Matrix cookbook - Part 2

20 January, 2008 05:52

Today’s entry is continuation of my last post where I have introduced some basic information about matrices. In the next few lines I would like to share with you more definitions related to matrices and describe basic operations on it.

Let me start with definitions.

• Stochastic matrix is matrix whose sum of all row elements (or column elements) equal to 1.
• Triangularl matrix is matrix in which all elements above or below the principal have 0 value.
• Rank of matrix is equal to the number of linearly independent rows or columns it contains, whichever of these two numbers is smaller. It is worth to remember that rank of a square matrix is equal to the number of nonzero rows.
• Determinant is function that associates a scalar to a square matrix.
• Invertible matrix is matrix with a nonzero determinant.
• Regular matrix is a square matrix that determinant is not 0.
• Singular matrix is matrix that determinant is equal to 0.

Let me now show few basic operation on matrices. Let’s assume we have to matrices A and B.

• Addition
  
• Substraction
  
• Multiplication
  
• Calculation of matrix determinant
  

Matrix cookbook - Part 1

13 January, 2008 07:09

In this post I would like to introduce some basic information about matrices and matters relating to them. I do not pretend to make a comprehensive review out of it. Material I have prepared is divided into two parts and limited to what I think will be the most relevant to understand posts about Singular Value Decomposition, Latent Semantic Indexing and Vector Space Model I am going to write in the coming weeks. Goal of this post is just to help readers to grasp fundamental concepts and fully benefit from the future posts.

First of all, let’s go through some one-line definitions and visualizations that will introduce different types of matrices.

• Matrix is a rectangular array composed of rows and columns.
• Square matrix is matrix where the number of rows (m) equals to the number of columns (n).
• Principal of the matrix is diagonal extending from the upper-left to the lower-right corner of a square matrix.

• Trace of the matrix is sum of the all elements on the principal.
• Diagonal matrix is matrix in which all elements that are not located on the principal equal to 0.
• Scalar matrix is a variation of a diagonal matrix where all elements located on the principal are equal.
• Identity matrix also known as unit matrix is special case of scalar matrix where all elements are equal to 1.

• Transpose matrix is matrix that was obtained by converting rows into columns and vice versa.

Your suggestion for additional content or elaboration of some topics is most welcome. Please don’t hesitate to contact with me tomek@codequest.eu.