3 Ways to Perform SVD in Python Applications of Singular Value Decomposition (SVD) We are going to follow a top-down approach here and discuss the applications first.
I have explained the math behind SVD after the applications for those interested in how it works underneath.
You just need to know four things to understand the applications: SVD is the decomposition of a matrix A into 3 matrices – U, S, and V S is the diagonal matrix of singular values.
Think of singular values as the importance values of different features in the matrix The rank of a matrix is a measure of the unique information stored in a matrix.
Higher the rank, more the information Eigenvectors of a matrix are directions of maximum spread or variance of data In most of the applications, the basic principle of Dimensionality Reduction is used.
You want to reduce a high-rank matrix to a low-rank matrix while preserving important information.
SVD for Image Compression How many times have we faced this issue?.We love clicking images with our smartphone cameras and saving random photos off the web.
And then one day – no space!.Image compression helps deal with that headache.
It minimizes the size of an image in bytes to an acceptable level of quality.
This means that you are able to store more images in the same disk space as compared to before.
Image compression takes advantage of the fact that only a few of the singular values obtained after SVD are large.
You can trim the three matrices based on the first few singular values and obtain a compressed approximation of the original image.
Some of the compressed images are nearly indistinguishable from the original by the human eye.
Here’s how you can code this in Python: View the code on Gist.
Output: If you ask me, even the last image (with n_components = 100) is quite impressive.
I would not have guessed that it was compressed if I did not have the other images for comparison.
SVD for Image Recovery Ever clicked an image in low light?.Or had an old image become corrupt?.We assume that we cannot get that image back anymore.
It’s surely lost to the past.
Well – not anymore!.We’ll understand image recovery through the concept of matrix completion (and a cool Netflix example).
Matrix Completion is the process of filling in the missing entries in a partially observed matrix.
The Netflix problem is a common example of this.
Given a ratings-matrix in which each entry (i,j) represents the rating of movie j by customer i, if customer i has watched movie j and is otherwise missing, we would like to predict the remaining entries in order to make good recommendations to customers on what to watch next.
The basic fact that helps to solve this problem is that most users have a pattern in the movies they watch and in the ratings they give to these movies.
So, the ratings-matrix has little unique information.
This means that a low-rank matrix would be able to provide a good enough approximation for the matrix.
This is what we achieve with the help of SVD.
Where else do you see this property?.Yes, in matrices of images!.Since an image is contiguous, the values of most pixels depend on the pixels around them.
So a low-rank matrix can be a good approximation of these images.
Here is a snapshot of the results: Chen, Zihan.
“Singular Value Decomposition and its Applications in Image Processing.
” ACM, 2018 The entire formulation of the problem can be complex to comprehend and requires knowledge of other advanced concepts as well.
You can read the paper that I referred to here.
SVD for Eigenfaces The original paper Eigenfaces for Recognition came out in 1991.
Before this, most of the approaches for facial recognition dealt with identifying individual features such as the eyes or the nose and developing a face model by the position, size, and relationships among these features.
The Eigenface approach sought to extract the relevant information in a face image, encode it as efficiently as possible, and compare one face encoding with a database of models encoded similarly.
The encoding is obtained by expressing each face as a linear combination of the selected eigenfaces in the new face space.
Let me break the approach down into five steps: Collect a training set of faces as the training set Find the most important features by finding the directions of maximum variance – the eigenvectors or the eigenfaces Choose top M eigenfaces corresponding to the highest eigenvalues.
These eigenfaces now define a new face space Project all the data in this face space For a new face, project it into the new face space, find the closest face(s) in the space, and classify the face as a known or an unknown face You can find these eigenfaces using both PCA and SVD.
Here is the first of several eigenfaces I obtained after performing SVD on the Labelled Faces in the Wild dataset: As we can see, only the images in the first few rows look like actual faces.
Others look noisy and hence I discarded them.
I preserved a total of 120 eigenfaces and transformed the data into the new face space.
Then I used the k-nearest neighbors classifier to predict the names based on the faces.
You can see the classification report below.
Clearly, there is scope for improvement.
You can try adjusting the number of eigenfaces to preserve and experiment with different classifiers: Have a look at some of the predictions and their true labels: You can find my attempt at Facial Recognition using Eigenfaces here.
SVD for Spectral Clustering Clustering is the task of grouping similar objects together.
It is an unsupervised machine learning technique.
For most of us, clustering is synonymous with K-Means Clustering – a simple but powerful algorithm.
However, it is not always the most accurate.
Consider the below case: Clearly, there are 2 clusters in concentric circles.
But KMeans with n_clusters = 2 gives the following clusters: K-Means is definitely not the appropriate algorithm to use here.
Spectral clustering is a technique that combats this.
It has roots in Graph theory.
These are the basic steps: Start with the Affinity matrix (A) or the Adjacency matrix of the data.
This represents how similar one object is to another.
In a graph, this would represent if an edge existed between the points or not Find the Degree matrix (D) of each object.
This is a diagonal matrix with entry (i,i) equal to the number of objects object i is similar to Find the Laplacian (L) of the Affinity Matrix: L = A – D Find the highest k eigenvectors of the Laplacian Matrix depending on their eigenvalues Run k-means on these eigenvectors to cluster the objects into k classes You can read about the complete algorithm and its math here.
The implementation of Spectral Clustering in scikit-learn is similar to KMeans: View the code on Gist.
You will obtain the below perfectly clustered data from the above code: SVD for Removing Background from Videos I have always been curious how all those TV commercials and programs manage to get a cool background behind the actors.
While this can be done manually, why put in that much manual effort when you have machine learning?.Think of how you would distinguish the background of a video from its foreground.
The background of a video is essentially static – it does not see a lot of movement.
All the movement is seen in the foreground.
This is the property that we exploit to separate the background from the foreground.
Here are the steps we can follow for implementing this approach: Create matrix M from video – This is done by sampling image snapshots from the video at regular intervals, flattening these image matrices to arrays, and storing them as the columns of matrix M We get the following plot for matrix M: What do you think these horizontal and wavy lines represent?.Take a moment to think about this.
The horizontal lines represent the pixel values that do not change throughout the video.
So essentially, these represent the background in the video.
The wavy lines show movement and represent the foreground.
We can, therefore, think of M as being the sum of two matrices – one representing the background and other the foreground The background matrix does not see a variation in pixels and is thus redundant i.
e.
it does not have a lot of unique information.
So, it is a low-rank matrix So, a low-rank approximation of M is the background matrix.
We use SVD in this step We can obtain the foreground matrix by simply subtracting the background matrix from the matrix M Here is a frame of the video after removing the background: Pretty impressive, right?.We have discussed five very useful applications of SVD so far.
But how does the math behind SVD actually work?.And how useful is it for us as data scientists?. More details