Singular Value Decomposition (SVD) Part 1

Singular Value Decomposition (SVD) is a complex computation in Linear Algebra, and it’s widely used in recommendation system. By SVD, the input user-ratings matrix can be divided into three different matrices: user-features, features-features and item-features matrices. This post is to show the full calculation process of SVD and explain each step among it.

The format of SVD:

$M = U \Sigma V^T$

M is the input m*n matrix, $U$ are the left singular vectors (m*k matrix), $\Sigma$ are the diagonal matrix (k*k matrix), $V$ are the right singular vectors (n*k matrix).

Step 1: Transfer M into a square matrix

In order to finsh SVD, we need to know the eigenvalues of the input matrix at first. But M is not always a square matrix, and it might be retangular matrix sometimes. So firstly, we need to transfer M into a square matrix by multiplying M with its transpose.

$M=\left[\begin{array}{ll} 1 & 1 \\ 0 & 3 \\ 3 & 0 \end{array}\right], \quad \quad M^{\top} M=\left[\begin{array}{lll} 1 & 0 & 3 \\ 1 & 3 & 0 \end{array}\right] \cdot\left[\begin{array}{ll} 1 & 1 \\ 0 & 3 \\ 3 & 0 \end{array}\right]=\left[\begin{array}{ll} 10 & 1 \\ 1 & 10 \end{array}\right]$

Step 2: Calculate the eigenvalues

To get the eigenvalues, we need to calculate the determinant of $M^{\top} M - \lambda I$. In the computation of this determinant, a polynomial is obtained, and the results of this polynomial are the eigenvalues.

$M^{\top} M - \lambda I=\left[\begin{array}{ll} 10 - \lambda & 1 \\ 1 & 10 - \lambda \end{array}\right], \quad \quad \begin{aligned} \operatorname{det}\left(M^{\top} M-\lambda I\right) &=\left(10-\lambda)^{2}-1\right.\\ \lambda &=11 \quad or \quad 9 \end{aligned}$

So the eigenvalues of $M^{\top} M$ are 11 and 9.

Step 3: Calculate the eigenvectors

After the calculation of eigenvalues, the next step is to calculate the eigenvectors for each eigenvalue. First we plug the eigenvalues sequently as the value of $\lambda$ into $M^{\top} M - \lambda I$ to get a matrix. To obtain eigenvectors, we also have the know the null space of this matrix. Therefore, we set a vector as $A$ and calculate $A$ through the equation $(M^{\top} M - \lambda I)*A=0$. After that, we convert the vector into an unit vector, and this unit vector is the eigenvector.

$For \quad \lambda = 9, \quad M^{\top} M - 9I=\left[\begin{array}{ll} 1 & 1 \\ 1 & 1 \end{array}\right]$

$\begin{gathered} \left(M^{\top} M-9 I\right) * A=\left[\begin{array}{ll} 1 & 1 \\ 1 & 1 \end{array}\right] \cdot\left[\begin{array}{l} a_{1} \\ a_{2} \end{array}\right], \quad {\left[\begin{array}{l} a_{1} \\ a_{2} \end{array}\right]=\left[\begin{array}{c} 1 \\ -1 \end{array}\right]} \end{gathered}$

$\sqrt{a_{1}{ }^{2}+a_{2}{ }^{2}}=\sqrt{2}, \quad \text { eigenvector: }\left[\begin{array}{l} a_{1} / \sqrt{2} \\ a_{2} / \sqrt{2} \end{array}\right]=\left[\begin{array}{c} 1 / \sqrt{2} \\ -1 / \sqrt{2} \end{array}\right]$

$\\$

$For \quad \lambda = 10, \quad M^{\top} M - 10I=\left[\begin{array}{ll} -1 & 1 \\ 1 & -1 \end{array}\right]$

$\begin{gathered} \left(M^{\top} M-10 I\right) * A=\left[\begin{array}{ll} -1 & 1 \\ 1 & -1 \end{array}\right] \cdot\left[\begin{array}{l} a_{1} \\ a_{2} \end{array}\right], \quad {\left[\begin{array}{l} a_{1} \\ a_{2} \end{array}\right]=\left[\begin{array}{c} 1 \\ 1 \end{array}\right]} \end{gathered}$

$\sqrt{a_{1}{ }^{2}+a_{2}{ }^{2}}=\sqrt{2}, \quad \text { eigenvector: }\left[\begin{array}{l} a_{1} / \sqrt{2} \\ a_{2} / \sqrt{2} \end{array}\right]=\left[\begin{array}{c} 1 / \sqrt{2} \\ 1 / \sqrt{2} \end{array}\right]$

Step 4: Construct $\Sigma$ (diagonal matrix) and V (right singular vectors)

For $\Sigma$, the diagonal elements are the square root of eigenvalues and the rest are all zero. For V, it consists of eigenvectors and each eigenvector represents one column of data in the matrix.

$V=\left[\begin{array}{cc} 1 / \sqrt{2} & -1 / \sqrt{2} \\ 1 / \sqrt{2} & 1 / \sqrt{2} \end{array}\right], \quad D=\left[\begin{array}{cc} \sqrt{11} & 0 \\ 0 & \sqrt{9} \end{array}\right]$

Step 5: Calculate U (left singular vectors)

From $M=U \Sigma V^T$, we get $U=MV \Sigma^T$. First we compute $MV$ and change the vectors in this matrix into unit vector. Then we compute $MV \Sigma^T$. After this computation, we make a unit vector transformation again, and this is the result of $U$.

$MV = \left[\begin{array}{ll} 1 & 1 \\ 0 & 3 \\ 3 & 0 \end{array}\right] \cdot\left[\begin{array}{l} 1/\sqrt{2} & -1/\sqrt{2} \\ 1/\sqrt{2} & 1/\sqrt{2} \end{array}\right] = \left[\begin{array}{l} \frac{2}{\sqrt{2}} & 0 \\ \frac{3}{\sqrt{2}} & \frac{3}{\sqrt{2}} \\ \frac{3}{\sqrt{2}} & -\frac{3}{\sqrt{2}} \end{array}\right]$

$\sqrt{(\frac{2}{\sqrt{2}})^2+(\frac{3}{\sqrt{2}})^2+(\frac{3}{\sqrt{2}})^2}=\frac{\sqrt{22}}{\sqrt{2}}, \quad \sqrt{0^2+(\frac{3}{\sqrt{2}})^2+(\frac{3}{\sqrt{2}})^2}=\frac{\sqrt{18}}{\sqrt{2}}$

$MV=\left[\begin{array}{l} \frac{2}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{22}} & 0 \cdot \frac{\sqrt{2}}{\sqrt{18}} \\ \frac{3}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{22}} & \frac{3}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{18}}\\ \frac{3}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{22}} & -\frac{3}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{18}} \end{array}\right] = \left[\begin{array}{l} \frac{2}{\sqrt{22}} & 0 \\ \frac{3}{\sqrt{22}} & \frac{3}{\sqrt{18}} \\ \frac{3}{\sqrt{22}} & -\frac{3}{\sqrt{18}} \end{array}\right]$

$MVD^T = \left[\begin{array}{l} \frac{2}{\sqrt{22}} & 0 \\ \frac{3}{\sqrt{22}} & \frac{3}{\sqrt{18}} \\ \frac{3}{\sqrt{22}} & -\frac{3}{\sqrt{18}} \end{array}\right] \cdot \left[\begin{array}{cc} \sqrt{11} & 0 \\ 0 & \sqrt{9} \end{array}\right] = \left[\begin{array}{l} \frac{2\sqrt{11}}{\sqrt{22}} & 0 \\ \frac{3\sqrt{11}}{\sqrt{22}} & \frac{3\sqrt{9}}{\sqrt{18}} \\ \frac{3\sqrt{11}}{\sqrt{22}} & -\frac{3\sqrt{9}}{\sqrt{18}} \end{array}\right] = \left[\begin{array}{l} \frac{2}{\sqrt{2}} & 0 \\ \frac{3}{\sqrt{2}} & \frac{3}{\sqrt{2}} \\ \frac{3}{\sqrt{2}} & -\frac{3}{\sqrt{2}} \end{array}\right]$

$\sqrt{(\frac{2}{\sqrt{2}})^2+(\frac{3}{\sqrt{2}})^2+(\frac{3}{\sqrt{2}})^2}=\frac{\sqrt{22}}{\sqrt{2}}, \quad \sqrt{0^2+(\frac{3}{\sqrt{2}})^2+(\frac{3}{\sqrt{2}})^2}=\frac{\sqrt{18}}{\sqrt{2}}$

$MV\Sigma^T = \left[\begin{array}{l} \frac{2}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{22}} & 0 \cdot \frac{\sqrt{2}}{\sqrt{18}} \\ \frac{3}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{22}} & \frac{3}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{18}}\\ \frac{3}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{22}} & -\frac{3}{\sqrt{2}} \cdot \frac{\sqrt{2}}{\sqrt{18}} \end{array}\right] = \left[\begin{array}{l} \frac{2}{\sqrt{22}} & 0 \\ \frac{3}{\sqrt{22}} & \frac{3}{\sqrt{18}} \\ \frac{3}{\sqrt{22}} & -\frac{3}{\sqrt{18}} \end{array}\right] = U$

*The 5 steps above is the full procedure of SVD. After all $U$, $\Sigma$, $V$ are obtain, we should compute $U\Sigma V^T$ to check if the result is equal to $M$. This is to verify the SVD we make is right.