IMG_4863.jpeg

# Lecture 12: The Singular Value Decomposition (SVD) ## 1. The SVD Any $m \times n$ matrix $A$ can be factored: $A = U \Sigma V^T$ where * $U$ is an $m \times m$ orthogonal matrix ($U^T U = I$) * $V$ is an $n \times n$ orthogonal matrix ($V^T V = I$) * $\Sigma$ is an $m \times n$ diagonal...

# Lecture 12: The Singular Value Decomposition (SVD) ## 1. The SVD Any $m \times n$ matrix $A$ can be factored: $A = U \Sigma V^T$ where * $U$ is an $m \times m$ orthogonal matrix ($U^T U = I$) * $V$ is an $n \times n$ orthogonal matrix ($V^T V = I$) * $\Sigma$ is an $m \times n$ diagonal matrix with nonnegative entries ($\sigma_i \ge 0$) $\sigma_i$ are called the singular values of A. **Note:** The columns of $U$ are called the left singular vectors of A. The columns of $V$ are called the right singular vectors of A. ### Example $A = \begin{bmatrix} 4 & 11 & 14 \\ 8 & 7 & -2 \end{bmatrix} = U \Sigma V^T$ where $U = \begin{bmatrix} 1/ \sqrt{5} & -2/ \sqrt{5} \\ 2/ \sqrt{5} & 1/ \sqrt{5} \end{bmatrix}$ $\Sigma = \begin{bmatrix} 18 & 0 & 0 \\ 0 & 3 & 0 \end{bmatrix}$ $V^T = \begin{bmatrix} 1/3 & 2/3 & 2/3 \\ -2/3 & -1/3 & 2/3 \\ 2/3 & -2/3 & 1/3 \end{bmatrix}$ ### How to compute the SVD $A^T A = (U \Sigma V^T)^T (U \Sigma V^T) = V \Sigma^T U^T U \Sigma V^T = V \Sigma^T \Sigma V^T$ $A^T A = V \Sigma^T \Sigma V^T$ $\rightarrow A^T A V = V \Sigma^T \Sigma$ $\rightarrow V$ are eigenvectors of $A^T A$ $\rightarrow \sigma_i = \sqrt{\lambda_i}$, where $\lambda_i$ are eigenvalues of $A^T A$ $A A^T = (U \Sigma V^T) (U \Sigma V^T)^T = U \Sigma V^T V \Sigma^T U^T = U \Sigma \Sigma^T U^T$ $A A^T = U \Sigma \Sigma^T U^T$ $\rightarrow A A^T U = U \Sigma \Sigma^T$ $\rightarrow U$ are eigenvectors of $A A^T$ ### Example: SVD of $A = \begin{bmatrix} 4 & 11 & 14 \\ 8 & 7 & -2 \end{bmatrix}$ 1. Compute $A^T A$: $A^T A = \begin{bmatrix} 4 & 8 \\ 11 & 7 \\ 14 & -2 \end{bmatrix} \begin{bmatrix} 4 & 11 & 14 \\ 8 & 7 & -2 \end{bmatrix} = \begin{bmatrix} 80 & 100 & 40 \\ 100 & 170 & 140 \\ 40 & 140 & 200 \end{bmatrix}$ 2. Compute eigenvalues of $A^T A$: $\det(A^T A - \lambda I) = 0$ $\begin{vmatrix} 80 - \lambda & 100 & 40 \\ 100 & 170 - \lambda & 140 \\ 40 & 140 & 200 - \lambda \end{vmatrix} = 0$ $(\lambda - 36)(\lambda - 9)(\lambda - 0) = 0$ $\lambda_1 = 36, \lambda_2 = 9, \lambda_3 = 0$ 3. Compute singular values: $\sigma_1 = \sqrt{\lambda_1} = \sqrt{36} = 6$ $\sigma_2 = \sqrt{\lambda_2} = \sqrt{9} = 3$ $\Sigma = \begin{bmatrix} 6 & 0 & 0 \\ 0 & 3 & 0 \end{bmatrix}$ 4. Compute eigenvectors of $A^T A$: For $\lambda_1 = 36$: $(A^T A - 36 I)v_1 = 0$ $\begin{bmatrix} 44 & 100 & 40 \\ 100 & 134 & 140 \\ 40 & 140 & 164 \end{bmatrix} v_1 = 0$ $v_1 = \begin{bmatrix} 1/3 \\ 2/3 \\ 2/3 \end{bmatrix}$ For $\lambda_2 = 9$: $(A^T A - 9 I)v_2 = 0$ $\begin{bmatrix} 71 & 100 & 40 \\ 100 & 161 & 140 \\ 40 & 140 & 191 \end{bmatrix} v_2 = 0$ $v_2 = \begin{bmatrix} -2/3 \\ -1/3 \\ 2/3 \end{bmatrix}$ For $\lambda_3 = 0$: $(A^T A - 0 I)v_3 = 0$ $\begin{bmatrix} 80 & 100 & 40 \\ 100 & 170 & 140 \\ 40 & 140 & 200 \end{bmatrix} v_3 = 0$ $v_3 = \begin{bmatrix} 2/3 \\ -2/3 \\ 1/3 \end{bmatrix}$ $V = \begin{bmatrix} 1/3 & -2/3 & 2/3 \\ 2/3 & -1/3 & -2/3 \\ 2/3 & 2/3 & 1/3 \end{bmatrix}$ 5. Compute U: $u_i = \frac{1}{\sigma_i} A v_i$ $u_1 = \frac{1}{6} \begin{bmatrix} 4 & 11 & 14 \\ 8 & 7 & -2 \end{bmatrix} \begin{bmatrix} 1/3 \\ 2/3 \\ 2/3 \end{bmatrix} = \begin{bmatrix} 6/6 \\ 12/6 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \frac{1}{\sqrt{5}} = \begin{bmatrix} 1/ \sqrt{5} \\ 2/ \sqrt{5} \end{bmatrix}$ $u_2 = \frac{1}{3} \begin{bmatrix} 4 & 11 & 14 \\ 8 & 7 & -2 \end{bmatrix} \begin{bmatrix} -2/3 \\ -1/3 \\ 2/3 \end{bmatrix} = \begin{bmatrix} -3/3 \\ 6/3 \end{bmatrix} = \begin{bmatrix} -1 \\ 2 \end{bmatrix} \frac{1}{\sqrt{5}} = \begin{bmatrix} -1/ \sqrt{5} \\ 2/ \sqrt{5} \end{bmatrix}$ $U = \begin{bmatrix} 1/ \sqrt{5} & -1/ \sqrt{5} \\ 2/ \sqrt{5} & 2/ \sqrt{5} \end{bmatrix}$ **Note:** If $\sigma_i = 0$, then $u_i$ is any vector orthogonal to other $u_i$'s. ## 2. Low-rank approximation \[The text is truncated in the image.\] If $A$ is an $m \times n$ matrix, then $A = U \Sigma V^T = \sum_{i=1}^{r} \sigma_i u_i v_i^T$, where $r$ is the rank of $A$. $A_k = \sum_{i=1}^{k} \sigma_i u_i v_i^T$ is the best rank $k$ approximation of $A$. $\| A - A_k \|_2 = \sigma_{k+1}$ ### Example \[The text is truncated in the image. The following text is a reasonable reconstruction.\] Let's consider the first example in the above: $A = \begin{bmatrix} 4 & 11 & 14 \\ 8 & 7 & -2 \end{bmatrix}$ $A = U \Sigma V^T = \begin{bmatrix} 1/ \sqrt{5} & -2/ \sqrt{5} \\ 2/ \sqrt{5} & 1/ \sqrt{5} \end{bmatrix} \begin{bmatrix} 18 & 0 & 0 \\ 0 & 3 & 0 \end{bmatrix} \begin{bmatrix} 1/3 & 2/3 & 2/3 \\ -2/3 & -1/3 & 2/3 \\ 2/3 & -2/3 & 1/3 \end{bmatrix}^T$ The rank-1 approximation of $A$ is $A_1 = \sigma_1 u_1 v_1^T = 18 \begin{bmatrix} 1/ \sqrt{5} \\ 2/ \sqrt{5} \end{bmatrix} \begin{bmatrix} 1/3 & 2/3 & 2/3 \end{bmatrix} = \ldots$ $u_i$ = ith column of $U$ $v_i$ = ith column of $V$ $\sigma_i$ = ith diagonal element of $\Sigma$