The provided context discusses the concept of Singular Value Decomposition (SVD) in linear algebra and its applications, focusing on its mathematical explanation, derivation, and practical use in Python and image compression.

Abstract

The given text is an in-depth exploration of Singular Value Decomposition (SVD), an essential linear algebra concept in data science, machine learning, and artificial intelligence. It starts by explaining matrix multiplication and decomposing the operation into rotation and stretch of an original vector. The text then moves on to generalizing the concept of rotation and stretching, finding the singular value decomposition both analytically and computationally. Finally, the article demonstrates the application of SVD in image compression by reducing the rank of the singular value matrix (Σ). The article also includes Python code snippets to help illustrate the concepts.

Bullet points

The context introduces the concept of Singular Value Decomposition (SVD) in linear algebra and its importance in data science, machine learning, and artificial intelligence.

The text explains the concept of matrix multiplication and decomposes the operation into a rotation and a stretch of an original vector or collection of vectors.

The article discusses the generalization of rotation and stretching, finding the singular value decomposition analytically and computationally.

The article includes Python code snippets to help illustrate the concepts.

The article demonstrates the application of SVD in image compression by reducing the rank of the singular value matrix (Σ).

The text aims to help practitioners understand SVD by gently introducing the mathematics required in tandem with tangible Python code.

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 vectorsV…

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

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 (Σ)…

480

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 (Σ).