NLA MT25, Singular value decomposition
- Course - Numerical Linear Algebra MT25U
- Notes - NLA MT25, Eigenvalue decompositionU
- The majority of results about SVD are contained in:
- Notes - Numerical Analysis HT24, Singular value decompositionU
- See also:
- Notes - Machine Learning MT23, Singular value decompositionU
Flashcards
@State the SVD theorem (in the thin form, with a remark on the full form).
Suppose $A \in \mathbb R^{m \times n}$ is a matrix with $m \ge n$. Then $A$ has the thin SVD decomposition
\[A = U \Sigma V^\top\]where:
- $U \in \mathbb R^{m \times n}$ has orthonormal columns (the “left singular vectors”), so $U^\top U = I _ n$ but $UU^\top \ne I _ m$ in general.
- $V \in \mathbb R^{n \times n}$ is orthogonal (the “right singular vectors”), so $V^\top V = V V^\top = I _ n$.
- $\Sigma = \text{diag}(\sigma _ 1, \ldots, \sigma _ n) \in \mathbb R^{n \times n}$
- $\sigma _ 1 \ge \cdots \ge \sigma _ n \ge 0$ (the “singular values”)
The full SVD instead takes $U \in \mathbb R^{m \times m}$ orthogonal (filling in $U _ \perp \in \mathbb R^{m \times (m-n)}$ such that $[U \mid U _ \perp]$ is square orthogonal) and $\Sigma \in \mathbb R^{m \times n}$ rectangular with diagonal $\sigma _ 1, \ldots, \sigma _ n$ and zero rows below.
The ∆svd-theorem states that every matrix $A$ has the decomposition
\[A = U \Sigma V^\top\]
where:
- The columns of $U$ are the “left singular vectors”
- The columns of $V$ are the “right singular vectors”
- $U^\top U = V^\top V = I _ n$
- $\Sigma = \text{diag}(\sigma _ 1, \ldots, \sigma _ n)$
- $\sigma _ 1 \ge \cdots \ge \sigma _ n \ge 0$ (the “singular values”)
How can you interpret this geometrically?
Any matrix can be thought of as a rotation / reflection, followed by a magnification / shrinkage, followed by another rotation / reflection.
Example SVD calculations
Find the SVD of
\[A = \begin{bmatrix}
-1 & -2 \\
2 & 1 \\
1 & 0 \\
0 & 1
\end{bmatrix}\]
Compute the Gram matrix:
\[A^\top A = \begin{bmatrix} 6 & 4 \\ 4 & 6 \end{bmatrix}\]Calculate the eigenvalues:
\[\chi _ A(\lambda) = (\lambda - 6)^2 - 4^2 = 0\]so eigenvalues are $10$ and $2$.
Calculate eigenvector matrix:
\[V = \frac{1}{\sqrt 2} \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}\]Hence
\[A^\top A = V \Sigma^2 V^\top\]where
\[\Sigma^2 = \begin{bmatrix} 10 & \\ & 2 \end{bmatrix}\]Calculate $U$:
\[U = AV\Sigma^{-1} = \begin{bmatrix} -3/\sqrt{20} & -1/2 \\ \phantom{-}3/\sqrt{20} & -1/2 \\ \phantom{-}1/\sqrt{20} & -1/2 \\ \phantom{-}1/\sqrt{20} & \phantom{-}1/2 \end{bmatrix}\]Properties of the SVD
Many of these are proved and stated in Notes - Numerical Analysis HT24, Singular value decompositionU.
@Prove the ∆svd-properties, e.g. that if $A$ has the singular value decomposition
\[A = U\Sigma V^\top\]
then:
- The rank $r$ of $A$ is the number of non-zero singular values of $A$, which is the number of non-zero entries in $\Sigma$
- A basis for the column space of $A$ is given by the first $r$ columns of $U$
- A basis for the column space of $A^\top$ is given by the first $r$ columns of $V$
- A basis for the null space of $A$ is given by the last $n - r$ columns of $V$
- A basis for the null space of $A^\top$ is given by the last $n - r$ columns of $U$
(Property 1) The rank $r$ of $A$ is the number of non-zero singular values of $A$, which is the number of non-zero entries in $\Sigma$:
Since $U$ and $V$ are invertible, we have $\text{rank}(A) = \text{rank}(\Sigma) = r$.
(Property 2) A basis for the column space of $A$ is given by the first $r$ columns of $U$:
For any $x \in \mathbb R^n$, we have $Ax = U \Sigma V^\top x = U \Sigma y$ where $y = V^\top x$. Hence $\Sigma y = (\sigma _ 1 y _ 1, \ldots, \sigma _ r y _ r, 0, \ldots, 0)^\top$, so
\[Ax = \sum^r _ {i = 1} \sigma _ i y _ i u _ i\]and hence $\text{col}(A) \subseteq \text{span}(u _ 1, \ldots, u _ r)$.
To see the other inclusion, note that as $V^\top$ is bijective, $y$ ranges over all of $\mathbb R^n$ as $x$ varies and so $y _ 1, \ldots, y _ r$ can be chosen freely. As $\sigma _ i \ne 0$ for $i \le r$, each $u _ i$ is attainable, giving $\text{span}(u _ 1, \ldots, u _ r) \subseteq \text{col}(A)$.
(Property 3) A basis for the column space of $A^\top$ is given by the first $r$ columns of $V$:
Apply Property 2 to $A^\top$.
(Property 4) A basis for the null space of $A$ is given by the last $n - r$ columns of $V$:
We have
\[\begin{aligned} Ax = 0 &\iff U \Sigma V^\top x = 0 \\ &\iff \Sigma V^\top x = 0 \\ \end{aligned}\]as $U$ is invertible. Setting $y = V^\top x$, it follows $\Sigma y = 0$, i.e. $\sigma _ i y _ i = 0$ for all $i$. Hence
\[y _ 1 = \cdots = y _ r = 0\]since $\sigma _ i \ne 0$ for $i \le r$ and we are free to choose $y _ {r+1}, \ldots, y _ n$. Hence $y \in \text{span}(e _ {r+1}, \ldots, e _ n)$, and since $x = V y$, it follows
\[x \in V \text{span}(e _ {r+1}, \ldots, e _ n) = \text{span}(v _ {r+1}, \ldots, v _ n)\](Property 5) A basis for the null space of $A^\top$ is given by the last $n - r$ columns of $U$:
Apply Property 4 to $A^\top$.
@Prove that if $A \in \mathbb R^{m \times n}$ with SVD $A = U \Sigma V^\top$, then:
- $V$ is an eigenvector matrix of $A^\top A$
- $U$ is an eigenvector matrix of $A A^\top$
- $\sigma _ i = \sqrt{\lambda _ i (A^\top A)}$
For (1), note that
\[\begin{aligned} A^\top A &= (U \Sigma V^\top)^\top (U \Sigma V^\top) \\ &= V \Sigma U^\top U \Sigma V^\top \\ &= V(\Sigma^\top \Sigma) V^\top \end{aligned}\]Now $\Sigma^\top \Sigma \in \mathbb R^{n \times n}$ is diagonal with entries $\sigma^2 _ i$. This is an eigendecomposition of $A^\top A$, establishing (1) and (3).
For (2), we have similarly
\[\begin{aligned} A A^\top &= U \Sigma V^\top V \Sigma^\top U^\top \\ &= U(\Sigma \Sigma^\top) U^\top \end{aligned}\]This gives an eigendecomposition of $AA^\top$, as required.
Suppose that $A$ is normal. @State a result about the connection between its eigenvalues $\lambda _ i$ and its singular values $\sigma _ i$.
@Prove that if $A \in \mathbb C^{n \times n}$ is normal, then
\[\sigma _ i(A) = \vert \lambda _ i(A) \vert \]
As $A$ is normal, its Schur decomposition $A = U D U^\ast$ has $D$ diagonal by ∆diagonal-schur-iff-normal, with the diagonal entries of $D$ equal to the eigenvalues $\lambda _ i$.
Since $D$ is diagonal, $D^\ast D$ is diagonal with entries $ \vert \lambda _ i \vert ^2$. Since $D = U^\ast A U$,
\[D^\ast D = U^\ast A^\ast UU^\ast A U = U^\ast A^\ast A U\]it follows $D^\ast D$ is a unitary diagonalisation of $A^\ast A$ and hence the eigenvalues of $A^\ast A$ are $ \vert \lambda _ i \vert ^2$, and the singular values are $\sigma _ i = \vert \lambda _ i \vert $.
Suppose that $A$ is symmetric. @State a result about the connection between its eigenvalues $\lambda _ i$ and its singular values $\sigma _ i$ and quickly @justify why it is true by appealing to another theorem.
This follows from the more general fact this is true for all normal matrices.
Suppose that $A$ is unitary. @State a result about the connection between its eigenvalues $\lambda _ i$ and its singular values $\sigma _ i$ and quickly @justify why it is true by appealing to another theorem.
This follows from the more general fact this is true for all normal matrices.
Suppose that $A$ is skew-symmetric. @State a result about the connection between its eigenvalues $\lambda _ i$ and its singular values $\sigma _ i$ and quickly @justify why it is true by appealing to another theorem.
This follows from the more general fact this is true for all normal matrices.
Suppose that $A$ is normal. @State a result about the connection between its eigenvalues $\lambda _ i$ and its singular values $\sigma _ i$.
Jordan–Wielandt matrix
Suppose $A$ is a matrix. @Define the Jordan–Wielandt matrix.
The Jordan–Wielandt matrix associated with a matrix $A$ is
\[H(A) = \begin{bmatrix}
0 & A \\
A^\top & 0
\end{bmatrix}\]
(sometimes also called the Hermitian dilation).
@State a result concerning its eigenvalues and eigenvectors.
This matrix has eigenvalues
\[\underbrace{\sigma _ 1, \ldots, \sigma _ n} _ {n \text{ values}},\quad \underbrace{-\sigma _ 1, \ldots, -\sigma _ n} _ {n \text{ values}},\quad \underbrace{0, \ldots, 0} _ {m - n \text{ values}},\]and it has orthogonal eigenvector matrix
\[\frac{1}{\sqrt{2}} \begin{bmatrix} U & U & \sqrt 2 \, U _ \perp \\ V & -V & 0 \end{bmatrix} \in \mathbb R^{(m + n)\times (m + n)}\]where $A = U \Sigma V^\top$, and $U = [U _ 1 \quad U _ \bot]$ where $U _ 1 \in \mathbb R^{m \times n}$ holds the first $n$ left singular vectors and $U _ \bot \in \mathbb R^{m \times (m - n)}$ holds the remaining ones.
Low-rank approximation
See Notes - Numerical Analysis HT24, Singular value decompositionU. Especially important are the results that:
Bite-sized
Uniqueness of the SVD: which factors are unique, which are not?
The singular values $\sigma _ 1, \ldots, \sigma _ n$ are always unique (they are the square roots of eigenvalues of $A^\top A$). The singular vectors are not: signs can be flipped (with $u _ i$ and $v _ i$ flipped together to preserve $A = \sum \sigma _ i u _ i v _ i^\top$); and if any $\sigma _ i = \sigma _ j$ coincide, the corresponding singular vectors span a multi-dimensional subspace with any orthonormal basis valid. Extreme case: orthogonal matrices have all $\sigma _ i = 1$, so $U, V$ enjoy enormous freedom.
“Shortest proof” of SVD existence (full-rank, $m \ge n$): take the symmetric eigendecomposition $A^\top A = V \Lambda V^\top$. Set $\Sigma = \Lambda^{1/2}$ and $U = A V \Sigma^{-1}$. Check $U^\top U = $ $I$ (using $A^\top A = V \Sigma^2 V^\top$). Then $A = U \Sigma V^\top$.
Cost of computing the SVD via Golub-Kahan bidiagonalisation: $\approx $ $\tfrac{8}{3} m n^2$ flops for singular values alone, and $\approx $ $20 m n^2$ flops including the singular vectors $U, V$. This is preferred over “form $A^\top A$, then eigendecompose” because the latter loses accuracy on small singular values.
The summation form of the SVD: $A = \sum _ {i=1}^{\mathrm{rank}(A)} $ $\sigma _ i u _ i v _ i^\top$ — a sum of rank-1 outer products of singular vectors, scaled by singular values. Truncating at $r$ gives the rank-$r$ best approximation (Eckart-Young).
Image compression via SVD: how big is the storage saving for a $500 \times 500$ image truncated at rank $r = 50$?
Original storage: $500 \times 500 = 250{,}000$ entries. Rank-50 truncation stores $U _ r$ ($500 \cdot 50$), $\Sigma _ r$ ($50$), and $V _ r$ ($500 \cdot 50$): total $(500 + 50 + 500) \cdot 50 = 52{,}500$ entries, roughly $5\times$ compression. Visually the rank-50 image is essentially indistinguishable from the original.
Strategy for proving the SVD properties — rank, column space, row space, null spaces (∆svd-properties-proof).
The proof works by using the change of variables $y = V^\top x$, so $Ax = U \Sigma y$, then leveraging the invertibility of $U, V$ to read everything off $\Sigma$.
- Rank: $\mathrm{rank}(A) = \mathrm{rank}(\Sigma) = r$ (number of nonzero $\sigma _ i$), since $U, V$ are invertible.
- Column space: $Ax = \sum _ {i \le r} \sigma _ i y _ i u _ i$, so $\mathrm{col}(A) = \mathrm{span}(u _ 1, \ldots, u _ r)$ (both inclusions follow from $V^\top$ being bijective and $\sigma _ i \ne 0$ for $i \le r$).
- Null space: $Ax = 0 \iff \Sigma V^\top x = 0 \iff (V^\top x) _ i = 0$ for $i \le r \iff x \in \mathrm{span}(v _ {r+1}, \ldots, v _ n)$.
- Column space of $A^\top$ and null space of $A^\top$: apply the above to $A^\top$ (which has SVD $A^\top = V \Sigma U^\top$, swapping the roles of $U$ and $V$).
The proof of $\sigma _ i(A) = \vert \lambda _ i(A) \vert $ for normal $A$ goes via the Schur decomposition: normality ⇒ $T$ in the Schur form is diagonal (∆diagonal-schur-iff-normal). Then $D^\top D = U^\top A^\top A U$ is a diagonalisation of $A^\top A$ with entries $ \vert \lambda _ i \vert ^2$, so the eigenvalues of $A^\top A$ are $ \vert \lambda _ i \vert ^2$, and $\sigma _ i = \vert \lambda _ i \vert $.