Singular value decomposition

SVD, pseudoinverse, and PCA: SVD: singular value decomposition

Singular value decomposition

The singular value decomposition of a matrix, abbreviated as SVD, is widely used in statistics (for example, in principal components analysis and in the least-squares method for data regression), in signal processing (e.g., to reduce noise in a signal), and in even more disciplines, such as computer vision and related fields. In this theory page we only discuss what the singular value decomposition is and what it has to do with eigenvalues, but not how to calculate the SVD. In practice you do the computations anyway with numerical software.

We consider an \(m\times n\) matrix \(A\). Then \(A^{\top}\!A\) is a symmetric matrix, and, according to the spectral theorem for symmetric matrices, diagonalizable with real eigenvalues. But in this case holds even more:

The eigenvalues of \(A^{\top}\!A\) are nonnegative.

Let \(\vec{v}\) be an eigenvector of \(A^{\top}\!A\) corresponding to the eigenvalue \(\lambda\). We may assume that \(\lVert\vec{v}\rVert=1\). Then: \[\begin{aligned} 0\le\lVert A\vec{v}\rVert^2 &= (A\vec{v})\boldsymbol{\cdot} (A\vec{v})= (A\vec{v})^{\top}\!A\vec{v}=\vec{v}^{\top}\!A^{\top}\!A\vec{v}\\ &= \vec{v}^{\top}\lambda \vec{v}=\lambda (\vec{v}\boldsymbol{\cdot}\vec{v})=\lambda \lVert\vec{v}\rVert^2=\lambda\end{aligned}\]

So you can take square roots of the eigenvalues.

Let \(A\) be an \(m\times n\) matrix. Then the singular values of \(A\) are the square roots of the eigenvalues of \(A^{\top}\!A\).
Singular values is commonly denoted by \(\sigma_1,\ldots, \sigma_n\) and arranged in descending order, that is, \(\sigma_1\ge \sigma_2\ge \cdots\ge\sigma_n\).

Calculate exactly the singular values of \(A=\matrix{-2 & -2 \\ 1 & -2 \\ 0 & 2 \\ }\).

The matrix \[A^{\top}A= \matrix{-2 & 1 & 0 \\ -2 & -2 & 2 \\ } \matrix{-2 & -2 \\ 1 & -2 \\ 0 & 2 \\ } = \matrix{5 & 2 \\ 2 & 12 \\ }\] has eigenvalues \( \lambda_{1}={{\sqrt{65}+17}\over{2}} , \lambda_{2}={{17- \sqrt{65}}\over{2}} \) (check this!).

Thus, the singular values of \(A\) are \( \sigma_{1}={{\sqrt{\sqrt{65}+17}}\over{\sqrt{2}}} , \sigma_{ 2}={{\sqrt{17-\sqrt{65}}}\over{\sqrt{2}}} \).

New example

Before we can formulate the singular value decomposition we must define the notion of orthogonal matrix.

A real square matrix \(B\) is orthogonal if and only if \(B^{\top}\!B=B\,B^{\top}=I\)

The following properties of a matrix \(B\) are equivalent:

\(B\) is orthogonal.
the rows of \(B\) have length 1 and are mutually perpendicular to each other with respect to the standard dotproduct.
the columns of \(B\) have length 1 and are mutually perpendicular to each other with respect to the standard dotproduct.

Now we can formulate the singular value decomposition in the following way.

Singular value decomposition Let \(A\) be an \(m\times n\) matrix with rank \(r\) and with singular values \(\sigma_1\ge \sigma_2\ge\cdots\sigma_r\gt 0\) and \(\sigma_{r+1}=\sigma_{r+2}=\cdots = \sigma_n=0\). Then, there is an orthogonal \(m\times m\) matrix \(U\), an orthogonal \(n\times n\) matrix \(V\), and an \(m\times n\) matrix \(\Sigma\) with the singular values on the main diagonal in descending order and zeros elsewhere, such that \[A=U\Sigma V^{\top}\] \(\Sigma\) is uniquely determined, but the orthogonal matrices \(U\) and \(V\) not.

You can also write the decomposition with the first \(r\) column vectors \(\vec{u}_1,\ldots,\vec{u}_r\) of the matrix \(U\) and the first \(r\) column vectors \(\vec{v}_1,\ldots,\vec{v}_r\) of the matrix \(V\). Then: \[A=U\Sigma V^{\top}=\sigma_1\vec{u}_1\vec{v}_1^{\top}+ \ldots + \sigma_r\vec{u}_r\vec{v}_r^{\top}\] If \(r<m\) and/or \(r<n\), this gives a more compact description of the singular value decomposition.

\[A=\matrix{2 & 0 \\ 0 & -3}= \matrix{0 & 1\\ 1 & 0} \cdot \matrix{3 & 0 \\ 0 & 2}\cdot \matrix{0 & 1\\ -1 & 0}=U\Sigma V^{\top}\]

\[A=\matrix{1 & 1 \\ 1 & 0 \\ 0 & 1}= \matrix{\tfrac{1}{3}\sqrt{6} & 0 & -\tfrac{1}{3}\sqrt{3}\\ \tfrac{1}{6}\sqrt{6} & -\tfrac{1}{2}\sqrt{2} & \tfrac{1}{3}\sqrt{3} \\ \tfrac{1}{6}\sqrt{6} & \tfrac{1}{2}\sqrt{2} & \tfrac{1}{3}\sqrt{3}}\cdot \matrix{\sqrt{3} & 0 \\ 0 & 1 \\ 0 & 0}\cdot \matrix{\tfrac{1}{2}\sqrt{2} & \tfrac{1}{2}\sqrt{2} \\ -\tfrac{1}{2}\sqrt{2} & \tfrac{1}{2}\sqrt{2}}=U\Sigma V^{\top}\] We also have the following more compact decomposition: \[\begin{aligned}A=\matrix{1 & 1 \\ 1 & 0 \\ 0 & 1} &= \matrix{\tfrac{1}{3}\sqrt{6} & 0 \\ \tfrac{1}{6}\sqrt{6} & -\tfrac{1}{2}\sqrt{2} \\ \tfrac{1}{6}\sqrt{6} & \tfrac{1}{2}\sqrt{2}} \cdot \matrix{\sqrt{3} & 0 \\ 0 & 1 }\cdot \matrix{\tfrac{1}{2}\sqrt{2} & \tfrac{1}{2}\sqrt{2} \\ -\tfrac{1}{2}\sqrt{2} & \tfrac{1}{2}\sqrt{2}} \\ \\ &= \sqrt{3}\cdot \matrix{\tfrac{1}{3}\sqrt{6} \\ \tfrac{1}{6}\sqrt{6} \\ \tfrac{1}{6}\sqrt{6}}\cdot \matrix{\tfrac{1}{2}\sqrt{2} \\ \tfrac{1}{2}\sqrt{2}}^{\top}+ 1\cdot\matrix{0 \\ -\tfrac{1}{2}\sqrt{2} \\ \tfrac{1}{2}\sqrt{2}}\cdot \matrix{-\tfrac{1}{2}\sqrt{2} \\ \tfrac{1}{2}\sqrt{2}}^{\top}\end{aligned}\]