13.1 Singular Value Decomposition

Singular Value Decomposition

A general matrix $A\in {\mathbb{R}}^{m\times n}$ with rank $r=\mathrm{Rank}(A)$ can be decomposed as
$A=U\text{Upsigma}{V}^T$
where $U=\left[\begin{array}{cc}{U}_r& U_{m-r}\end{array}\right]\in {\mathbb{R}}^{m\times m}$ and $V_r=\left[\begin{array}{cc}{V}_r& V_{n-r}\end{array}\right]\in {\mathbb{R}}^{n\times n}$ are square orthonormal matrices whose columns are known respectively as the left singular vectors and right singular vectors of $A$, whereas $\text{Upsigma}=\left[\begin{array}{cc}{\text{Upsigma}}_r& 0_{r\times (n-r)}\\ 0_{(m-r)\times r}& 0_{(m-r)\times (n-r)}\end{array}\right]\in {\mathbb{R}}^{m\times n}$ is a block matrix with ${\Sigma }_r=\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_r)\succ 0$ having positive ordered diagonal entries known as the singular values of $A$, such that for $A{A}^T$ and $A^{T}A$, ${\sigma }_i=\sqrt{{\lambda }_i}$.

The SVD of $A$ can also be rewritten in compact-form, such that
$A=U_r{\Sigma }_r{V}_r^T={\sum }_{i=1}^r{\sigma }_i{\vec{u}}_i{\vec{v}}_i^T,$
where $A{\vec{v}}_i={\sigma }_i{\vec{v}}_i$ and ${\vec{u}}^{T}A={\sigma }_i{\vec{u}}_i^T$.

Intuition

We can geometrically interpret SVD by considering what each component of the decomposition does when considering $A$ as a linear transformation. Take a look at this illustration:

\usepackage{amsmath}
\usepackage{tikz}
\usetikzlibrary{arrows.meta, shapes.geometric, decorations.markings, calc}
 
\begin{document}
\begin{tikzpicture}[scale=1.2, transform shape]
 
% Matrix V^T
\begin{scope}[shift={(1,0)}]
	\draw[thick] (-1.5, 0) -- (1.5, 0);
	\draw[thick] (0, 1.5) -- (0, -1.5);
	\draw[thick, fill=none] (0,0) circle (1) node[scale=1.75, teal, yshift=1.5cm, xshift=-1cm]{$V^T$};
	\draw[->, thick] (0, 0) -- (0.3, 0.95) node[above]{$\vec{v}_2$};
	\draw[->, thick] (0, 0) -- (0.95, -0.3) node[right]{$\vec{v}_1$};
	\node (vt) at (0, -1.5){};
\end{scope}
 
% Matrix Sigma
\begin{scope}[shift={(-3,0)}]
	\draw[thick] (-1.5, 0) -- (1.5, 0);
	\draw[thick] (0, -1.5) -- (0, 1.5);
	\draw[thick, fill=none] (0,0) circle (1) node[scale=1.75, purple, yshift=1.5cm, xshift=-1cm]{$\Sigma$};
	\draw[->, thick, teal] (0, 0) -- (0, 1) node[above right]{$\vec{e}_2$};
	\draw[->, thick, teal] (0, 0) -- (1, 0) node[above right]{$\vec{e}_1$};
	\node (s) at (0, -1.5){};
\end{scope}
 
% Matrix U
\begin{scope}[shift={(-7,0)}]
	\draw[thick] (-1.5, 0) -- (1.5, 0);
	\draw[thick] (0, -1.5) -- (0, 1.5);
	\draw[thick, fill=none] (0,0) ellipse (1 and 0.65) node[scale=1.75, green, yshift=1.5cm, xshift=-1cm]{$U$};
	\draw[->, thick, purple] (0, 0) -- (0, 0.65) node[above right]{$\sigma_2\vec{e}_2$};
	\draw[->, thick, purple] (0, 0) -- (1, 0) node[above right]{$\sigma_1\vec{e}_1$};
	\node (u) at (0, -1.5){};
\end{scope}
 
\begin{scope}[shift={(-11,0)}]
	\draw[thick] (-1.5, 0) -- (1.5, 0);
	\draw[thick] (0, -1.5) -- (0, 1.5);
	\draw[thick, fill=none, rotate=45] (0,0) ellipse (1 and 0.65) node[scale=1.75, yshift=1.5cm, xshift=0.65cm, rotate=-45]{$A=$};
	\draw[->, thick, green, rotate=45] (0, 0) -- (0, 0.65) node[above left, rotate=-45]{$\sigma_2\vec{u}_2$};
	\draw[->, thick, green, rotate=45] (0, 0) -- (1, 0) node[above right, rotate=-45]{$\sigma_1\vec{u}_1$};
	\node (a) at (0, -1.5){};
\end{scope}
 
% Arrows
\draw[->, thick, teal] (vt.south west) to [out=-150,in=-30] (s.south east);
\draw[->, thick, purple] (s.south west) to [out=-150,in=-30] (u.south east);
\draw[->, thick, green] (u.south west) to [out=-150,in=-30] (a.south east);
 
\end{tikzpicture}
\end{document}

We can see from the figure above that there are 3 transformations that take place:

1. Here, $V^T$ transforms each vector such that they return to standard basis (since we are performing an operation on the eigenvectors of A). The singular vector with the largest $\sigma$ lands on the x-axis, the vector with the second-largest $\sigma$ lands on the y-axis, and so on.
2. Then, $\Sigma$ stretches or compresses the vectors by factors corresponding to the roots of their eigenvalues. Additionally, $\text{Upsigma}$ may also add or remove dimensionality.
3. Finally, $U$ rotates the standard basis vectors to align with the left singular vectors.

Additionally, the full SVD is connected to the compact SVD (and therefore outer product SVD) as follows:

$$\begin{array}{rl}U\text{Upsigma}{V}^T& =\left[\begin{array}{cc}{U}_r& U_{m-r}\end{array}\right]\left[\begin{array}{cc}{\text{Upsigma}}_r& 0_{r\times (n-r)}\\ 0_{(m-r)\times r}& 0_{(m-r)\times (n-r)}\end{array}\right]\left[\begin{array}{c}{V}_r^T\\ V_{n-r}^T\end{array}\right]\\ & =\left[\begin{array}{cc}{U}_r& U_{m-r}\end{array}\right]\left[\begin{array}{c}{\text{Upsigma}}_r{V}_r^T\\ 0_{(m-r)\times r}\end{array}\right]\\ & =U_r{\text{Upsigma}}_r{V}_r^T.\end{array}$$

Moreover, the full SVD requires running Gram-Schmidt twice to compute $V_{n-r}$ and $U_{m-r}$, and $\text{Upsigma}$ is non-square. However, $U$ and $V$ are invertible, and there is characterization of null spaces.

Properties

(Condition Number) For $A\in {\mathbb{R}}^{n\times n}$, $\kappa (A)=\frac{{\sigma }_1}{{\sigma }_r}=\Vert A{\Vert }_2\Vert A^{-1}\Vert =\{\begin{array}{ll}+\infty & A\in {\mathbb{S}}^n,\\ k\ge 1& \text{o.w}.\end{array}$

(Squared Frobenius Norm) $\Vert A{\Vert }_F^2=\sum _{i=1}^r{\sigma }_r^2$.

(Spectral Norm) $\Vert A{\Vert }_2^2={\max }^2{\Sigma }_r={\sigma }_1^2={\lambda }_1$.

(Nuclear Norm) $\Vert A{\Vert }_{\ast }=\sum _{i=1}^r{\sigma }_i$

$\mathrm{Col}(U_r)=\mathrm{Col}(A)$

$\mathrm{Col}(V_r)=\mathrm{Row}(A)=\mathrm{Col}(A^T)$

$\mathrm{Col}(U_{m-r})=\mathrm{Null}(A^T)$

Since

$\mathrm{Col}(V_{n-r})=\mathrm{Null}(A)$

$||\vec{x}||\le 1⟺||A\vec{x}||\le {\sigma }_1$ for any $\vec{x}\in {\mathbb{R}}^n$