# Singular Value Decomposition

Aug-Nov 2020

## Recap

• Vector space $V$ over a scalar field $F= \mathbb{R}$ or $\mathbb{C}$
• $m\times n$ matrix A represents a linear map $T:F^n\to F^m$
• dim null $T+$ dim range $T=$ dim $V$
• Solution to $Ax=b$ (if it exists): $u+$ null$(A)$
• Four fundamental subspaces of a matrix
• Column space, row space, null space, left null space
• Eigenvalue $\lambda$ and Eigenvector $v$: $Tv=\lambda v$
• There is a basis w.r.t. which a linear map is upper-triangular
• If there is a basis of eigenvectors, linear map is diagonal w.r.t. it
• Inner products, norms, orthogonality and orthonormal basis
• There is an orthonormal basis w.r.t. which a linear map is upper-triangular
• Orthogonal projection: distance from a subspace
• Adjoint of a linear map: $\langle Tv,w\rangle=\langle v,T^*w\rangle$
• null $T=$ $($range $T^*)^{\perp}$
• Self-adjoint: $T=T^*$, Normal: $TT^*=T^*T$
• Complex/real spectral theorem: $T$ is normal/self-adjoint $\leftrightarrow$ orthonormal basis of eigenvectors
• Positive operators: self-adjoint with non-negative eigenvalues
• Isometries: normal with absolute value 1 eigenvalues
• Singular values/vectors of $T$: Eigenvalues/eigenvectors of $T^*T$

## Preliminaries

Unitary matrix

$n\times n$ matrix $V$ is said to be unitary if its columns are orthonormal.

1. Unitary matrices represent isometries

2. $VV^*=V^*V=I$ ($V^*$ is conjugate-transpose)

Rectangular diagonal matrices

$m\times n$ matrix $D$ with $(i,j)$-th element $d_{ij}$

Main diagonal of $D$: $(1,1),(2,2),\ldots$

$D$ is diagonal if the only nonzero values of $D$ are on the main diagonal

## Singular Value Decomposition (SVD)

$A$: $m\times n$ matrix

Singular values: eigenvalues of $A^*A$ or $AA^*$

Right-singular vectors: orthonormal eigenvectors of $A^*A$

Left-singular vectors: orthonormal eigenvectors of $AA^*$

SVD: There exist

1. an $m\times m$ unitary matrix $U$
2. an $n\times n$ unitary matrix $V$
3. an $m\times n$ diagonal matrix $D$

such that $A=UDV^*$.

$U$: columns are left-singular vectors

$V$: columns are right-singular vectors

$D$: singular values on main diagonal

## Example

$A=\begin{bmatrix}1&2&3\\4&5&6\end{bmatrix}$ (standard basis)

Singular values of $A$: $\sigma_1=9.508$, $\sigma_2=0.773$, $\sigma_3=0$

Right-singular vectors of $A$: $e_1=(0.429,0.566,0.704)$, $e_2=(0.805,0.112,-0.581)$, $e_3=(0.408,-0.816,0.408)$

Left-singular vectors of $A$: $f_1=(0.386,0.922)$, $f_2=(-0.922,0.386)$

$A=\begin{bmatrix} 0.386&-0.922\\ 0.922&0.386 \end{bmatrix}\begin{bmatrix} 9.508&0&0\\ 0&0.773&0 \end{bmatrix}\begin{bmatrix} 0.429&0.566&0.704\\ 0.805&0.112&-0.581\\ 0.408&-0.816&0.408 \end{bmatrix}$

Basis for $\mathbb{R}^3$: $e_1$, $e_2$, $e_3$; Basis for $\mathbb{R}^2$: $f_1$, $f_2$

$A$ in above basis: $\begin{bmatrix} 9.508&0&0\\ 0&0.773&0 \end{bmatrix}$ (diagonal)

## SVD: a restatement

$T:V\to W$, linear map

$B_V$: basis of $V$, $B_W$: basis of $W$

$M(T,B_V,B_W)$: matrix of $T$ w.r.t. $B_V$ and $B_W$

SVD: There exist

1. an orthonormal basis $B_V$ for $V$, and
2. an orthonormal basis $B_W$ for $W$

such that $M(T,B_V,B_W)$ is diagonal.

$B_V$: right-singular vectors; $B_W$: left-singular vectors

$M(T,B_V,B_W)$: singular values on diagonal

## Proof of SVD

Lemma: For $v\in V$, $\lVert Tv\rVert=\lVert\sqrt{T^*T}v\rVert$

Proof of Lemma

\begin{align} \langle Tv,Tv\rangle &= \langle T^*Tv,v\rangle\\ &= \langle \sqrt{T^*T}\sqrt{T^*T}v,v\rangle\\ &= \langle \sqrt{T^*T}v,\sqrt{T^*T}v\rangle\\ \end{align}

range $T=\{Tv:v\in V\}$, range $\sqrt{T^*T}=\{\sqrt{T^*T}v:v\in V\}$

Let $S:$ range $\sqrt{T^*T}\to$ range $T$ be s.t. $\sqrt{T^*T}v$ is mapped to $Tv$

Properties of $S$

1. $S$ is well-defined. If $\sqrt{T^*T}v_1=\sqrt{T^*T}v_2$, then $Tv_1=Tv_2$.

2. $S$ is linear. $S$ is one-to-one and onto.

3. For $u\in$ range $\sqrt{T^*T}$, $\lVert u\rVert=\lVert Su\rVert$.

4. For $u_1,u_2\in$ range $\sqrt{T^*T}$, $\langle u_1,u_2\rangle=\langle Su_1,Su_2\rangle$.

## Proof of SVD (continued)

$\{e_1,\ldots,e_n\}$: orthonormal eigenvector basis of $\sqrt{T^*T}$ (and $T^*T$)

$\sigma_1,\ldots,\sigma_n$: corresponding eigenvalues or singular values of $T$

Suppose $k=$ rank $\sqrt{T^*T}$; $\sigma_1$ to $\sigma_k$: nonzero.

$\{\sqrt{T^*T}e_1,\ldots,\sqrt{T^*T}e_k\}$: orthogonal basis of range $\sqrt{T^*T}$

$\{Te_1,\ldots,Te_k\}$: orthogonal basis of range $T$ (by Property 4)

$\sigma_i=\lVert\sigma_ie_i\rVert=\lVert\sqrt{T^*T}e_i\rVert=\lVert Te_i\rVert$

$\{f_1=\dfrac{1}{\sigma_1}Te_1,\ldots,f_k=\dfrac{1}{\sigma_k}Te_k\}$: orthonormal basis of range $T$

$\{f_1,\ldots,f_k,\ldots,f_m\}$: orthonormal extension to basis of $W$

$T$: diagonal w.r.t. basis $\{e_1,\ldots,e_n\}$ for $V$ and $\{f_1,\ldots,f_m\}$ for $W$

Singular values on diagonal

$TT^*f_i=\dfrac{1}{\sigma_i}TT^*Te_i=\dfrac{1}{\sigma_i}T(\sigma_i^2e_i)=\sigma_i^2f_i$

1. $T\leftrightarrow \sigma_1f_1\overline{e^T_1}+\cdots+\sigma_kf_k\overline{e^T_k}$
2. rank $T$: number of nonzero singular values
3. range $T$: orthonormal basis is $\{f_1,\ldots,f_k\}$
4. null $T$: orthonormal basis is $\{e_{k+1},\dots,e_n\}$