Singular value decomposition

One of the most important matrix decompositions in data science and machine learning.

Eigenvalues are great for understanding $A^n$. Does it grow? Does it shrink? How can it be easily modeled?

But it says nothing about the size of $Ax$. How is $A$ transforming $x$ and rescaling the vector?

Because $A$ is a matrix, multiple scales are involved when applying $A$. These scales can be represented systematically using the singular value decomposition.

$$A=U\Sigma V^T$$

• $A$: $m\times n$.
• $U$: orthogonal, $m\times m$. Left singular vectors
• $V$: orthogonal, $n\times n$. Right singular vectors
• $\Sigma$: $m\times n$, diagonal matrix with real positive entries = pure scaling = singular values.

• $A{v}_i={\sigma }_i{u}_i$

Consider a ball $B$ in $R^n$. $A$ transforms this ball into an ellipsoid.

• $Ax=U\Sigma V^{T}x$:
  • $V^{T}x$: point on the unit ball
  • $\Sigma (V^{T}x)$: point on an ellipsoid; the axes are aligned with the coordinate axes.
  • $U(\Sigma V^{T}x)$: rotate/reflect the ellipsoid.

The lengths of the axes of this ellipsoid are the singular values of $A$.

As we can expect, the size of a matrix can be related to its singular values:

$$\Vert A{\Vert }_2={\sigma }_1(A),\Vert A{\Vert }_F=\sqrt{\sum _{i=1}^p{\sigma }_i^2}$$

We can also define a new operator norm using the SVD, the Schatten $p$-norm:

$$\Vert A{\Vert }_p^{\text{Schatten}}=\Vert ({\sigma }_1,\dots ,{\sigma }_r){\Vert }_p$$

where $r$ is the rank and $\Vert {\Vert }_p$ is the vector $p$-norm.

The four fundamental spaces. Assume $A$ is $m\times n$. $r$: number of non-zero singular values = rank of the matrix. Then:

$$\begin{array}{rl}N(A)& =\{v_{r+1},\dots ,v_n\}\\ R(A)& =\{u_1,\dots ,u_r\}\\ N(A^T)& =\{u_{r+1},\dots ,u_m\}=R(A{)}^{\perp }\\ R(A^T)& =\{v_1,\dots ,v_r\}=N(A{)}^{\perp }\end{array}$$

We recover the four fundamental spaces and the rank-nullity theorem.

Connection with eigenvalues. The eigenvalues of $A{A}^T$ and $A^{T}A$ are equal to ${\sigma }_1^2,$ …, ${\sigma }_r^2,$ or 0. The eigenvectors of $A{A}^T$ are given by $U$, and those of $A^{T}A$ by $V$:

$$A{A}^T=U{\Sigma }^2{U}^T,A^{T}A=V{\Sigma }^2{V}^T$$

The computational cost of computing the singular value decomposition is $O(n^3)$.

The four fundamental spaces, Eigenvalues, Operator and matrix norms, Orthogonal matrix and projector