# Singular Value Decomposition Singular Value Decomposition (SVD) is a matrix factorization method that is applicable to all matrices, including rectangular ones (unlike Eigen-decomposition, for example). ![[SVD visualization.png]] $ \begin{aligned} A=U \Sigma V^{\mathbf{T}}=\left[\begin{array}{ccc} 1 & \mid & \mid \\ \boldsymbol{u}_1 & \boldsymbol{u}_2 & \boldsymbol{u}_3 \\ \mid & \mid & \mid \end{array}\right]\left[\begin{array}{cc} \sigma_1 & \\ & \sigma_2 \\ & \end{array}\right]\left[\begin{array}{c} -\boldsymbol{v}_1^{\mathbf{T}}- \\ -\boldsymbol{v}_2^{\mathbf{T}}- \end{array}\right] & =\sigma_1\left[\begin{array}{c} \mid \\ \boldsymbol{u}_1 \\ \mid \end{array}\right]\left[-\boldsymbol{v}_1^{\mathbf{T}}-\right]+\sigma_2\left[\begin{array}{c} \mid \\ \boldsymbol{u}_2 \\ \mid \end{array}\right]\left[-\boldsymbol{v}_2^{\mathbf{T}}-\right] \\ & =\sigma_1 \boldsymbol{u}_1 \boldsymbol{v}_1^{\mathbf{T}}+\sigma_2 \boldsymbol{u}_2 \boldsymbol{v}_2^{\mathbf{T}} \end{aligned} $ where: - $A \in \mathbb{R}^{m \times n}$ - $U \in \mathbb{R}^{m \times m}$ and $V \in \mathbb{R}^{n \times n}$ are orthogonal matrices - $\Sigma = \text{diag}(\sigma_1, \ldots, \sigma_p) \in \mathbb{R}^{m \times n}$ where $p = \min(m,n)$ - $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_p \geq 0$ (singular values in descending order) Instead of seeing the matrix as a mess of numbers, SVD reveals that any matrix is really just: 1. A rotation/reflection ( $V^T$ ) 2. Followed by pure stretching along perpendicular axes ( $\Sigma$ ) 3. Followed by another rotation/reflection ( $U$ ) This is the "simplest possible" way to understand what any linear transformation actually does. ## Low Rank $ A_k=U D_k V^T, \quad D_k=\operatorname{diag}\left(\sigma_1, \ldots, \sigma_k, 0, \ldots, 0\right) . $ Truncating the matrix A $k<r$ terms gives the best rank- $k$ approximation to $A$ in both the 2 -norm and the Frobenius norm. ## Eigen values Any $n \times m$ matrix $\mathbf{A}$ can be written as $ \mathbf{A}=\mathbf{U \Sigma V}^T, $ where $ \begin{array}{ll} \mathbf{U}=\text { eigenvectors of } \mathbf{A A}^T & n \times n \\ \Sigma=\sqrt{\operatorname{diag}\left(\operatorname{eig}\left(\mathbf{A} \mathbf{A}^T\right)\right)} & n \times m \\ \mathbf{V}=\text { eigenvectors of } \mathbf{A}^T \mathbf{A} & m \times m \end{array} $ ## References 1. The Art of Linear Algebra, Kenji Hirannbe 2021 2. https://www.cs.princeton.edu/~smattw/Teaching/Fa19Lectures/lec11/lec11.pdf