$ \huge A = U \Sigma V^{\intercal} $ $\large \begin{align} A \in M_{n\times m}\\ U &\in M_{n\times n} \\ \Sigma &\in M_{n\times m}\\ V^{\intercal} &\in M_{m\times m} \end{align} $ [[Singular Value Decomposition]] is that process of decomposing any [[Matrix]] into a [[Orthogonal Matrix|Rotation]] $V^\intercal$, [[Diagonal Matrix|Scale along the cardinal directions]] $\Sigma$, and another [[Rotation Transformation|Rotation]] $U$. Unlike [[Eigendecomposition]], [[Singular Value Decomposition]] can be applied to any $n\times m$ [[Matrix]]. Components: - $U$ is an [[Orthogonal Matrix]] that consists of a [[Orthonormal Basis]] from the [[Eigenvector|Eigenvectors]] $AA^T$ ($AA^T$ is always [[Symmetric Matrix|Symmetric]] therefore its [[Eigenvector|Eigenvectors]] are always [[Orthogonal]]). - $\Sigma$ is a [[Diagonal Matrix]] composed of the [[Eigenvalue|Eigenvalues]] of $A\tpose A$ - $V$ is an [[Orthogonal Matrix]] $\huge \begin{align} A &= U\Sigma V^{\intercal} \\ \end{align} $ $ \huge A \in M_{n\times m} = \mat{ \hat{u}_1 & \cdots & \hat{u}_{m}} \mat{ \sigma_{1} & & \\ & \ddots & \\ & & & \sigma_{n} } \mat{\hat{v}_{1} & \cdots & \hat{v}_{n}}^{\intercal} $ $\hat{v}_{1}$ is the [[Unit Vector]] such that $||A \hat{v}_{1}||$ is __maximal__, with $\sigma_{1}=\norm{ A \hat{v}_{i} }$, and $\hat{u}_{1}$ the direction of $A \hat{v}_{2}$. $\hat{v}_{n}$ is the [[Unit Vector]] such that $\norm{ A \hat{v}_{n} }$ is **minimal**, with $\sigma_{n}=\norm{ A \hat{v}_{n} }$, and $\hat{u}_{n}$ the direction of $A\hat{v}_{n}$. >[!example]- Example problem: > > >![[../../06 Mind Dump/202504070917|202504070917]] ### [[Square Matrix|Non-Square Matrices]] [[Singular Value Decomposition|SVD]] still works on [[Matrix|Matrices]] that are not square because the [[Gram Matrix]] of any matrix is a square matrix. In these cases, $\Sigma$ is not a square matrix. ## Derivation [[Singular Value Decomposition]] can come from the question, for some $A\in M_{n\times n}$ [[Positive Semidefinite Matrix|Positive Semidefinite]] [[Matrix]], what [[Unit Vector]] $\hat{u}\in \R^{n}$ has a *maximal* $\hat{u}^{\intercal}A \hat{u}$? Let $\set{\vec v_{1}, \vec v_{2}, \dots}$ be the [[Orthonormal]] [[Basis]] of $A$ (we can infer because $A$ is [[Positive Semidefinite Matrix|Positive Semidefinite]]). $\large \begin{align} \forall i: \hat{v}_{i}^{\intercal} \hat{v}_{i} &= 1 \\ A\hat{u} &= A\pa{ c_{1} \hat{v}_{1} + c_{2} \hat{v}_{2} + \cdots } \\ &= c_{1} A \hat{v}_{1} + c_{2}A \hat{v}_{2} + \cdots \\ &= c_{1} \lambda_{1} \hat{v}_{1} + c_{2} \lambda_{2} \hat{v}_{2} + \cdots \\ \hat{u}^{\intercal}A \hat{u} &= \pa{ c_{1} \hat{v}_{1} + \cdots }\pa{c_{1} \lambda_{1} \hat{v}_{1} + c_{2} \lambda_{2} \hat{v}_{2} + \cdots} \\ &= c_{1} \hat{v}_{1}^{\intercal}(c_{1} \lambda_{1} \hat{v}_{1}) + \cdots \\ &= c_{1}^{2} \lambda_{1} + c_{2}^{2} \lambda_{2} + \cdots \end{align} $ $c^{2}_{1}$ is maximized as $\hat v_{i}$ is ordered from largest to smallest eigenvalue. This means for a [[Positive Semidefinite Matrix]], the vector with maximal growth is the unit [[Eigenvector]] with largest [[Eigenvalue]]. For another matrix $A\in M_{n\times n}$ (not necessarily [[Symmetric Matrix|Symmetric]], but still a [[Square Matrix]]), which unit vector $\hat{v} \in \R^{n}$ maximizes $||A \hat{v}||_{2}$? $\huge \begin{align} \norm{ A \hat{v} } ^{2} &= \pa{A \hat{v}}^{\intercal} \pa{A \hat{v}} \\ &= \hat{v} ^{\intercal} \underbrace{A^{\intercal} A}_{\text{Gram}} \hat{v} \\ \end{align}$ Note that the [[Gram Matrix]] of $A$, $A^{\intercal}A$ is a [[Symmetric Matrix|Symmetric]] [[Positive Semidefinite Matrix]]. Let $\set{\hat{v}_{1}, \dots, \hat{v}_{n}}$ be [[Orthonormal]] [[Eigenvector|Eigenvectors]] of $A\tpose A$. Let $\lambda_{1},\dots,\lambda_{n}$ be their ordered [[Eigenvalue|Eigenvalues]]. Let $V$ be the [[Orthogonal Matrix]] composed of the [[Eigenvector|Eigenvectors]] of $A \tpose A$. $\huge \begin{align} A\tpose A &= (U \Sigma V \tpose )\tpose (U \Sigma V \tpose ) \\ &= (V \tpose ) \tpose \Sigma U\tpose U \Sigma V \tpose \\ &= V(\Sigma \tpose \Sigma) V\tpose \\ &= V \Sigma^{2} V^{{-1}} \end{align} $ Which is the [[Eigendecomposition|Diagonalisation]] of the [[Gram Matrix]] of $A$. $ \large \begin{align} \Sigma &= \mat{ \sqrt{ \lambda_{1} } & & \\ & \sqrt{ \lambda_{2} } & \\ & & & \ddots } \\ \let \sigma_{i} &= \sqrt{ \lambda_{i} } \end{align} $ Which means $\sigma_{i}$ is an [[Eigenvalue]] of $A\tpose A$. $ \huge \begin{align} A \hat{v}_{i} &= U \Sigma^{2} U \tpose \\ V &= \mat{\hat{v}_{1}& \cdots \hat{v}_{n}} \\ V\hat{e}_{i} &= \hat{v}_{i} \\ V^{{-1}} \hat{v}_{i} &= \hat{e}_{i} \\ U \Sigma V^{\intercal} \hat{v}_{i} &= U \Sigma \hat{e}_{i} \\ &= U \sigma_{i} \hat{e}_{i} \\ &= \sigma_{i} U \hat{e}_{i} \\ &= \sigma_{i} \hat{u}_{i} \end{align} $