Singular Value Decomposition

What is Singular Value Decomposition (SVD)?

To me, Singular Value Decomposition is a process of exploring the essence of a matrix, and it is also one of the most important matrix decompositions.

I still remember that in high school and college linear algebra classes, the most common matrix decomposition was LU decomposition.

Back then, I could never understand: to solve a system of linear equations $Ax=b$, wouldn’t it be straightforward to just find the inverse of matrix A? Why go through all the trouble of decomposing matrices? During lectures, the purpose of matrix decomposition was rarely mentioned; instead, the emphasis was on manual calculations, which left a very bitter memory. I will touch upon this in later chapters, so please stay tuned!

Returning to the topic, Singular Value Decomposition breaks down a matrix into three matrices:

Where U is the matrix formed by the eigenvectors of AA^T, and U will always be an orthogonal matrix.

$\Sigma$ is a diagonal matrix containing the square roots of the eigenvalues of AA^T or A^TA. Due to the properties of AA^T, the eigenvalues are guaranteed to be non-negative. Typically, singular values are arranged in descending order.

V^T is the matrix formed by the eigenvectors of A^TA, which is also an orthogonal matrix.

From an engineering perspective, it can be roughly understood as follows: every matrix can be broken down into these three operations:

U: Rotation

S: Scaling (stretching or shrinking)

V: Rotation

However, if we think about it from the perspective of an image, every image can be viewed as a combination of countless simpler feature vectors transformed through rotation and scaling.

Applications

SVD is widely used in various fields. Here are a few common applications, and we will wrap up with image compression as an example.

Principal Component Analysis (PCA)

Sometimes when analyzing data, having too many features makes it difficult to intuitively see the relationships between data points. A common method in data analysis is Principal Component Analysis (PCA). The core concept is to project the data’s covariance matrix onto eigenvectors (principal components) to achieve dimensionality reduction.

https://link.medium.com/hqd7YIs1SCb

Recommendation Systems

To improve the accuracy of its recommendation system, Netflix once hosted a competition, which was ultimately won by BellKor’s Pragmatic Chaos team with a 10% improvement. A key breakthrough at that time came when one team used SVD to improve their algorithm, prompting other teams to follow suit.

In recommendation systems, a user’s preferences are typically influenced by only a few factors. Moreover, recommendation systems often face issues with missing data. During the Netflix Prize competition, Funk SVD was even invented, which addressed the sparse matrix problem commonly encountered in recommendation systems while factorizing the data into only two matrices.

For a detailed explanation, please refer to this website.

Image Compression

We can think of an image as a matrix full of pixels. Performing Singular Value Decomposition on an image matrix is equivalent to finding the eigenvalues of the most important feature vectors for that image. If we pick the top singular values and discard the unimportant ones, we can reduce the matrix size while still retaining a great visual result.

import numpy as np
from PIL import Image
import matplotlib.pyplot as plt

image = Image.open('./pizza.jpg')
image_array = np.array(image.convert('L')) # 轉成灰階比較容易處理

U, S, VT = np.linalg.svd(image_array) # 奇異值分解
k = 50 # 取前 50 個奇異值

# 把原來的圖片矩陣改成 U * S(前 50 個奇異值) * Vt
image_compressed = U[:, :k] @ np.diag(S[:k]) @ VT[:k, :]
image_compressed = np.clip(image_compressed, 0, 255)
image_compressed = image_compressed.astype('uint8')
plt.imshow(image_compressed, cmap='gray')
plt.show()

First, let’s look at the result when k = 5:

There is a vague outline, but it’s hard to tell what it is.

Next, let’s look at the result when k = 50:

You can already tell it’s a pizza, though the resolution is still a bit low.

Now let’s check the result when k = 200:

The resolution is instantly much higher.

Finally, here is the original image—a delicious pizza!

Afterword

There are many underlying topics involved in Singular Value Decomposition. To fully understand it, one needs a solid grasp of concepts ranging from linear transformations and eigenvalues to matrix diagonalization, diagonal matrices, and positive definite matrices. Therefore, many detailed explanations and mathematical proofs have been omitted here.

However, for engineering applications, we only need to know that SVD allows us to see through the essence of a matrix. Any matrix can be decomposed into three smaller matrices, and based on our needs, we can select the eigenvectors corresponding to the largest singular values. This significantly reduces storage space while still reconstructing the overall picture of the matrix.