Singular Value Decomposition

Explanation, Derivation and Applications in Python

Introduction

The linear algebra essential to data science, machine learning, and artificial intelligence is often overlooked as most introductory courses fail to display the big picture. Concepts such as eigendecomposition and singular value decomposition (SVD) are incredibly important from a practitioner's standpoint; they are the core of dimensionality reduction techniques including principal component analysis (PCA) and latent semantic analysis (LSA). This article aims to exhibit SVD by gently introducing the mathematics required in tandem with tangible Python code.

Singular Value Decomposition (SVD)

Matrix Multiplication

To start, let’s consider the following vector, x, as the sum of two basis vectors i and j.

We can easily visualize this vector using matplotlib and Python…

Vectors are relatively straightforward, they have a direction and magnitude. In this example, we plot the vector, x, from the origin. However, this same vector can be equivalently plotted anywhere in ℝ².

Now let’s consider a matrix and matrix multiplication. Mathematically…

Using standard matrix multiplication…

In Python…

Further, we can plot the product of the matrix and vector…

We can see that the matrix multiplication (Ax) changes both the direction and magnitude of our original vector x.

Essentially, the matrix rotated and stretched our original vector.

This can be seen more effectively by plotting both vectors on the same chart…

More specifically, we can see that the original vector, x, has been rotated by an angle, θ, and stretched by a scalar α. This notion of decomposition into a rotation and stretch can be generalized.

However, before we continue, instead of our original vector, x, let’s now consider a collection of vectors as a matrix V.

In this case, our collection of vectors contains the original basis vectors (i and j) which summed to create x.

The dimensionality can be generally extended to mxn —using 2x2 aids in visualization.

This notion of rotation and stretching can also be seen in AV…

Rotational Matrix

This is the matrix responsible for rotating the original vector by θ.

It is important to note that rotation matrices are unitary transformations. A special property of unitary transformations is their inverses are (trivial) the complex conjugate transposed.

Rotations are easily visualized, especially in two-dimensional space. However, this matrix may be modified to accomplish rotations at higher dimensions while specifying a particular axis of rotation.

Stretching Matrix

This is the matrix responsible for stretching the original vector by α.

The extension to higher dimensions is quite obvious — by simply diagonalizing the stretching parameter in the relevant dimensional space.

Reduced Singular Value Decomposition

All of the pieces of the puzzle are now available to us. We know that the product, AV, comprises a rotation and a stretch. To further generalize this idea, we will also consider…

dim(A)=mxn
dim(U_hat) = mxn
dim(Σ_hat) = nxn
dim(V*) = nxn

Mathematically…

If we multiply both sides on the right by the inverse of V…

In this case we will refer to the inverse of V as V*

This is the reduced singular value decomposition.

Singular Value Decomposition

We can accomplish this by adding m-n columns to the rotational matrix and m-n rows to the stretching matrix. Using this idea we redefine U_hat and Σ_hat as U and Σ…

dim(A)=mxn
dim(U) = mxm
dim(Σ) = mxn
dim(V*) = nxn

This is known formally as the singular value decomposition. Where Σ contains the stretching elements, the singular values, in descending order. The major benefit to this decomposition is that it exists for any rectangular or square matrix.

Singular Value Decomposition Analytically

Eigendecomposition is closely tied to singular value decomposition as previously mentioned. We can turn what we have already derived above into a classic eigenvalue problem from elementary linear algebra to find the SVD.

Recall that U is a unitary transformation…

Multiplying both sides by the collection of vectors V…

Recall the eigenvalue problem…

We can match the following elements in the context of this problem…

A → A^TA
x → V
λ → Σ²

The same procedure can be taken to find U by starting instead with AA^T.

Singular Value Decomposition in Python

Python makes it incredibly easy to find the singular value decomposition of a matrix using numpy.

array([[ 2.,  3.],
       [-2.,  4.]])

In the code snippet above we find the singular value decomposition of matrix A, also exhibiting the reconstruction of the original matrix by it’s SVD.

In its decomposed form, we can also visualize the elements of the singular value decomposition by linearly transforming the original collection of basis vectors V.

Applications in Image Compression

Perhaps one of the most intuitive examples of singular value decomposition comes in image compression. First, we will read in an image and find the singular value decomposition. Next, we will reduce the rank to three arbitrary levels of the matrix containing singular values (Σ). Finally, we will reconstruct the image with the reduced rank.

Reading in an Image

Note: Ensure your cwd has an image so you can follow along

Photo by Aaron Burden on Unsplash — plot generated by the author

Removing Color Channels

Prior to singular value decomposition, we are going to want to remove the color channels associated with this picture…

Singular Value Decomposition

Now we can compute the singular value decomposition of the matrix representing this image. We will use numpy just as before and visualize the components of this decomposition using matplotlib…

To get a better idea of the singular values we can plot the first 50 as they are in descending order…

Reducing the Rank of Σ

Now let’s compute the rank of the diagonal matrix S (Σ)…

We can choose which singular values to persist and set the rest of them to zero to reduce the rank — consequently, we can see the effect on our original image by taking the product of the decomposition and plotting…

10 Singular Values

25 Singular Values

50 Singular Values

Conclusion

This article has been an introduction to singular value decomposition and its applications. First, we took a basic understanding of matrix multiplication and decomposed the operation into a rotation and a stretch of an original vector (or collection of vectors). Then we generalized the notion of rotation and stretching by finding the singular value decomposition analytically and computationally; while showing the effect of the decomposition on a collection of basis vectors. Finally, we give an application of SVD in image compression by reducing the rank of matrix containing singular values (Σ).