Singular Value Decomposition

Definition:

• theorem SVD Decomposition: Any non-zero matrix $A\in {\mathbb{R}}^{m,n}$ can be factored as $A=U\tilde{S}{V}^{⊺}$ where:
  • $V\in {\mathbb{R}}^{n,n}$ and $U\in {\mathbb{R}}^{m.m}$ are orthogonal matrices, ie, $U^{⊺}U=I_m,V^{⊺}V=I_n$
  • $\tilde{S}\in {\mathbb{R}}^{m,n}$ is matrix having the first $r\doteq \text{rank}A$ diagonal entries $({\sigma }_1,...,{\sigma }_r)$ positive and decreasing magnitude and all other entries are 0
    • $\tilde{S}=\left[\begin{array}{cc}S& 0_{r,n-r}\\ 0_{m-r,r}& 0_{m-r,n-r}\end{array}\right],S=diag({\sigma }_1,...,{\sigma }_n)$
• corollary Compact-form SVD:
  • Any matrix non-zero $A\in {\mathbb{R}}^{m,n}$ can be expressed as $A={\sum }_{j=1}^r{\sigma }_i{u}_i{v}_i^{⊺}=U_{r}S{V}_r^{⊺}$ where
    • $r=\text{rank}A$
    • $U_r=[u_1...u_r]$ is such that $U_r^{⊺}{U}_r=I_r$
    • $V_r=[v_1...v_r]$ is such that $V_r^{⊺}{V}_r=I_r$
    • ${\sigma }_1\ge {\sigma }_2\ge ...\ge {\sigma }_r\ge 0$
  • The positive numbers ${\sigma }_i$ are called singular value of $A$
  • Vectors $u_i$ are called the left singular vectors of $A$
  • Vectors $v_i$ are called the right singular vectors of $A$
  • These satisfies $A{v}_i={\sigma }_i{u}_i,A^{⊺}{u}_i={\sigma }_i{v}_i,i=1,...,r$
  • Intepretation:
    • The singular value decomposition theorem allows to write any matrix as a sum of Dyad $A={\sum }_{j=1}^r{\sigma }_i{u}_i{v}_i^{⊺}$ where
      • vectors $u_i,v_i$ are normalized with ${\sigma }_i>0$ providing “strength” of the corresponding dyad
      • the vectors $u_i,i=1,...,r$ (respectively $v_i,i=1,...r$) are mutually orthogonal, ensuring that each dyad represents “new information”

Matrix properties via SVD:

• Rank nullspace and range:
  • The rank of $A$ is also the nb of non-zero entries on the diagonal of $\tilde{S}$
  • Since $r=\text{rank}A$, by Fundamental of Linear Algebra, the dimension of the nullspace of $A$ is $\dim \mathcal{N}(A)=n-r$. An orthogonal basis spanning $\mathcal{N}(A)$ is given by the last $n-r$ collumns of $V$, i.e $\mathcal{N}(A)=\mathcal{R}(V_{nr}),V_{nr}\doteq [u_{r+1}...v_n]$
  • Similarly, an orthonormal basis spanning the range of $A$ is given by the first $r$ columns of $U$, i.e. $\mathcal{R}(A)=\mathcal{R}(U_r)$ $U_r\doteq [u_1...u_r]$
• Matrix norms:
  • The squared Frobenius matrix norm of a matrix $A\in {\mathbb{R}}^{m,n}$ can be defined as $||A|{|}_F^2=\text{trace}{A}^{⊺}A={\sum }_{i=1}^n{\sigma }_i^2$ where ${\sigma }_i$ are the singular values of $A$
    • Hence the squared Frobenius norm is sum of squared of the singular values
  • The $l_2$ induced norm $||A|{|}_2$ is equal to the largest singular value: $||A|{|}_2=\underset{x\ne 0}{\max }\frac{||Ax|{|}_2}{||x|{|}_2}={\sigma }_1$

Solving linear equation via SVD:

• The linear equation $Ax=y$ can be fully analyzed via SVD. If $A=U\sum ^{~}{V}^{⊺}$ is the SVD of A then $Ax=y$ is equivalent to $\sum ^{~}\tilde{x}=\tilde{y}$ where
  • $A\in {\mathbb{R}}^{m,n}$ and $y\in {\mathbb{R}}^m$
  • $\tilde{x}\doteq V^{⊺}x$
  • $\tilde{y}\doteq U^{⊺}y$
• Since $\sum ^{~}$ is a diagonal matrix: $\sum ^{~}=\left[\begin{array}{cc}\sum & 0_{r,n-r}\\ 0_{m-r,r}& 0_{m-r,n-r}\end{array}\right],\sum =\text{diag }({\sigma }_1,...,{\sigma }_r)\succ 0$ , the system $\sum ^{~}\tilde{x}=\tilde{y}$ is simple to solve
  • For $\sum ^{~}\tilde{x}=\tilde{y}$, write ${\sigma }_i{\tilde{x}}_i={\tilde{y}}_i$ for $i=1,...,r$ and $0=\tilde{y}$ for $i=r+1,...,m$
  • 2 cases can occur:
    • If the last $m-r$ components of $\tilde{y}$ are not zero, then the above system is infeasible, and the solution set is empty. This occurs when $y$ is not in range of $A$
    • If $y\in \mathcal{R}(A)$ then the last set of conditions in the above system hold, and we solve for $\tilde{x}$ with the first set of conditions: ${\tilde{x}}_i={\tilde{y}}_i/{\sigma }_i$.
      • The last $n-r$ components of $\tilde{x}$ are free, which corresponds to elements in the nullspace of A.
    • If A is full column rank (its nullspace is reduced to {0}), then there is a unique solution.

Applications:

• Low-rank Approximation
• Latent Semantic Analysis
• Recommendation System
• Matrix Completion