This post is PART-1 of two posts. PART-1 will go through matrix decomposition using Singular Vector Decomposition (SVD), randomized Singular Vector Decomposition (rSVD) and Nonnegative Matrix Factorization (NMF) mainly for image compression.

PART-2 will look at video background removal using randomized SVD and robust PCA.

Singular Vector Decomposition (simple matrix example)

Singular Vector Decomposition (SVD) is a mathematical technique for decomposing a matrix into three separate matrices, each having special properties. In essence, SVD transforms correlated variables into a set of uncorrelated variables.

SVD can be used to better understanding a dataset because SVD will show you the number of important dimensions, it also can simplify the dataset by reducing the number of features removing linearly dependent features from the point of view of Linear Algebra. So SVD can be used to reduce a high-dimensional dataset into fewer dimensions while retaining important information.

Suppose A is a matrix with each variable in a column, and observations in rows, then the SVD are composed by:

A = U · d · V^T

Where:

• A: original matrix (m x n)
• U: orthogonal matrix (m × n)
• d: diagonal matrix (n × n)
• V: orthogonal matrix (n × n)

Let’s start with a small example dataset A: 10 x 3, with 3 features and 10 rows.

Next code will transform the A matrix into 3 matrices (diagonal matrix: d, and the u and v) according to SVD decomposition and using the function svd(). Below you can see these matrices:

We have to take into account some aspects about SVD result matrices:

• Each row of u matrix corresponds with each row in the the original matrix.
• The columns of matrix v match with features in original matrix.
• The columns of matrix u must be considered like topic1, topic2, and topic3 and doesn’t match directly with the original matrix columns (feature_1, feature_2, feature_3).
• Diagonal matrix (d) corresponds with each topic, and are ordered by topic importance (first element more important and so on).

According to that, we can put names to each column to clarify it:

Observe the correlation between columns of u matrix:

As an example, only to see the differences between features (from the original matrix) and topics, we can replicate the A matrix into the object B, and then put zeros in feature_3:

Now we can calculate the SVD of matrix B. As you can see below the zero values are visible only in the diagonal matrix, and in the v matrix, but not in the u matrix.

Now we can reconstruct the original B matrix using u,v and d matrices and computing B=u·d·v^T.

We can check now if the original B matrix and the reconstructed B_ matrix are the same (or almost the same) by simply subtracting the matrices. You can see that two matrices match very well.

We can also calculate the RMSE of all the errors:

Singular Vector Decomposition (image example)

Now let’s suppose we want to reduce the size of an image by compressing it. We can use SVD for this job!.

First of all, we need to install/load the package rsvd, next there is an example image of a tiger than we will use for our purpose, the dimensions are: 1600×1200 grayscaled (8 bit [0-255]/255) image.

Next step is to apply svd() to the tiger image, so we get our three matrices: u, d, and v.

Next, we can plot the importance of the topics, remember that are ordered by importance, so the left side of the plot is more important and right side is less important, in order to explain the original image:

For this example, we will select the most important 100 topics. Remember that topics are ordered, so it’s as easy as selecting the first 100 columns of the matrices.

So starting from 1200 topics, we will get only the first 100 and then we will reconstruct the image using the reduced matrices:

In essence, we are using only the orange part of the matrices for reconstructing matrix A. See below for a diagram.

Finally, we can display the original and the reduced image:

And we can estimate below the size of the matrices that have been reduced by 9.52%

Randomized SVD method (image example)

In the last part, we used SVD method for compressing images. We can also use the randomized SVD method (using the rsvd package) that is equivalent to classical SVD but faster. You can have a look at: PDF for benchmark details.

A simple speed comparative can be found below.

As you can see, in this case, the randomize SVD is much faster than the classical SVD. Next, we will see how rSVD works, note that you have to tell to the function the number of topics or the the low-rank decomposition (the k argument of the function) in advance.

Comparing the results of SVD and rSVD, it looks similar.

Calculating the error (RMSE) of the decomposition depending on the k value:

As we can see below, incrementing the k value (the low-rank decomposition) decreases the RMSE and increases the size of the matrices in memory:

Below we can observe the different result images for different k values:

Non-negative Matrix Factorization (image example)

Non-negative matrix factorization (NMF) is another method of matrix decomposition. It decomposes a given matrix V into two matrices W and H:

V = W · H

The columns of W are called basis vectors and the columns of H represent the encodings, which are in one-to-one correspondence with the basis vectors of W.

One big difference over SVD is that all three matrices have no negative elements. SDV can have negative values, NMF is not possible to have negative values, non-negative values are easier interpretable than values with negative, so this is the main reason for the popularity of NMF over SVD. In counterpart, NMF will not able to recover the original matrix if does have negative numbers.

You can get more info about NMF package at PDF.

You must take into account that NMF is computationally intensive, and becomes infeasible for massive data. We can see below that the time consumed for processing our tiger image is huge, by 900 times slower than rSVD.

Below we can find the original image, and the three transformations used in this post with a low-rank decomposition of 100.

In this post we have seen the SVD, rSVD and NMF matrix decomposition methods manly applied to images. In PART 2 we will use these techniques in video surveillance for video background removal.

See you in the next post!!

---

Session Info:

Appendix, all the code: