Understanding Singular Vector Decomposition

Singular Value Decomposition or SVD as its fondly called is one of the most popular method for dimensionality reduction. It has various applications ranging from Image compression, Recommender Engines, solving matrix equations, etc. Here, I will try to make you understand the intuition behind SVD and then will try to build a real world example in R. I have also written a similar script for python and link for the same can be found at the end of the article.

I assume you have a basic understanding of Matrix algebra while reading this article. Though example would help you understand the intuition but an understanding of matrix algebra will go a long way.

Lets suppose we have rectangular matrix A of dimension (m X n) such that A=USVᵀ

Where

A = m x n rectangular matrix

U = m x r orthognal matrix

S = r x r diagonal matrix

V = r x n orthogonal matrix

To calculate SVD we need to find the eigenvalues and eigenvectors of AᵀA and AAᵀ. The eigenvectors of AᵀA make up the columns of V , the eigenvectors of AAᵀmake up the columns of U. Singular values in S are square roots of the eigenvectors of AᵀA or AAᵀ.

I am not going to solve a matrix here for an illustration rather I will go ahead and do an application of the same in R. I am going to take an image here, calculate its eigenvectors, eigenvalues and then construct back the image from U, S & Vᵀ. with varying numbers of eigenvalues from S. It will help you visualize how the chosen number of eigenvectors help you compress the image.

I have taken an image from USC database here. All images present in this collection have played a very important role when it comes image processing techniques. I will be processing the image 4.2.03.tiff (baboon). Actual image is a color image (512×512 px). For ease of explanation I have converted the image to black and white, that way we end up dealing only a single channel in our code.

Lets begin digging into the code and read this image using the jpeg library in R. When its read using jpeg package, we get an matrix type object as an output. We can create an image matrix out of this using the following code snippet.

img.matrix = matrix(imagejpg, nrow = nrow(imagejpg), ncol = ncol(imagejpg))

We now have our A, a mxn matrix. Lets go ahead and calculate svd for this matrix. No, we don’t need to calculate AᵀA & AAᵀ here as R has a method in base package to do it directly.

img.matrix.svd = svd(img.matrix)

img.matrix.svd is a list object and it has 3 members namely, u,v & d. Here d represents S in the SVD equation. We can access these list members as

d = img.matrix.svd$d

u = img.matrix.svd$u

v = img.matrix.svd$v

d,u & v can be combined to give out the original matrix. You can try that with matrix.reconstruction <- u %*% diag(d) %*% t(v).

Now lets see the effect of choosing the number of eigenvalues to reconstruct the image back. Since the elements of diagonal matrix S/d are arranged in descending order, it makes it easier to discard the negligible values appearing in the end. I will reconstruct the image by taking 3, 4, 5, 10, 20, 50, 70, 100, 200 eigenvalues which is less than half of our 512 available eigenvalues for this matrix. Notice the subtle changes after we cross the 50, one can easily recognize the baboon at that level & what we do post that just add a bit more features to the image making it more clear.

Thanks for reading through the article. Hope I was able to explain SVD intuitively. Do let me know via comments how liked the article. What else would you like to see in this space in future. R code can be found at my github repo here & for Python lovers click here.