Singular Value Decomposition

Andrew Thangaraj

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\)

Observations about SVD

Notation: as in the proof

  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\}\)

Most numerical computations with matrices start with SVD today!