allenfrostline

Orthonormal Bases for Four Subspaces using Singular Value Decomposition

2019-10-23


The singular value decomposition (SVD) can be used to get orthonormal bases for each of the four subspaces: the column space \(\newcommand{1}[1]{\unicode{x1D7D9}_{\{#1\}}} \newcommand{Corr}{\text{Corr}} \newcommand{E}{\text{E}} \newcommand{Cov}{\text{Cov}} \newcommand{Var}{\text{Var}} \newcommand{span}{\text{span}} \newcommand{bs}{\boldsymbol} \newcommand{R}{\mathbb{R}} \newcommand{rank}{\text{rank}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \newcommand{diag}{\text{diag}} \newcommand{tr}{\text{tr}} \newcommand{braket}[1]{\left\langle#1\right\rangle} \newcommand{C}{\mathbb{C}}C(\bs{A})\), the null space \(N(\bs{A})\), the row space \(C(\bs{A}')\), and the left null space \(N(\bs{A}')\).

In this post, we denote SVD of matrix \(\bs{A}\in\R^{m\times n}\) as

\[ \bs{A} = \bs{U}\bs{\Sigma}\bs{V}' \]

where \(\bs{U}\in\R^{m\times m}\), \(\bs{\Sigma}\in\R^{m\times n}\) and \(\bs{V}\in\R^{n\times n}\). \(\bs{U}\) and \(\bs{V}\) are orthonormal, namely \(\bs{U}'\bs{U}=\bs{V}'\bs{V}=\bs{I}\). \(\bs{\Sigma}\) is diagonal (despite being rectangle), which means all entries \(\sigma_{ij}\) are zero if \(i\neq j\). \(\bs{V}'\) means transposition of \(\bs{V}\). Apart from this regular form, we have full-rank SVD as

\[ \bs{A} = \begin{bmatrix} \bs{U}_r & \hat{\bs{U}}_r \end{bmatrix}\begin{bmatrix} \bs{\Sigma}_r & \bs{O}\\ \bs{O} & \bs{O} \end{bmatrix}\begin{bmatrix} \bs{V}_r & \hat{\bs{V}}_r \end{bmatrix}' = \bs{U}_r\bs{\Sigma}_r\bs{V}_r' \]

where \(r=\rank(A)\); \(\bs{U}_r\in\R^{m\times r}\) is the block consisting of the first \(r\) columns \(\bs{U}\), \(\hat{\bs{U}}_r\in\R^{m\times (m-r)}\) is the complement of \(\bs{U}_r\) from \(\bs{U}\); \(\bs{\Sigma}_r\in\R^{r\times r}\) is the top-left square block of \(\bs{\Sigma}\); \(\bs{V}_r\in\R^{n\times r}\) is the block consisting of the first \(r\) columns \(\bs{V}\), \(\hat{\bs{V}}_r\in\R^{n\times(n-r)}\) is the complement of \(\bs{V}_r\) from \(\bs{U}\). Note that orthonormality still holds for \(\bs{U}_r\) and \(\bs{V}_r\), and that now \(\bs{\Sigma}_r\) is square and invertible.

Columns Space \(C(\bs{A})\)

Claim: \(\bs{U}_r\) forms a basis of \(C(\bs{A})\). We prove it as follows.

Proof. All we need is to show that \(C(\bs{A})=C(\bs{U}_r)\). Left to right: assume \(\bs{a}\in C(\bs{A})\), then we know \(\exists \bs{x}\) s.t.

\[ \bs{a}=\bs{Ax}=\bs{U}_r\bs{\Sigma}_r\bs{V}_r'\bs{x}:= \bs{U}_r\bs{x}^* \in C(\bs{U}_r). \]

Right to left: assume \(\bs{u}\in C(\bs{U}_r)\), then similarly \(\exists \bs{x}\) s.t.

\[ \bs{u} = \bs{U}_r\bs{x} = \bs{A}\bs{V}_r\bs{\Sigma}_r^{-1}\bs{x} := \bs{A}\bs{x}^* \in C(\bs{A}). \]

Therefore, we conclude that \(C(\bs{A})=C(\bs{U}_r)\).Q.E.D.

Row Space \(C(\bs{A}')\)

Claim: \(\bs{V}_r\) gives a basis of \(C(\bs{A}')\).

Proof. Similar to the column space, here we need to prove \(C(\bs{A}')=C(\bs{V}_r)\). In fact, since SVD of \(\bs{A}'\) is merely

\[ \bs{A}' = \bs{V}_r\bs{\Sigma}_r\bs{U}_r', \]

the conclusion follows right away from the previous one.Q.E.D.

Null Space \(N(\bs{A})\)

Claim: \(\bar{\bs{V}}_r\) forms a basis of \(N(\bs{A})\).

Proof. Solving \(\bs{\Sigma}\) from the regular SVD gives

\[ \bs{\Sigma} = \bs{U}'\bs{A}\bs{V} = \begin{bmatrix} \bs{U}_r'\bs{A}\bs{V}_r & \bs{U}_r'\bs{A}\bar{\bs{V}}_r\\ \bar{\bs{U}}_r'\bs{A}\bs{V}_r & \bar{\bs{U}}_r'\bs{A}\bar{\bs{V}}_r \end{bmatrix} = \begin{bmatrix} \bs{\Sigma}_r & \bs{O}\\ \bs{O} & \bs{O} \end{bmatrix} \]

and thus

\[ \begin{bmatrix} \bs{U}_r'\bs{A}\bar{\bs{V}}_r\\ \bar{\bs{U}}_r'\bs{A}\bar{\bs{V}}_r \end{bmatrix} = \begin{bmatrix} \bs{O} \\ \bs{O} \end{bmatrix} \Rightarrow \bs{A}\bar{\bs{V}}_r = \bs{O} \]

which means \(\bar{\bs{V}}_r\in N(\bs{A})\). Meanwhile, since \(\bar{\bs{V}}_r\) is orthonormal with \(\rank(\bar{\bs{V}}_r) = n-r = \dim(N(\bs{A}))\), we conclude that \(\bar{\bs{V}}_r\) forms a basis of \(N(\bs{A})\).Q.E.D.

Left Null Space \(N(\bs{A}')\)

Claim: \(\bar{\bs{U}}_r\) gives a basis of \(N(\bs{A}')\).

Proof. Similar to the null space of \(N(\bs{A})\), if we consider \(\bs{A}'\) in the place of \(\bs{A}\), then we have right away that

\[ \bs{A}'\bar{\bs{U}}_r = \bs{O} \Rightarrow \bar{\bs{U}}_r\in N(\bs{A}') \]

and because \(\rank(\bar{\bs{U}}_r)=m-r=\dim(N(\bs{A}'))\), we conclude that \(\bar{\bs{U}}_r\) forms a basis for the left null space of \(\bs{A}\).Q.E.D.