奇異值分解

What is Singular Value Decomposition (SVD)

Singular Value Decomposition is a process for exploring the essence of matrices and is one of the most important matrix decompositions.

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

At that time, I couldn't quite understand why, when solving the linear equation $Ax=b$, we couldn't simply find the inverse of A instead of going through the cumbersome process of matrix decomposition. The purpose of matrix decomposition was rarely mentioned in lectures; instead, there was an emphasis on manual calculations, which left a rather unpleasant memory. This part will be addressed in later sections, so stay tuned!

Back to the main topic, SVD can decompose a matrix into three matrices:

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

$\Sigma$ is a diagonal matrix, consisting of 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, the eigenvalues are arranged from largest to smallest.

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

From an engineer's perspective, you can roughly understand that every matrix can be broken down into these three operations:

U: Rotation

S: Scaling

V: Rotation

However, if we think in terms of images, we can consider each image as being composed of countless simpler feature vectors combined through rotation and scaling.

Applications

SVD is widely used across various fields. Here are a few common applications, and we'll conclude with an example of image compression.

Principal Component Analysis

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

https://link.medium.com/hqd7YIs1SCb

Recommendation Systems

In an effort to improve the accuracy of its recommendation system, Netflix once held a competition, which was ultimately won by BellKor’s Pragmatic Chaos team, who improved the algorithm by 10%. A breakthrough at that time was when one team used SVD to enhance their algorithm, prompting other teams to start incorporating SVD as well.

In recommendation systems, a user's preferences are typically influenced by only a few factors, and due to the common issue of missing values in such systems, Funk SVD was even invented during the Netflix competition to tackle the problem of sparse matrices, while only splitting into two matrices.

For a detailed explanation, you can refer to this website.

Image Compression

We can think of an image as a matrix filled with pixels. Performing SVD on the image matrix is akin to identifying the most important feature vectors of that image. By selecting the top few singular values and discarding the less important ones, we can reduce the matrix size while still achieving a good effect.

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')) # Convert to grayscale for easier processing

U, S, VT = np.linalg.svd(image_array) # Singular Value Decomposition
k = 50 # Taking the top 50 singular values

# Reconstruct the original image matrix as U * S (top 50 singular values) * 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 effect with k = 5:

It seems to show some contours, but it's hard to tell what it is.

Next, let's check the effect with k = 50:

Now we can see it’s a pizza, but the resolution is quite low.

Finally, let's take a look at the effect with k = 200:

The resolution improves significantly.

Now, let's see the original image—it's a delicious pizza!

Conclusion

There are many topics involved in understanding Singular Value Decomposition. To fully grasp it, one needs to have a certain level of understanding of linear transformations, eigenvalues, matrix diagonalization, diagonal matrices, and positive definite matrices. Thus, many explanations and mathematical proofs have been omitted.

However, for practical engineering applications, we only need to know that SVD can reveal the essence of a matrix. Any matrix can be decomposed into three smaller matrices, and depending on our needs, we can select the few feature vectors with the largest eigenvalues to significantly reduce storage space while reconstructing the complete structure of the matrix.