The SVD stands for Singular value decomposition, its a matrix factorization method more details can be found on Wikipedia. Each matrix can be decomposed into 3 matrices.
Were is a diagonal matrix with the singular values. The decomposition will look like the follwoing figure:
Instead of using all singular values, select the top , and instead of multiplying and to get matrix , now multiply and to get an approximation of matrix ,
So this approximation can be created by using far less data than the original matrix. How good is the approximation? Well you could look at the Frobenius norm, or any other matrix norm that measures the distance between the approximation and the original matrix, see http://en.wikipedia.org/wiki/Matrix_norm.
Instead, to get things more visual you can look at pictures. I am using an old picture of me and my son in the following “SVD experiment”.
Original picture 2448 X 3264 pixels ~ a matrix with 8 milion numbers
Now I am taking only the 15 largest singular values and reconstructing the picture with . This uses only 1% of the data and I get the following picture
Now I am taking only the 75 largest singular values and reconstructing the picture with . This uses around 5% of the data and I get.
In a next post I’ll show how this can be used in text mining….