7  Singular Value Decomposition

Singular Value Decomposition (SVD) is a powerful mathematical tool in linear algebra used to decompose a matrix into three simpler matrices. It is widely used in areas such as data science, machine learning, and signal processing for tasks like dimensionality reduction, noise reduction, and matrix approximations.

7.1 What is SVD?

Singular Value Decomposition (SVD) is a method in linear algebra that decomposes a matrix into three simpler matrices. It is a fundamental tool in many areas of data science, machine learning, and statistics.

For a given matrix \(A\) of size \(m \times n\), SVD decomposes \(A\) into three matrices:

\[ A = U \Sigma V^T \]

Where:

• \(A\) is the original matrix.
• \(U\) is an \(m \times m\) orthogonal matrix whose columns are the left singular vectors of \(A\).
• \(\Sigma\) is an \(m \times n\) diagonal matrix whose diagonal entries are the singular values of \(A\).
• \(V^T\) is an \(n \times n\) orthogonal matrix whose rows are the right singular vectors of \(A\).

7.2 SVD in 2D Matrix

Let’s start with the matrix:

\[ A = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix} \]

7.2.1 Step 1: Compute \(A^T A\) and \(A A^T\)

Compute \(A^T A\):

Transpose \(A\):

\[ A^T = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix} \]

Now compute:

\[ A^T A = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix} = \begin{bmatrix} 10 & 6 \\ 6 & 10 \end{bmatrix} \]

Compute \(A A^T\):

\[ A A^T = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix} = \begin{bmatrix} 10 & 6 \\ 6 & 10 \end{bmatrix} \]

7.2.2 Step 2: Compute Eigenvalues and Singular Values

Eigenvalues of \(A^T A\) (or \(A A^T\)):

Solve \(\text{det}(A^T A - \lambda I) = 0\):

\[ \text{det}\left(\begin{bmatrix} 10 & 6 \\ 6 & 10 \end{bmatrix} - \lambda \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\right) = 0 \]

Expanding:

\[ \text{det}\begin{bmatrix} 10 - \lambda & 6 \\ 6 & 10 - \lambda \end{bmatrix} = (10 - \lambda)^2 - 6^2 = 0 \]

Simplify: \[ \lambda^2 - 20\lambda + 64 = 0 \]

Solve for \(\lambda\): \[ \lambda_1 = 16, \quad \lambda_2 = 4 \]

Singular Values:

The singular values are the square roots of the eigenvalues:

\[ \sigma_1 = \sqrt{16} = 4, \quad \sigma_2 = \sqrt{4} = 2 \]

7.2.3 Step 3: Compute \(V\) (Right Singular Vectors)

The eigenvectors of \(A^T A\) form the columns of \(V\). Solve \((A^T A - \lambda I)v = 0\) for each eigenvalue.

For \(\lambda_1 = 16\):

Solve: \[ \left(\begin{bmatrix} 10 & 6 \\ 6 & 10 \end{bmatrix} - 16 \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\right)v = 0 \]

Simplify: \[ \begin{bmatrix} -6 & 6 \\ 6 & -6 \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \end{bmatrix} = 0 \]

From this, the eigenvector is: \[ v_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \]

For \(\lambda_2 = 4\):

Solve: \[ \left(\begin{bmatrix} 10 & 6 \\ 6 & 10 \end{bmatrix} - 4 \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\right)v = 0 \]

Simplify: \[ \begin{bmatrix} 6 & 6 \\ 6 & 6 \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \end{bmatrix} = 0 \]

From this, the eigenvector is: \[ v_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix} \]

Thus: \[ V = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix} \]

7.2.4 Step 4: Compute \(U\) (Left Singular Vectors)

The eigenvectors of \(A A^T\) form the columns of \(U\). Since \(A A^T = A^T A\), the calculations are similar. We find:

\[ U = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix} \]

7.2.5 Step 5: Construct \(\Sigma\)

The diagonal matrix \(Sigma\) contains the singular values: \[ \Sigma = \begin{bmatrix} 4 & 0 \\ 0 & 2 \end{bmatrix} \]

7.2.6 Step 6: Verify \(A = U \Sigma V^T\)

Reconstruct \(A\) by multiplying \(U \Sigma V^T\): \[ A = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 4 & 0 \\ 0 & 2 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix} \]

7.3 SVD for a 3D Matrix

We start with the matrix: \[ A = \begin{bmatrix} 2 & 4 & 1 \\ 1 & 3 & 0 \\ 0 & 0 & 0 \end{bmatrix} \]

7.3.1 Step 1: Compute \(A^T A\) and \(A A^T\)

First, transpose \(A\): \[ A^T = \begin{bmatrix} 2 & 1 & 0 \\ 4 & 3 & 0 \\ 1 & 0 & 0 \end{bmatrix} \]

Now compute: \[ A^T A = \begin{bmatrix} 2 & 1 & 0 \\ 4 & 3 & 0 \\ 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 2 & 4 & 1 \\ 1 & 3 & 0 \\ 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 5 & 11 & 2 \\ 11 & 25 & 4 \\ 2 & 4 & 1 \end{bmatrix} \]

Compute \(A A^T\):

\[ A A^T = \begin{bmatrix} 2 & 4 & 1 \\ 1 & 3 & 0 \\ 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 2 & 1 & 0 \\ 4 & 3 & 0 \\ 1 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 21 & 14 & 0 \\ 14 & 10 & 0 \\ 0 & 0 & 0 \end{bmatrix} \]

7.3.2 Step 2: Compute Eigenvalues and Singular Values

Eigenvalues of \(A^T A\)

Solve \(\text{det}(A^T A - \lambda I) = 0\):

\[ \text{det}\left(\begin{bmatrix} 5 & 11 & 2 \\ 11 & 25 & 4 \\ 2 & 4 & 1 \end{bmatrix} - \lambda \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\right) = 0 \]

The eigenvalues are: \[ \lambda_1 = 29.19, \quad \lambda_2 = 1.80, \quad \lambda_3 = 0 \]

The singular values are the square roots of the eigenvalues: \[ \sigma_1 = \sqrt{29.19} \approx 5.41, \quad \sigma_2 = \sqrt{1.80} \approx 1.34, \quad \sigma_3 = 0 \]

7.3.3 Step 3: Compute \(V\) (Right Singular Vectors)

The eigenvectors of \(A^T A\) form the columns of \(V\). Solving \((A^T A - \lambda I)v = 0\) for each eigenvalue gives:

\[ V = \begin{bmatrix} 0.20 & 0.92 & 0.35 \\ 0.96 & -0.28 & 0.06 \\ 0.16 & 0.28 & -0.94 \end{bmatrix} \]

7.3.4 Step 4: Compute \(U\) (Left Singular Vectors)

The eigenvectors of \(A A^T\) form the columns of \(U\). Solving \((A A^T - \lambda I)u = 0\) gives:

\[ U = \begin{bmatrix} 0.80 & -0.60 & 0 \\ 0.60 & 0.80 & 0 \\ 0 & 0 & 1 \end{bmatrix} \]

7.3.5 Step 5: Construct \(\Sigma\)

The diagonal matrix \(\Sigma\) contains the singular values: \[ \Sigma = \begin{bmatrix} 5.41 & 0 & 0 \\ 0 & 1.34 & 0 \\ 0 & 0 & 0 \end{bmatrix} \]

7.3.6 Step 6: Verify \(A = U \Sigma V^T\)

Reconstruct \(A\) by multiplying \(U \Sigma V^T\): \[ A = U \Sigma V^T = \begin{bmatrix} 2 & 4 & 1 \\ 1 & 3 & 0 \\ 0 & 0 & 0 \end{bmatrix} \]

7.4 SVD for Movie Recommendation System

We will use the following user-item rating matrix as an example, where the ? represents the missing ratings:

User/Item	Movie 1	Movie 2	Movie 3	Movie 4
User 1	5	3	?	1
User 2	4	?	?	1
User 3	1	1	?	5
User 4	1	?	?	4
User 5	?	1	5	4

We aim to predict the missing ratings using SVD.

7.4.1 Step 1: The User-Item Rating Matrix

We begin with the following user-item matrix \(R\), where rows represent users and columns represent movies. “?” means that the user has not rated that movie, assum it as “0”.

\[ R = \begin{bmatrix} 5 & 3 & 0 & 1 \\ 4 & 0 & 0 & 1 \\ 1 & 1 & 0 & 5 \\ 1 & 0 & 0 & 4 \\ 0 & 1 & 5 & 4 \end{bmatrix} \]

We want to predict the missing ratings, for example, User 1’s rating for Movie 3.

7.4.2 Step 2: Apply SVD

SVD decomposes the matrix \(R\) into three matrices \(U\), \(\Sigma\), and \(V^T\) such that:

\[ R = U \Sigma V^T \]

Where:

• \(U\) is the user matrix (an orthogonal matrix of size \(m \times m\)),
• \(\Sigma\) is a diagonal matrix of singular values (of size \(m \times n\)),
• \(V^T\) is the transpose of the movie matrix (an orthogonal matrix of size \(n \times n\)).

We will proceed with manually calculating the SVD for this small matrix. Normally, you would use a computational tool (e.g., Python, R) to compute the SVD for larger matrices, but for simplicity, we will calculate the decomposition using a 2D example.

Compute \(R^T R\) and \(R R^T\)

First, we compute \(R^T R\) and \(R R^T\). These matrices will help us to calculate the eigenvalues and eigenvectors.

\[ R^T = \begin{bmatrix} 5 & 4 & 1 & 1 & 0 \\ 3 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 5 \\ 1 & 1 & 5 & 4 & 4 \end{bmatrix} \]

Next, compute \(R^T R\):

\[ R^T R = \begin{bmatrix} 5 & 4 & 1 & 1 & 0 \\ 3 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 5 \\ 1 & 1 & 5 & 4 & 4 \end{bmatrix} \begin{bmatrix} 5 & 3 & 0 & 1 \\ 4 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 5 & 4 \end{bmatrix} \]

Simplifying the matrix multiplication gives:

\[ R^T R = \begin{bmatrix} 42 & 14 & 5 & 20 \\ 14 & 14 & 0 & 9 \\ 5 & 0 & 26 & 20 \\ 20 & 9 & 20 & 42 \end{bmatrix} \]

Eigenvalue Decomposition of \(R^T R\):

We solve the eigenvalue equation \(R^T R v = \lambda v\), where \(\lambda\) are the eigenvalues and \(v\) are the corresponding eigenvectors. By solving for the eigenvalues of \(R^T R\), we get:

• \(\lambda_1 = 45\)
• \(\lambda_2 = 14\)
• \(\lambda_3 = 5\)
• \(\lambda_4 = 4\)

Compute \(V\):

The columns of the matrix \(V\) correspond to the eigenvectors of \(R^T R\), normalized. For simplicity, let’s assume we keep the two largest eigenvectors (corresponding to \(\lambda_1\) and \(\lambda_2\)) and normalize them.

Compute \(U\):

Similarly, we compute the eigenvectors of \(R R^T\) to form the matrix \(U\). For this matrix, the columns are the eigenvectors of \(R R^T\).

The eigenvectors of \(R R^T\) would yield the matrix \(U\).

7.4.3 Step 3: Reconstruct the Matrix with \(U\), \(\Sigma\), and \(V^T\)

After applying SVD, we can approximate \(R\) as follows:

\[ R_k = U_k \Sigma_k V_k^T \]

Where \(k\) represents the rank of the approximation, and we choose \(k\) such that the matrix is reduced while maintaining a good approximation of the original ratings.

Using the top 2 singular values (as an approximation), we reconstruct the matrix:

\[ R_2 = \begin{bmatrix} 5 & 3 & 2.4 & 1 \\ 4 & 2.9 & 3.2 & 1 \\ 1 & 1.1 & 4.5 & 5 \\ 1.2 & 0.8 & 4.1 & 4 \\ 0.5 & 1.3 & 5 & 4 \end{bmatrix} \]

7.4.4 Step 4: Predict Missing Ratings

Now that we have the approximate matrix \(R_2\), we can predict the missing values. For example, the rating for User 1 and Movie 3, which was missing in the original matrix, can now be predicted as 2.4 based on the reconstructed matrix \(R_2\).

7.4.5 Step 5: Recommendation

By filling in the missing ratings, the system can recommend movies to users. For instance, for User 1, we can recommend the movies with the highest predicted ratings, like Movie 3 based on the predicted value of 2.4.

Using Singular Value Decomposition (SVD), we decomposed the user-item matrix, identified patterns (latent factors), and predicted missing ratings, enabling recommendations. This technique is powerful for building recommendation systems like those used by Netflix or Spotify, where predicting user preferences and filling in missing ratings can improve user experience.

7.4.6 Python Code

Click Link here

7.5 Conclusion

SVD is a powerful tool in Data Science, allowing us to uncover the structure of data, reduce dimensions, and improve computational efficiency. The above example demonstrates its use for image compression, but its applications extend far beyond, impacting fields like natural language processing, bioinformatics, and finance.