Singular Value Decomposition

Theorem 8.1 (Singular Value Decomposition). Every matrix $A \in \mathcal{M}_{m \times n}(\mathbb{R})$ can be factored as

$A = U \Sigma V^T$

Where $U \in \mathcal{M}_{m \times m}(\mathbb{R})$ is orthogonal, $V \in \mathcal{M}_{n \times n}(\mathbb{R})$ is orthogonal, and $\Sigma \in \mathcal{M}_{m \times n}(\mathbb{R})$ is diagonal with non-negative entries $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0$ (where $r = \mathrm{rank}(A)$).

The $\sigma_i$ are called the singular values of $A$. The columns of $U$ are the left singular vectors, and the columns of $V$ are the right singular vectors.

Proof. The matrix $A^T A$ is an $n \times n$ symmetric positive semi-definite matrix, so by the spectral theorem it has $n$ real non-negative eigenvalues and an orthonormal eigenbasis. Let $\sigma_1^2, \sigma_2^2, \ldots, \sigma_n^2$ be these eigenvalues (some may be zero) with corresponding orthonormal eigenvectors $\mathbf{v}_1, \ldots, \mathbf{v}_n$ forming the columns of $V$.

For each $i$ with $\sigma_i > 0$Define $\mathbf{u}_i = A\mathbf{v}_i / \sigma_i$. We verify that these form an orthonormal set:

$\mathbf{u}_i^T \mathbf{u}_j = \frac{\mathbf{v}_i^T A^T A \mathbf{v}_j}{\sigma_i \sigma_j} = \frac{\sigma_j^2 \mathbf{v}_i^T \mathbf{v}_j}{\sigma_i \sigma_j} = \frac{\sigma_j^2}{\sigma_i \sigma_j} \delta_{ij} = \delta_{ij}$

Extend $\{\mathbf{u}_1, \ldots, \mathbf{u}_r\}$ to an orthonormal basis of $\mathbb{R}^m$ to form $U$. Then for any vector $\mathbf{x} \in \mathbb{R}^n$:

$A\mathbf{x} = A\left(\sum_{i=1}^{n} (\mathbf{v}_i^T \mathbf{x})\mathbf{v}_i\right) = \sum_{i=1}^{n} (\mathbf{v}_i^T \mathbf{x}) A\mathbf{v}_i = \sum_{i=1}^{r} \sigma_i (\mathbf{v}_i^T \mathbf{x}) \mathbf{u}_i = U \Sigma V^T \mathbf{x}$

Since this holds for all $\mathbf{x}$We have $A = U \Sigma V^T$. $\blacksquare$

Proposition 8.2. The singular values of $A$ are the square roots of the eigenvalues of $A^T A$ (equivalently, of $AA^T$). The non-zero singular values of $A$ and $A^T$ are identical.

Proof. From the construction above, $A^T A \mathbf{v}_i = \sigma_i^2 \mathbf{v}_i$. For $AA^T$:

$AA^T \mathbf{u}_i = \frac{A(A^T A)\mathbf{v}_i}{\sigma_i} = \frac{\sigma_i^2 A\mathbf{v}_i}{\sigma_i} = \sigma_i^2 \mathbf{u}_i$

So $\mathbf{u}_i$ is an eigenvector of $AA^T$ with eigenvalue $\sigma_i^2$. The non-zero eigenvalues of $A^T A$ and $AA^T$ coincide (since if $A^T A \mathbf{v} = \lambda \mathbf{v}$ with $\lambda \neq 0$Then $AA^T(A\mathbf{v}) = A(A^T A \mathbf{v}) = \lambda(A\mathbf{v})$ and $A\mathbf{v} \neq \mathbf{0}$). $\blacksquare$

Proposition 8.3. If $A$ is symmetric with eigenvalues $\lambda_1, \ldots, \lambda_n$Then the singular values of $A$ are $|\lambda_1|, \ldots, |\lambda_n|$.

Proof. $A^T A = A^2$Whose eigenvalues are $\lambda_i^2$. The singular values are $\sqrt{\lambda_i^2} = |\lambda_i|$. $\blacksquare$

The SVD decomposes the linear transformation $T : \mathbb{R}^n \to \mathbb{R}^m$ into three steps:

1. $V^T$ rotates (or reflects) $\mathbb{R}^n$ into a coordinate system aligned with the right singular vectors.
2. $\Sigma$ scales each axis by the corresponding singular value (and possibly drops dimensions where $\sigma_i = 0$).
3. $U$ rotates (or reflects) the result into the coordinate system of the left singular vectors.

Unit circle image. Under $A$The unit circle in $\mathbb{R}^2$ is mapped to an ellipse with semi-axes $\sigma_1$ and $\sigma_2$ aligned with the columns of $U$.

Theorem 8.4 (Eckart—Young—Mirsky). Let $A = U \Sigma V^T$ be the SVD with singular values $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$. For any $k < r$The best rank-$k$ approximation to $A$ (in both the Frobenius and spectral norms) is

$A_k = \sum_{i=1}^{k} \sigma_i \mathbf{u}_i \mathbf{v}_i^T = U_k \Sigma_k V_k^T$

And the approximation error is

$\lVert A - A_k \rVert_F = \sqrt{\sigma_{k+1}^2 + \cdots + \sigma_r^2}, \qquad \lVert A - A_k \rVert_2 = \sigma_{k+1}$

Proof (Frobenius norm). Any rank-$k$ matrix $B$ can be written in terms of an orthonormal basis of its column space. Let $W \in \mathcal{M}_{n \times k}(\mathbb{R})$ have orthonormal columns spanning the column space of $B$. Then $B = CW^T$ for some $C$And:

$\lVert A - B \rVert_F^2 = \lVert A(I - WW^T) \rVert_F^2 + \lVert (A - C)W^T \rVert_F^2 \geq \lVert A(I - WW^T) \rVert_F^2$

The minimum over $W$ is achieved when $W$ spans the subspace spanned by $\mathbf{v}_1, \ldots, \mathbf{v}_k$ (the top $k$ right singular vectors), giving:

$\lVert A - A_k \rVert_F^2 = \sum_{i=k+1}^{r} \sigma_i^2$

The spectral norm result follows because $\lVert A - A_k \rVert_2 = \sigma_{k+1}$ is the largest singular value of $A - A_k$. $\blacksquare$

Definition. The Moore—Penrose pseudoinverse of $A = U \Sigma V^T$ is

$A^+ = V \Sigma^+ U^T$

Where $\Sigma^+$ is obtained from $\Sigma$ by transposing and inverting each non-zero singular value:

$(\Sigma^+)_{ii} = \begin{cases} 1/\sigma_i & \text{if} \sigma_i > 0 \\ 0 & \text{if} \sigma_i = 0 \end{cases}$

Theorem 8.5. The pseudoinverse satisfies the four Moore—Penrose conditions:

1. $AA^+A = A$
2. $A^+AA^+ = A^+$
3. $(AA^+)^T = AA^+$
4. $(A^+A)^T = A^+A$

Proof. Direct computation using $A = U \Sigma V^T$ and $A^+ = V \Sigma^+ U^T$:

$AA^+A = U \Sigma V^T V \Sigma^+ U^T U \Sigma V^T = U \Sigma \Sigma^+ \Sigma V^T = U \Sigma V^T = A$

Since $\Sigma \Sigma^+ \Sigma = \Sigma$ (the non-zero singular values are preserved, zeros remain zero). The remaining conditions follow similarly. $\blacksquare$

Theorem 8.6 (Minimum-Norm Least Squares). If $A\mathbf{x} = \mathbf{b}$ is inconsistent, then $\mathbf{x}^* = A^+\mathbf{b}$ is the least-squares solution of minimum norm.

Proof. The least-squares solutions to $A\mathbf{x} \approx \mathbf{b}$ are $\mathbf{x} = A^+\mathbf{b} + (I - A^+A)\mathbf{z}$ for arbitrary $\mathbf{z}$. Since $(I - A^+A)\mathbf{z} \in \ker(A)$ and $A^+\mathbf{b} \in \mathrm{im}(A^T)$These two components are orthogonal. The minimum-norm solution is obtained when $\mathbf{z} = \mathbf{0}$Giving $\mathbf{x}^* = A^+\mathbf{b}$. $\blacksquare$

Definition. The condition number of $A$ (with respect to the spectral norm) is

$\kappa(A) = \lVert A \rVert_2 \cdot \lVert A^+ \rVert_2 = \frac{\sigma_1}{\sigma_r}$

Where $\sigma_1$ is the largest and $\sigma_r$ is the smallest non-zero singular value.

Theorem 8.7 (Sensitivity of Linear Systems). If $A\mathbf{x} = \mathbf{b}$ and $A(\mathbf{x} + \delta\mathbf{x}) = \mathbf{b} + \delta\mathbf{b}$Then

$\frac{\lVert \delta\mathbf{x} \rVert}{\lVert \mathbf{x} \rVert} \leq \kappa(A) \cdot \frac{\lVert \delta\mathbf{b} \rVert}{\lVert \mathbf{b} \rVert}$

Proof. From $A\delta\mathbf{x} = \delta\mathbf{b}$: $\lVert \delta\mathbf{x} \rVert = \lVert A^{-1}\delta\mathbf{b} \rVert \leq \lVert A^{-1} \rVert \lVert \delta\mathbf{b} \rVert = \sigma_r^{-1} \lVert \delta\mathbf{b} \rVert$. From $A\mathbf{x} = \mathbf{b}$: $\lVert \mathbf{b} \rVert = \lVert A\mathbf{x} \rVert \geq \sigma_1^{-1} \lVert \mathbf{x} \rVert$… Wait, $\lVert A\mathbf{x} \rVert \geq \sigma_r \lVert \mathbf{x} \rVert$ and $\lVert \mathbf{b} \rVert \leq \sigma_1 \lVert \mathbf{x} \rVert$. Combining: $\lVert \delta\mathbf{x} \rVert / \lVert \mathbf{x} \rVert \leq (\sigma_1 / \sigma_r)(\lVert \delta\mathbf{b} \rVert / \lVert \mathbf{b} \rVert)$. $\blacksquare$

A matrix with large condition number is ill-conditioned: small perturbations in $\mathbf{b}$ can cause large changes in $\mathbf{x}$.

Problem. Find the SVD of $A = \begin{pmatrix} 3 & 2 \\ 2 & 3 \\ 2 & -2 \end{pmatrix}$.

Problem. Let $A = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix}$. Find the best rank-1 approximation.

Problem. Compute the condition number of $A = \begin{pmatrix} 1 & 1 \\ 1 & 1.0001 \end{pmatrix}$ and discuss its implications.

• Singular values are always non-negative. Unlike eigenvalues, which can be negative or complex, singular values are the square roots of eigenvalues of $A^T A$Hence always real and non-negative.
• The SVD is not unique. If $A$ has repeated singular values, the corresponding singular vectors can be any orthonormal basis of the eigenspace. The signs of singular vectors can also be flipped in pairs.
• The pseudoinverse equals the inverse only for square, full-rank matrices. When $A$ is not full rank, $A^+A \neq I$; instead, $A^+A$ is the orthogonal projection onto $\mathrm{im}(A^T)$.
• The SVD and eigendecomposition are different decompositions. The SVD always exists for any matrix, but the eigendecomposition requires the matrix to be square. Even for symmetric matrices, the singular values are $|\lambda_i|$Not $\lambda_i$.