SVD Decomposition

We begin this section with an important definition.

Singular Value Decomposition (SVD) can be thought of as a generalization of orthogonal diagonalization of a symmetric matrix to an arbitrary \(m\times n\) matrix. This decomposition is the focus of this section.

The following is a useful result that will help when computing the SVD of matrices.

Suppose \(A\) is an \(m\times n\) matrix, and suppose that \(\lambda \) is a nonzero eigenvalue of \(A^TA\). Then there exists a nonzero vector \(\vec {x} \in \RR ^n\) such that

\begin{equation}\label {nonzero} (A^TA)\vec {x}=\lambda \vec {x} \end{equation}
Multiplying both sides of this equation by \(A\) yields:
\begin{eqnarray*} A(A^TA)\vec {x} & = & A\lambda \vec {x}\\ (AA^T)(A\vec {x}) & = & \lambda (A\vec {x}) \end{eqnarray*}

Since \(\lambda \neq 0\) and \(\vec {x}\neq 0_n\), \(\lambda \vec {x}\neq 0_n\), and thus by equation (nonzero), \((A^TA)\vec {x}\neq 0_m\); thus \(A^T(A\vec {x})\neq 0_m\), implying that \(A\vec {x}\neq 0_m\).

Therefore \(A\vec {x}\) is an eigenvector of \(AA^T\) corresponding to eigenvalue \(\lambda \). An analogous argument can be used to show that every nonzero eigenvalue of \(AA^T\) is an eigenvalue of \(A^TA\), thus completing the proof.

Given an \(m\times n\) matrix \(A\), we will see how to express \(A\) as a product

\[ A=U\Sigma V^T\]

where

  • \(U\) is an \(m\times m\) orthogonal matrix whose columns are eigenvectors of \(AA^T\).
  • \(V\) is an \(n\times n\) orthogonal matrix whose columns are eigenvectors of \(A^TA\).
  • \(\Sigma \) is an \(m\times n\) matrix whose only nonzero values lie on its main diagonal, and are the singular values of \(A\).

How can we find such a decomposition? We are aiming to decompose \(A\) in the following form:

\begin{equation*} A=U\left [ \begin{array}{cc} \sigma & 0 \\ 0 & 0 \end{array} \right ] V^T \end{equation*}

where \(\sigma \) is a block matrix of the form

\[ \sigma =\left [ \begin{array}{ccc} \sigma _{1} & & 0 \\ & \ddots & \\ 0 & & \sigma _{k} \end{array} \right ] \]

Thus \(A^T=V\left [ \begin{array}{cc} \sigma & 0 \\ 0 & 0 \end{array} \right ] U^T\) and it follows that

\begin{equation*} A^TA=V\left [ \begin{array}{cc} \sigma & 0 \\ 0 & 0 \end{array} \right ] U^TU\left [ \begin{array}{cc} \sigma & 0 \\ 0 & 0 \end{array} \right ] V^T=V\left [ \begin{array}{cc} \sigma ^{2} & 0 \\ 0 & 0 \end{array} \right ] V^T \end{equation*}

and so \(A^TAV=V\left [ \begin{array}{cc} \sigma ^{2} & 0 \\ 0 & 0 \end{array} \right ] .\) Similarly, \(AA^TU=U\left [ \begin{array}{cc} \sigma ^{2} & 0 \\ 0 & 0 \end{array} \right ] .\) Therefore, you would find an orthonormal basis of eigenvectors for \(AA^T\) make them the columns of a matrix such that the corresponding eigenvalues are decreasing. This gives \(U.\) You could then do the same for \(A^TA\) to get \(V\).

We formalize this discussion in the following theorem.

There exists an orthonormal basis, \(\left \{ \vec {v}_{1}, \dots , \vec {v}_n\right \}\) such that \( A^TA\vec {v}_{i}=\sigma _{i}^{2}\vec {v}_{i}\) where \(\sigma _{i}^{2}>0\) for \(i=1,\dots ,k,\left ( \sigma _{i}>0\right ) \) and equals zero if \(i>k.\) Thus for \(i>k,\) \(A\vec {v}_{i}=\vec {0}\) because

\begin{equation*} A\vec {v}_{i}\dotp A\vec {v}_{i} = (A\vec {v}_i)^T(A\vec {v}_i)=\vec {v}_i^T(A^TA\vec {v}_i)=\vec {0} \end{equation*}
For \(i=1,\dots ,k,\) define \(\vec {u}_{i}\in \RR ^{m}\) by
\begin{equation*} \vec {u}_{i}= \sigma _{i}^{-1}A\vec {v}_{i} \end{equation*}
Thus \(A\vec {v}_{i}=\sigma _{i}\vec {u}_{i}.\) Now
\begin{eqnarray*} \vec {u}_{i} \dotp \vec {u}_{j} &=& \sigma _{i}^{-1}A \vec {v}_{i} \dotp \sigma _{j}^{-1}A\vec {v}_{j} = \sigma _{i}^{-1}\vec {v}_{i}^T \sigma _{j}^{-1}A^TA\vec {v}_{j} \\ &=& \sigma _{i}^{-1}\vec {v}_{i} \dotp \sigma _{j}^{-1}\sigma _{j}^{2} \vec {v}_{j} = \frac {\sigma _{j}}{\sigma _{i}}\left ( \vec {v}_{i} \dotp \vec {v}_{j}\right )\end{eqnarray*}

This means that \(\vec {u}_{i} \dotp \vec {u}_{j}=1\) when \(i=j\) and \(\vec {u}_{i} \dotp \vec {u}_{j}=0\) when \(i\neq j\). Thus \(\left \{ \vec {u}_{1}, \dots , \vec {u}_{k}\right \}\) is an orthonormal set of vectors in \(\RR ^{m}.\) Also,

\begin{equation*} AA^T\vec {u}_{i}=AA^T\sigma _{i}^{-1}A\vec {v}_{i}=\sigma _{i}^{-1}AA^TA\vec {v}_{i}=\sigma _{i}^{-1}A\sigma _{i}^{2}\vec {v} _{i}=\sigma _{i}^{2}\vec {u}_{i} \end{equation*}
Now, using Gram-Schmidt, extend \(\left \{ \vec {u}_{1}, \dots , \vec {u}_{k}\right \}\) to an orthonormal basis for all of \(\RR ^{m},\left \{ \vec {u}_{1},\dots ,\vec {u}_{m}\right \}\) and let
\begin{equation*} U= \left [ \begin{array}{ccc} \vec {u}_{1} & \cdots & \vec {u}_{m} \end{array} \right ] \end{equation*}
while \(V= \left [ \begin{array}{ccc} \vec {v}_{1} & \cdots & \vec {v}_{n}\end{array}\right ] .\) Thus \(U\) is the matrix which has the \(\vec {u}_{i}\) as columns and \(V\) is defined as the matrix which has the \(\vec {v}_{i}\) as columns. Then
\begin{equation*} U^TAV=\left [ \begin{array}{c} \vec {u}_{1}^T \\ \vdots \\ \vec {u}_{k}^T \\ \vdots \\ \vec {u}_{m}^T \end{array} \right ] A \left [ \begin{array}{ccc} \vec {v}_{1} & \cdots & \vec {v}_{n}\end{array}\right ] \end{equation*}
\begin{equation*} =\left [ \begin{array}{c} \vec {u}_{1}^T \\ \vdots \\ \vec {u}_{k}^T \\ \vdots \\ \vec {u}_{m}^T \end{array} \right ] \left [ \begin{array}{cccccc} \sigma _{1}\vec {u}_{1} & \cdots & \sigma _{k}\vec {u}_{k} & \vec {0} & \cdots & \vec {0} \end{array} \right ] =\left [ \begin{array}{cc} \sigma & 0 \\ 0 & 0 \end{array} \right ] \end{equation*}
where \(\sigma \) is given in the statement of the theorem.

The SVD has as an immediate corollary which is given in the following interesting result.

Let’s compute the SVD of a simple matrix.

Here is another example.

Consider another example.

This illustrates that if you have a good way to find the eigenvectors and eigenvalues for a Hermitian matrix which has nonnegative eigenvalues, then you also have a good way to find the SVD of an arbitrary matrix.

Practice Problems

If \(A\) is a square matrix, show that \(|\text {det}(A)|\) is the product of the singular values of \(A\).
Find an SVD for each of the following matrices.
\[A=\begin{bmatrix}1 & -1\\0 & 1\\1 & 0\end{bmatrix},\quad B=\begin{bmatrix}1 & 1 & 1\\-1 & 0 & -2\\1 & 2 & 0\end{bmatrix}\]
Find an SVD for \(A=\begin{bmatrix}0 & 1\\-1 & 0\end{bmatrix}\).

Text Source

This section was adapted from Section 8.11 of Keith Nicholson’s Linear Algebra with Applications. (CC-BY-NC-SA)

W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition.