Singular Value Decomposition (SVD)

Theorem

Let $A$ be a $m\times n$ matrix, there always exists orthonormal matrices $U$ and $V$ such that

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

For some diagonal matrix $\sigma$.

Geometric Interpretation

What this means, is that the transformation described by $A\in m\times n$ will:

1. Take a set of vectors $\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_n}$ in ${\mathbb{R}}^m$
2. Map them to a set of vectors $\overrightarrow{u_1},\overrightarrow{u_2},\dots ,\overrightarrow{u_n}$ in ${\mathbb{R}}^n$
3. And scale them by the corresponding entries in $\Sigma$.

But wait! What happened to the extra $m-n$ dimensions in ${\mathbb{R}}^m$? They get mapped to the zero vector!

Proof

1

Given a $m\times n$ matrix $A$, consider the eigenvalues of $A^{T}A$.

First observation is that $A^{T}A$ is a symmetric matrix. Thus, by EVD. it must have real eigenvalues. Let’s call them ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n$.

Along with the corresponding eigenvectors $\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_n}$.

As we’re only interested in non-zero eigenvalues, let’s assume that ${\lambda }_1,{\lambda }_2,\dots ,{\lambda }_r$ are the non-zero eigenvalues, where $r=\mathrm{rank}(A)$. Of course, it’s possible that $r=n$, but we’ll keep it general for now. This also means that we will only consider the eigenvectors $\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_r}$.

Now, this means we can rewrite our eigenvalues as ${\sigma }_1^2,{\sigma }_2^2,\dots ,{\sigma }_r^2$, where ${\sigma }_i=\sqrt{{\lambda }_i}$.

2

Now let’s define the following

$$U_1=\frac{A{v}_1}{{\sigma }_1},U_2=\frac{A{v}_2}{{\sigma }_2},\dots ,U_r=\frac{A{v}_r}{{\sigma }_r}$$

Additionally, we’ll arbitrarily pick $U_{r+1},U_{r+2},\dots ,U_m$ such that the full set $\{U_1,U_2,\dots ,U_m\}$ is an orthonormal basis for ${\mathbb{R}}^m$.

Note: now we see why we only looked at the non-zero eigenvalues, because we are dividing by $\sigma$

Now, let’s define our matrix $U$ as

$$U=\left[\begin{array}{cccc}{U}_1& U_2& \dots & U_m\end{array}\right]$$

We can also define

$$V=\left[\begin{array}{cccc}{V}_1& V_2& \dots & V_n\end{array}\right]$$

Where $V_i=v_i$ for $i=1,2,\dots ,r$.

Once again, we arbitrarily picked $V_{r+1},V_{r+2},\dots ,V_n$ such that the full set $\{V_1,V_2,\dots ,V_n\}$ is an orthonormal basis for ${\mathbb{R}}^n$.

Thus we can now compute

$$\begin{array}{rl}{U}^{T}AV& =\left[\begin{array}{c}{U}_1^T\\ U_2^T\\ ⋮\\ U_m^T\end{array}\right]A\left[\begin{array}{cccc}{V}_1& V_2& \dots & V_n\end{array}\right]\\ & =\left[\begin{array}{c}{U}_1^T\\ U_2^T\\ ⋮\\ U_m^T\end{array}\right]\left[\begin{array}{cccc}A{V}_1& A{V}_2& \dots & A{V}_n\end{array}\right]\end{array}$$

Now let’s analyze and consider the first entry

$$U_1^T\cdot A{V}_1=U_1^T\cdot {\sigma }_1{U}_1={\sigma }_1(U_1^T\cdot U_1)={\sigma }_1$$

But if we go further we see

$$U_1^T\cdot A{V}_2=U_1^T{\sigma }_2{U}_2=\frac{v_1^T{A}^T}{{\sigma }_1}\cdot {\sigma }_2\frac{A{V}_2}{{\sigma }_2}=\frac{v_1^T{A}^{T}A{V}_2}{{\sigma }_1}$$

But recall, that $v_2$ is an eigenvector of $A^{T}A$ with eigenvalue ${\sigma }_2^2$. Thus, we have

$$\frac{V_1^T{A}^{T}A{V}_2}{{\sigma }_1}=\frac{V_1^T{\lambda }_2{V}_2}{{\sigma }_1}=\frac{{\lambda }_2}{{\sigma }_1}{V}_1^T{V}_2=0$$

As, $V_1$ is orthogonal to $V_2$.

Thus, if we perform the composition, we will get

$$U^{T}AV=\left[\begin{array}{cccc}{\sigma }_1& 0& \dots & 0\\ 0& {\sigma }_2& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & 0\end{array}\right]=\Sigma$$

Where the diagonal is simply ${\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r$ followed by $0$s.

Example

Consider the matrix

$$A=\left[\begin{array}{ccc}3& 2& 2\\ 2& 3& -2\end{array}\right]$$

Thus we then have

$$\begin{array}{rl}{A}^{T}A& =\left[\begin{array}{cc}3& 2\\ 2& 3\\ 2& -2\end{array}\right]\left[\begin{array}{ccc}3& 2& 2\\ 2& 3& -2\end{array}\right]\\ & =\left[\begin{array}{ccc}13& 12& 2\\ 12& 13& -2\\ 2& -2& 8\end{array}\right]\end{array}$$

Then if we compute the eigenvalues of this matrix, we will get

$${\lambda }_1=25,{\lambda }_2=9,{\lambda }_3=0$$

We then define

$${\sigma }_1^2=25,{\sigma }_2^2=9,{\sigma }_3^2=0$$

Corresponding to the eigenvalues are the eigenvectors, note that we need to normalize these vectors.

$$V_1=\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\\ 0\end{array}\right]V_2=\left[\begin{array}{c}\frac{1}{\sqrt{18}}\\ -\frac{1}{\sqrt{18}}\\ \frac{4}{\sqrt{18}}\end{array}\right]V_3=\left[\begin{array}{c}x\\ y\\ z\end{array}\right]$$

We actually don’t need to compute $V_3$ as will become obvious later.

Let’s build out $V$ matrix now

$$V=\left[\begin{array}{ccc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{18}}& x\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{18}}& y\\ 0& \frac{4}{\sqrt{18}}& z\end{array}\right]$$

Additionally, let’s compute our $U$ vectors

$$U_1=\frac{A{V}_1}{{\sigma }_1}=\frac{1}{5}\left[\begin{array}{ccc}3& 2& 2\\ 2& 3& -2\end{array}\right]\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\\ 0\end{array}\right]=\frac{1}{5}\left[\begin{array}{c}\frac{5}{\sqrt{2}}\\ \frac{5}{\sqrt{2}}\end{array}\right]=\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\end{array}\right]$$ $$U_2=\frac{A{V}_2}{{\sigma }_2}=\frac{1}{3}\left[\begin{array}{ccc}3& 2& 2\\ 2& 3& -2\end{array}\right]\left[\begin{array}{c}\frac{1}{\sqrt{18}}\\ -\frac{1}{\sqrt{18}}\\ \frac{4}{\sqrt{18}}\end{array}\right]=\frac{1}{3}\left[\begin{array}{c}\frac{9}{\sqrt{18}}\\ -\frac{9}{\sqrt{18}}\end{array}\right]=\left[\begin{array}{c}\frac{3}{\sqrt{18}}\\ -\frac{3}{3\sqrt{18}}\end{array}\right]=\left[\begin{array}{c}\frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}}\end{array}\right]$$

Thus, our $U$ matrix is

$$U=\left[\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right]$$

We are now done! So we can assert

$$\begin{array}{rl}A& =U\Sigma V^T\\ & =\left[\begin{array}{cc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}& -\frac{1}{\sqrt{2}}\end{array}\right]\left[\begin{array}{ccc}5& 0& 0\\ 0& 3& 0\end{array}\right]\left[\begin{array}{ccc}\frac{1}{\sqrt{2}}& \frac{1}{\sqrt{2}}& 0\\ \frac{1}{\sqrt{18}}& -\frac{1}{\sqrt{18}}& \frac{4}{\sqrt{18}}\\ x& y& z\end{array}\right]\end{array}$$

It follows, that we could’ve just dropped the last column of $V$ and the last row and column of $\Sigma$ as they don’t contribute to the final product. This gives us a simplified form.

Simplified SVD

This is a corollary to the above, but assuming the $A\in m\times n$ we can write

$$A_{m\times n}=U_{m\times m}{\Sigma }_{m\times m}{V}_{m\times n}$$

This is assuming $m\le n$.