The Singular Value Decomposition

Suppose that $T:V\to W$ is a linear map between inner product spaces. The adjoint $T^{}$of$T$isthelinearmap$T^{}:W\to V$ satisfying $⟨w,Tv⟩=⟨T^{\ast }w,v⟩.$

To see that $T^{}$exists,fix$w$andconsiderthelinearmap$\phi_w:v\mapsto \langle w, Tv\rangle$.Since$\phi_w$belongsto$\Hom(V,F)$,thereisaunique$v’\in V$suchthat$\phi_w(v)=\langle v’,v\rangle$.Then$v’=T^{}w$ by definition. The adjoint has the properties:

• $(S+T{)}^{\ast }=S^{\ast }+T^{\ast }$ and $(aS{)}^{\ast }=\bar{a}{S}^{\ast }$
• $(ST{)}^{\ast }=T^{\ast }{S}^{\ast }$.
• $(T^{\ast }{)}^{\ast }=T$
• $(T^{-1}{)}^{\ast }=(T^{\ast }{)}^{-1}$
• The identity is its own adjoint.

The spectral theorem (over $\mathbb{R}$) applies to self-adjoint operators $T:V\to V$ where $V$ is an inner product space. The singular value decomposition is a generalization to operators $T:V\to W$. So let $V$ and $W$ be real inner product spaces and $T:V\to W$ a linear map.

Let $Q=T^{\ast }T$. Then $Q$ is a map from $V\to V$:

• $Q$ is self-adjoint.
• $⟨Qv,v⟩\ge 0$ for all $v\in V$. A self adjoint operator with this property is called positive.
• The null space of $Q$ is the same as the null space of $T$.
• The range (column space) of $Q$ is the same as the column space of $T^{\ast }$.
• The ranks of $T$, ${}^{\ast }$, and $Q$ all coincide.

Proof:

The key point is that $⟨Qv,v⟩=⟨T^{\ast }Tv,v⟩=⟨Tv,Tv⟩$. So $⟨Qv,v⟩$ is greater than or equal to zero; and if it equals zero then $Tv=0$ and conversely. This proves that $\mathrm{null}(Q)=\text{null}(T)$.

In general:

• null space of $T^{\ast }$ is orthogonal to the range of $T$.
• range of $T^{\ast }$ is orthogonal to the null space of $T$.
• null space of $T$ is orthogonal to the range of $T^{\ast }$.
• range of $T$ is orthogonal to the nullspace of $T^{ast}$.

So since the null space of $Q$ and the null space of $T$ coincide, and $Q$ is self-adjoint, we have: $\mathrm{range}Q=(\mathrm{null}Q{)}^{\perp }=(\mathrm{null}(T){)}^{\perp }=\mathrm{range}(T^{\ast }).$

Also $\dim \mathrm{range}(T)=\dim \mathrm{null}(T^{\ast }{)}^{\perp }=\dim W-\dim \mathrm{null}(T^{\ast })=\dim \mathrm{range}(T^{\ast }).$

Definition: If $T:V\to W$ is a linear operator, then $Q=T^{\ast }T$ is diagonalizable. Let $\mathrm{\Lambda }$ be diagonal the matrix of $Q$ in an orthonomormal basis given by the spectral theorem, with eigenvalues listed in decreasing order. The singular values of $T$ are the entries in ${\mathrm{\Lambda }}^{1/2}$ – the square roots of the eigenvalues of $Q$.

Proposition: (Singular value decomposition) Let $T:V\to W$ be a linear map of inner product spaces with singular values $s_1,\dots ,s_n$. Then there are orthonormal basis $e_1,\dots ,e_n$ and $f_1,\dots ,f_n$ for $V$ and $W$ such that $T(v)=\sum _{i=1}^n{s}_i<v,e_i>f_i$ for all $v\in V$. In matrix terms this basically means that $T$ is “diagonal” in the bases given by the $e$’s and $f$’s (although $T$ needn’t be square).

This is usually written like this for matrices.

Theorem: (SVD) Let $A$ be an $m\times n$ matrix over $\mathbb{R}$. Then there are orthogonal matrices $P$ and $Q$ such that $A=PDQ$ where $P$ is $m\times m$, $Q$ is $n\times n$, and $D$ is $m\times n$. The “diagonal” entries of $D$ are the singular values of $A$.

This is the matrix version of the previous statement.

Proof:

There’s an orthonormal basis of $V$ so that $Q{e}_i={\lambda }_i{e}_i$ where the ${\lambda }_i$ are the eigenvalues of the self-adjoint operator $Q$. For the nonzero eigenvectors $e_i$ for $i=1,\dots ,r$, the vectors $f_i=\frac{T{e}_i}{\sqrt{{\lambda }_i}}$ are orthonormal. We can complete the set of $f_i$ (if needed) to a basis of $W$. Any $v\in V$ can be written $v=\sum _{i=1}^n⟨v,e_i⟩e_i.$ The sought-after formula comes from applying $T$ to this.

---