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)$.

Proof of the existence of the SVD. Multiple proofs are possible. Let’s look at one of them. Define the matrix

$$B=\left[\begin{array}{cc}0& A\\ A^T& 0\end{array}\right]$$

This matrix is symmetric and therefore is unitarily diagonalizable:

$$B=Q\Lambda Q^T$$

We can restrict this factorization such that $\Lambda$ has only non-zero entries on the diagonal. Assume that $[x;y]$ is an eigenvector of $B$ associated with $\lambda \ne 0$. Then

$$B\left[\begin{array}{c}x\\ -y\end{array}\right]=\left[\begin{array}{cc}0& A\\ A^T& 0\end{array}\right]\left[\begin{array}{c}x\\ -y\end{array}\right]=\left[\begin{array}{c}-Ay\\ A^{T}x\end{array}\right]=-\lambda \left[\begin{array}{c}x\\ -y\end{array}\right]$$

So $-\lambda$ is also an eigenvalue. Since the eigenvectors must be orthogonal we have

$$x^{T}x-y^{T}y=0$$

Let’s normalize our eigenvector such that

$$x^{T}x+y^{T}y=2$$

This implies that $\Vert x{\Vert }_2=\Vert y{\Vert }_2=1$.

Note that since $Ay=\lambda x$ and $A^{T}x=\lambda y$, we have

$$A^{T}Ay={\lambda }^{2}y,A{A}^{T}x={\lambda }^{2}x$$

So ${\lambda }^2$ is an eigenvalue of $A^{T}A$ and $A{A}^T$.

Denote by $X$ all the eigenvectors of $A{A}^T$ and by $Y$ those of $A^{T}A$ (keeping only the non-zero eigenvalues). We have shown that

$$Q=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}X& X\\ Y& -Y\end{array}\right],\Lambda =\left[\begin{array}{cc}\Sigma & 0\\ 0& -\Sigma \end{array}\right]$$

Using

$$\left[\begin{array}{cc}0& A\\ A^T& 0\end{array}\right]=Q\Lambda Q^T$$

we find that

$$A=X\Sigma Y^T$$

This is the SVD of $A$.

$\square$

The SVD is unique if and only if all the singular values are distinct (up to a sign change of columns in $U$ and $V$).

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