Singular Value Decomposition

Attempt these from memory before reading.

• State the SVD of a matrix $A$. What are the shapes of the three factors?
• Does every matrix have one? What about a non-square matrix?
• How are the singular values related to the eigenvalues of $A^TA$?
• State the Eckart-Young theorem.
• What is the condition number, and what does a large one tell you?

Check your answers against the text. Prompt 2 is the one that separates the SVD from the spectral theorem: the spectral theorem needs a square, normal matrix, and the SVD does not care.

Diagonalisation is the tool of section 5, and it has a catch: it needs a square matrix with a full set of eigenvectors. Rectangular matrices — the ones that describe data, transformations between different spaces, and every least-squares problem — are left out.

The singular value decomposition removes every one of those restrictions. Any $m \times n$ matrix, real or complex, singular or not, admits a factorisation

with $U$ and $V$ orthogonal and $\Sigma$ diagonal with non-negative entries. Those entries are the singular values, and they are the answer to a geometric question rather than an algebraic one.

The geometric picture is the best way in. Every linear map does three things, in this order: rotate, scale along the axes, rotate again. That is all the SVD says. The columns of $V$ are the directions in the domain that get mapped to the directions of $U$ in the codomain, and $\Sigma$ says how much each is stretched.

Why the singular values are what they are. They are the square roots of the eigenvalues of $A^TA$, which is symmetric and positive semidefinite — so the spectral theorem applies and the square roots are real and non-negative. That is the whole relationship to section 5: the SVD is the spectral theorem applied to $A^TA$, written so that it says something about $A$.

What it buys you. The Eckart-Young theorem says that truncating the SVD to the largest $k$ singular values gives the best rank-$k$ approximation, in the least-squares sense — not a good approximation, the best one. That single theorem is the basis of data compression, principal component analysis, noise reduction and recommender systems, and it is why the SVD is the most useful theorem in applied linear algebra.

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

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:

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$:

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$:

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

And the approximation error is

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:

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:

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

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

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$:

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

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

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.

The SVD answers the question: what is the simplest description of a linear transformation? Every matrix, whether square or rectangular, can be decomposed as a rotation, followed by independent stretching along perpendicular axes, followed by another rotation. The singular values tell you how much stretching occurs along each axis, and they are always non-negative because stretching is a magnitude, not a signed quantity.

Think of the SVD as finding the “natural coordinate system” for a transformation. The right singular vectors are the input directions that matter most, and the left singular vectors are the corresponding output directions. The singular values rank these directions by importance, which is why truncating the SVD gives the best low-rank approximation. This is the mathematical foundation of principal component analysis, image compression, and recommendation systems. The condition number, the ratio of largest to smallest singular value, measures how close a matrix is to being degenerate: a high condition number means the matrix nearly collapses some direction to zero, making the system $A\mathbf{x} = \mathbf{b}$ sensitive to noise.

• 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$.

The first row is the most common confusion, and it is worth being precise: for a symmetric positive semidefinite $A$ the singular values and eigenvalues coincide, and that special case is why the two ideas get muddled.

The condition number row is the practical one. $\kappa(A) = \sigma_{\max} / \sigma_{\min}$ measures how much a relative error in the input can be amplified, and a large value is why some linear systems cannot be solved reliably no matter how good the algorithm is.

• Randomised numerical linear algebra. Computing a rank-$k$ SVD by sampling rather than by exact factorisation, which is how very large matrices are handled in practice.
• Robust low-rank approximation. Eckart-Young is optimal in least squares, which is catastrophic under outliers; replacing the norm is the active question.
• Matrix completion. The Netflix problem: recover a matrix from a tiny sample of entries, using low rank as the prior, with theory that is still being sharpened.
• Tensor decompositions. The SVD does not generalise uniquely to higher orders, and the competing generalisations — CP, Tucker, tensor train — are an active design space.
• Non-negative matrix factorisation. Restricting the factors to be non-negative makes the problem non-convex but interpretable, and the theory is far less complete than for the SVD.

Mix these with Eigenvalues and Eigenvectors, Inner Product Spaces, Systems of Linear Equations, Real Analysis.

1. (Eigenvalues.) Show that the singular values of $A$ are the square roots of the eigenvalues of $A^TA$, and hence that the largest singular value equals the operator norm $\lVert A \rVert_2$. Then compute both for a rotation matrix and explain the answer.
2. (Inner product spaces.) Prove that the best rank-$k$ approximation in the Frobenius norm keeps the $k$ largest singular values. Identify which part of the proof uses orthogonality and would fail in a general norm.
3. (Systems of equations.) Use the SVD to write down the solution of $Ax = b$ of minimum norm when $A$ is rank-deficient, and explain what the small singular values do to it.
4. (Optimisation.) Principal component analysis centres a data matrix and takes its SVD. Show that the leading right singular vectors maximise the projected variance, which is why PCA is an optimisation problem rather than a definition.
5. (Numerical analysis.) A matrix with condition number $10^{16}$ cannot be reliably inverted in double precision. Explain what that number means in terms of the singular values, and why it is a statement about the problem rather than the algorithm.
6. (Research.) State the Eckart-Young theorem precisely and explain why it fails if the Frobenius norm is replaced by the operator norm — and what the correct answer is in that norm.

• Eigenvalues and Eigenvectors: Singular values are the square roots of eigenvalues of $A^T A$, linking SVD to spectral theory.

• Inner Product Spaces: The SVD uses orthonormal bases derived from inner products on the column and row spaces of a matrix.

• Systems of Linear Equations: The pseudoinverse derived from the SVD provides minimum-norm least squares solutions to inconsistent linear systems.

• Quantum Mechanics

• Graph Theory

• Eigenvalues and Eigenvectors
• Inner Product Spaces
• Linear Independence, Span, Basis, and Dimension
• Matrices