math.wiki
Linear algebra › Inner product spaces › Singular value decomposition
Sign in

Singular value decomposition

The spectral theorem makes a normal operator diagonal in one orthonormal basis. If a linear map may use one orthonormal basis for its inputs and another for its outputs, can every linear map be made diagonal?

Where you are 5 in Inner product spaces

Why this exists

The The spectral theorem gives an orthonormal basis of eigenvectors only for an operator, and only for a normal one (self-adjoint over \mathbb{R}). A 3 \times 2 matrix has no eigenvectors at all, and the single eigenvalue 1 of \begin{bmatrix} 1 & 4 \\ 0 & 1 \end{bmatrix} says nothing about how far it stretches vectors (Example 5).

The way out is to allow two orthonormal bases, one for the inputs and one for the outputs. Then every linear map between finite-dimensional inner product spaces has a diagonal matrix, and its diagonal entries, the singular values, measure how much the map stretches in each direction.

Definition

Throughout, V and W are finite-dimensional inner product spaces over \mathbb{F}, n = \dim V, m = \dim W, and T \in \mathcal{L}(V, W). By Example 5 of Adjoints and self-adjoint operators, T^{*}T \in \mathcal{L}(V) is self-adjoint with eigenvalues real and at least 0, so by the spectral theorem V has an orthonormal basis (\mathbf{v}_1, \dots, \mathbf{v}_n) with T^{*}T\mathbf{v}_k = \lambda_k\mathbf{v}_k and \lambda_1 \ge \dots \ge \lambda_n \ge 0.

The singular values of T are \displaystyle \sigma_k = \sqrt{\lambda_k}, k = 1, \dots, n: the nonnegative square roots of the eigenvalues of T^{*}T, largest first, each eigenvalue \lambda repeated \dim E_\lambda(T^{*}T) times. Let r be the number of positive ones.

A singular value decomposition of T is a pair of orthonormal bases, (\mathbf{v}_1, \dots, \mathbf{v}_n) of V and (\mathbf{u}_1, \dots, \mathbf{u}_m) of W, with

\begin{aligned} T\mathbf{v}_k &= \sigma_k\mathbf{u}_k \quad (k \le r), \\ T\mathbf{v}_k &= \mathbf{0} \quad (k > r). \end{aligned}

The \mathbf{v}_k are right singular vectors, the \mathbf{u}_k left singular vectors.

For A \in \mathbb{F}^{m \times n}, acting from \mathbb{F}^n to \mathbb{F}^m with the Euclidean inner products, a singular value decomposition is a factorization

A = U\Sigma V^{*}

with U \in \mathbb{F}^{m \times m} and V \in \mathbb{F}^{n \times n} unitary, and \Sigma \in \mathbb{R}^{m \times n} holding \sigma_1, \dots, \sigma_p, p = \min(m, n), down its main diagonal and 0 elsewhere. Over \mathbb{R}, U and V are orthogonal and V^{*} = V^{T}.

For V \neq \{\mathbf{0}\}, the norm of T is \lVert T \rVert = \max\{\lVert T\mathbf{x} \rVert : \lVert \mathbf{x} \rVert = 1\}, the largest stretch of a unit vector (Result 4 shows the maximum exists).

Intuition

Read A = U\Sigma V^{*} from right to left: V^{*} = V^{-1} takes the basis (\mathbf{v}_k) to the standard basis, \Sigma stretches the kth axis by \sigma_k (dropping or adding coordinates when m \neq n), and U takes the standard basis to (\mathbf{u}_k). Unitary matrices keep lengths and angles, so every change of shape happens in \Sigma: every linear map sends some orthonormal basis to orthogonal vectors of lengths \sigma_k.

For a real 2 \times 2 A with \sigma_1 \ge \sigma_2 > 0, a unit vector is \mathbf{x} = \cos t\,\mathbf{v}_1 + \sin t\,\mathbf{v}_2, and A\mathbf{x} = \sigma_1\cos t\,\mathbf{u}_1 + \sigma_2\sin t\,\mathbf{u}_2. The unit circle goes to an ellipse with semi-axes \sigma_1\mathbf{u}_1 and \sigma_2\mathbf{u}_2.

\mathbf{v}_1
\mathbf{v}_2
\sigma_1\mathbf{u}_1
\sigma_2\mathbf{u}_2
A
Figure 1A = \begin{bmatrix} 4 & 0 \\ 3 & 5 \end{bmatrix} of Example 1 takes the perpendicular unit vectors \displaystyle \mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(1, 1) and \displaystyle \mathbf{v}_2 = \tfrac{1}{\sqrt{2}}(1, -1) (left) to the perpendicular semi-axes \displaystyle A\mathbf{v}_1 = 2\sqrt{10}\,\mathbf{u}_1 and \displaystyle A\mathbf{v}_2 = \sqrt{10}\,\mathbf{u}_2 of the image of the unit circle (right, drawn at a smaller scale).

Results

Result 1 (singular values). The list \sigma_1, \dots, \sigma_n depends only on T, not on the eigenbasis chosen. In that eigenbasis \lVert T\mathbf{v}_k \rVert = \sigma_k, and r = \operatorname{rank} T, so r \le \min(m, n).

Result 2 (singular value decomposition). Every T \in \mathcal{L}(V, W) has a singular value decomposition. In any one, for every \mathbf{x} \in V,

T\mathbf{x} = \sum_{k=1}^{r} \sigma_k\langle \mathbf{x}, \mathbf{v}_k \rangle\mathbf{u}_k;

T^{*}\mathbf{u}_k = \sigma_k\mathbf{v}_k for k \le r and T^{*}\mathbf{u}_k = \mathbf{0} for k > r; (\mathbf{u}_1, \dots, \mathbf{u}_r) is an orthonormal basis of \operatorname{im} T and (\mathbf{v}_{r+1}, \dots, \mathbf{v}_n) one of \ker T; and the matrix of T with respect to the two bases is \Sigma.

Result 3 (matrix form). Every A \in \mathbb{F}^{m \times n} has a singular value decomposition A = U\Sigma V^{*}, real when A is real, whose columns of V and U are right and left singular vectors, and

A = \sigma_1\mathbf{u}_1\mathbf{v}_1^{*} + \dots + \sigma_r\mathbf{u}_r\mathbf{v}_r^{*},

the reduced form. Conversely, if A = U\Sigma V^{*} with U, V unitary and \Sigma \in \mathbb{R}^{m \times n} zero off its diagonal, with diagonal entries s_1 \ge \dots \ge s_p \ge 0, then these are the first p singular values of A and any others are 0.

Result 4 (largest and smallest stretch). In a singular value decomposition, for every \mathbf{x} \in V,

\lVert T\mathbf{x} \rVert^2 = \sum_{k=1}^{n} \sigma_k^2\,|\langle \mathbf{x}, \mathbf{v}_k \rangle|^2.

So \sigma_n\lVert \mathbf{x} \rVert \le \lVert T\mathbf{x} \rVert \le \sigma_1\lVert \mathbf{x} \rVert, with equality at \mathbf{v}_n and at \mathbf{v}_1. If V \neq \{\mathbf{0}\}, then \lVert T \rVert = \sigma_1.

Result 5 (best approximation of lower rank). Let 0 \le k < r and T_k\mathbf{x} = \sum_{j=1}^{k} \sigma_j\langle \mathbf{x}, \mathbf{v}_j \rangle\mathbf{u}_j. Then \operatorname{rank} T_k = k and \lVert T - T_k \rVert = \sigma_{k+1}, and every S \in \mathcal{L}(V, W) with \operatorname{rank} S \le k has \lVert T - S \rVert \ge \sigma_{k+1}. For a matrix, A_k = \sum_{j=1}^{k} \sigma_j\mathbf{u}_j\mathbf{v}_j^{*} is a closest matrix of rank at most k.

Result 6 (normal operators). Let T \in \mathcal{L}(V) be normal (if \mathbb{F} = \mathbb{C}) or self-adjoint (if \mathbb{F} = \mathbb{R}), with orthonormal eigenbasis T\mathbf{q}_k = \lambda_k\mathbf{q}_k. Then the singular values of T are |\lambda_1|, \dots, |\lambda_n| in decreasing order.

Why it is true

Result 1. Fix \lambda. If \mathbf{x} = \sum_k c_k\mathbf{v}_k lies in E_\lambda(T^{*}T), then \sum_k c_k(\lambda_k - \lambda)\mathbf{v}_k = T^{*}T\mathbf{x} - \lambda\mathbf{x} = \mathbf{0}, so c_k = 0 whenever \lambda_k \neq \lambda. So the \mathbf{v}_k with \lambda_k = \lambda span E_\lambda, and being independent they are a basis of it: \lambda occurs exactly \dim E_\lambda times, in every eigenbasis. Next, \lVert T\mathbf{v}_k \rVert^2 = \langle T^{*}T\mathbf{v}_k, \mathbf{v}_k \rangle = \lambda_k. Finally \ker T = \ker T^{*}T = E_0(T^{*}T) (Example 5 of Adjoints and self-adjoint operators) has dimension n - r, so the fundamental theorem of linear maps (Null space, range and the fundamental theorem) gives \operatorname{rank} T = r, and r \le m as \operatorname{im} T \subseteq W.

Result 2. Take the eigenbasis of the definition. For all j, k,

\langle T\mathbf{v}_j, T\mathbf{v}_k \rangle = \langle T^{*}T\mathbf{v}_j, \mathbf{v}_k \rangle = \sigma_j^2\langle \mathbf{v}_j, \mathbf{v}_k \rangle.

So the T\mathbf{v}_k are orthogonal with lengths \sigma_k: T\mathbf{v}_k = \mathbf{0} for k > r, and \mathbf{u}_k = T\mathbf{v}_k/\sigma_k for k \le r is an orthonormal list. Extending it to an orthonormal basis of W (Result 4 of Orthonormal bases and Gram-Schmidt, proved) gives a singular value decomposition.

In any singular value decomposition, \mathbf{x} = \sum_k \langle \mathbf{x}, \mathbf{v}_k \rangle\mathbf{v}_k (Result 3 of Orthonormal bases and Gram-Schmidt, proved); applying T gives the formula. It puts \operatorname{im} T inside \operatorname{span}\{\mathbf{u}_1, \dots, \mathbf{u}_r\}, and each such \mathbf{u}_k = T(\mathbf{v}_k/\sigma_k) is in \operatorname{im} T. The \mathbf{v}_k with k > r lie in \ker T, of dimension n - r by Result 1, so they are a basis of it. Next, \langle T^{*}\mathbf{u}_k, \mathbf{v}_j \rangle = \langle \mathbf{u}_k, T\mathbf{v}_j \rangle is the real number \sigma_k when j = k \le r and 0 otherwise, and expanding T^{*}\mathbf{u}_k in the basis (\mathbf{v}_j) gives \sigma_k\mathbf{v}_k or \mathbf{0}. Column k of the matrix holds the coordinates of T\mathbf{v}_k: \sigma_k in row k, zeros elsewhere. That is \Sigma.

Result 3. Apply Result 2 to \mathbf{x} \mapsto A\mathbf{x}, whose adjoint is \mathbf{y} \mapsto A^{*}\mathbf{y} (Result 3 of Adjoints and self-adjoint operators); for real A the eigenbasis of A^{T}A can be taken real (Result 5 of The spectral theorem). Put the \mathbf{v}_k as columns of V and the \mathbf{u}_k as columns of U; orthonormal columns make both unitary. Column k of AV is A\mathbf{v}_k, and column k of U\Sigma is \sigma_k\mathbf{u}_k for k \le p and \mathbf{0} beyond; they agree because A\mathbf{v}_k = \mathbf{0} and \sigma_k = 0 for k > r. So AV = U\Sigma and A = U\Sigma V^{*}. As \langle \mathbf{x}, \mathbf{v}_k \rangle = \mathbf{v}_k^{*}\mathbf{x}, the formula of Result 2 is the reduced form.

Conversely, \Sigma is real, so

A^{*}A = V\Sigma^{T}U^{*}U\Sigma V^{*} = V(\Sigma^{T}\Sigma)V^{*},

with \Sigma^{T}\Sigma = \operatorname{diag}(s_1^2, \dots, s_p^2, 0, \dots, 0) of size n \times n. So A^{*}AV = V\Sigma^{T}\Sigma: the columns of V are an orthonormal eigenbasis of A^{*}A with eigenvalues s_1^2, \dots, s_p^2, 0, \dots, 0 in decreasing order, and Result 1 finishes.

Result 4. By Result 2 and Result 1 of Orthonormal bases and Gram-Schmidt, proved, \lVert T\mathbf{x} \rVert^2 = \sum_{k \le r} \sigma_k^2|\langle \mathbf{x}, \mathbf{v}_k \rangle|^2, and the terms with k > r are 0. By Result 3 there, \lVert \mathbf{x} \rVert^2 = \sum_k |\langle \mathbf{x}, \mathbf{v}_k \rangle|^2. Replacing each \sigma_k^2 by \sigma_1^2, or by \sigma_n^2, gives the bounds, and \lVert T\mathbf{v}_k \rVert = \sigma_k gives the equalities.

Result 5. The image of T_k is \operatorname{span}\{\mathbf{u}_1, \dots, \mathbf{u}_k\}, of dimension k. As (T - T_k)\mathbf{x} = \sum_{k < j \le r} \sigma_j\langle \mathbf{x}, \mathbf{v}_j \rangle\mathbf{u}_j, the argument of Result 4 gives \lVert (T - T_k)\mathbf{x} \rVert \le \sigma_{k+1}\lVert \mathbf{x} \rVert, with equality at \mathbf{v}_{k+1}.

Now let \operatorname{rank} S \le k, so \dim \ker S \ge n - k by the fundamental theorem of linear maps. Let X = \operatorname{span}\{\mathbf{v}_1, \dots, \mathbf{v}_{k+1}\}, of dimension k + 1 \le n. By the dimension formula of Sums and direct sums of subspaces,

\dim(\ker S \cap X) \ge (n - k) + (k + 1) - n = 1.

Take a unit \mathbf{x} = \sum_{j \le k+1} c_j\mathbf{v}_j in \ker S \cap X. Then (T - S)\mathbf{x} = T\mathbf{x} and, by Result 4, \lVert T\mathbf{x} \rVert^2 = \sum_{j \le k+1} \sigma_j^2|c_j|^2, at least \sigma_{k+1}^2\sum_j |c_j|^2 = \sigma_{k+1}^2.

Result 6. By Result 7 of Adjoints and self-adjoint operators, T^{*}\mathbf{q}_k = \bar{\lambda}_k\mathbf{q}_k (over \mathbb{R}, T^{*} = T and \lambda_k is real), so T^{*}T\mathbf{q}_k = |\lambda_k|^2\mathbf{q}_k. The \mathbf{q}_k are an orthonormal eigenbasis of T^{*}T, and Result 1 finishes.

Worked examples

Example 1

A square matrix and its ellipse

Find a singular value decomposition of A = \begin{bmatrix} 4 & 0 \\ 3 & 5 \end{bmatrix} and describe the image of the unit circle.

Solution

A^{T}A = \begin{bmatrix} 25 & 15 \\ 15 & 25 \end{bmatrix} has The characteristic equation and finding eigenvalues \lambda^2 - 50\lambda + 400 = 0, with roots 40 and 10 and unit eigenvectors \displaystyle \mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(1, 1), \displaystyle \mathbf{v}_2 = \tfrac{1}{\sqrt{2}}(1, -1). So \displaystyle \sigma_1 = 2\sqrt{10}, \displaystyle \sigma_2 = \sqrt{10}, and

\begin{aligned} \mathbf{u}_1 &= \frac{A\mathbf{v}_1}{\sigma_1} = \frac{(4, 8)}{4\sqrt{5}} = \tfrac{1}{\sqrt{5}}(1, 2), \\ \mathbf{u}_2 &= \frac{A\mathbf{v}_2}{\sigma_2} = \frac{(4, -2)}{2\sqrt{5}} = \tfrac{1}{\sqrt{5}}(2, -1). \end{aligned}

So A = U\Sigma V^{T} with \displaystyle U = \tfrac{1}{\sqrt{5}}\begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix}, \displaystyle \Sigma = \begin{bmatrix} 2\sqrt{10} & 0 \\ 0 & \sqrt{10} \end{bmatrix} and \displaystyle V = \tfrac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}. The unit circle goes to an ellipse with semi-axes \displaystyle 2\sqrt{10} along (1, 2) and \displaystyle \sqrt{10} along (2, -1). The eigenvectors of A, (0, 1) for 5 and (1, -3) for 4, are neither perpendicular nor the axes.

Example 2

A rank-one matrix, full and reduced

Find the full and the reduced singular value decomposition of A = \begin{bmatrix} 2 & -2 \\ 1 & -1 \\ 2 & -2 \end{bmatrix}.

Solution

A^{T}A = \begin{bmatrix} 9 & -9 \\ -9 & 9 \end{bmatrix} has eigenvalues 18, with \displaystyle \mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(1, -1), and 0, with \displaystyle \mathbf{v}_2 = \tfrac{1}{\sqrt{2}}(1, 1). So \displaystyle \sigma_1 = 3\sqrt{2}, \sigma_2 = 0, r = 1, and \mathbf{u}_1 = A\mathbf{v}_1/\sigma_1 = (4, 2, 4)/6 = \tfrac{1}{3}(2, 1, 2). The reduced form is

A = 3\sqrt{2}\,\mathbf{u}_1\mathbf{v}_1^{T}.

The full form completes \mathbf{u}_1 to an orthonormal basis of \mathbb{R}^3. The vectors (1, 2, -2) and (2, -2, -1) are orthogonal to (2, 1, 2) and to each other, all of length 3, so

U = \frac{1}{3}\begin{bmatrix} 2 & 1 & 2 \\ 1 & 2 & -2 \\ 2 & -2 & -1 \end{bmatrix},

V = [\mathbf{v}_1\ \mathbf{v}_2], and \Sigma is 3 \times 2 with only the entry \displaystyle 3\sqrt{2} in the corner. Any orthonormal basis of (\operatorname{im} A)^{\perp} = \ker A^{T} would serve as \mathbf{u}_2, \mathbf{u}_3.

Example 3

Differentiation on quadratics

Example 3 of Adjoints and self-adjoint operators gave \mathcal{P}_2(\mathbb{R}), with \langle p, q \rangle = \int_0^1 p(x)q(x)\,dx, the orthonormal basis q_1 = 1, \displaystyle q_2 = \sqrt{3}(2x - 1), \displaystyle q_3 = \sqrt{5}(6x^2 - 6x + 1), with Dq_1 = 0, \displaystyle Dq_2 = 2\sqrt{3}\,q_1, \displaystyle Dq_3 = 2\sqrt{15}\,q_2. Find a singular value decomposition of D and the largest \lVert p' \rVert with \lVert p \rVert = 1.

Solution

The images of q_3, q_2, q_1 are the orthogonal vectors \displaystyle 2\sqrt{15}\,q_2, \displaystyle 2\sqrt{3}\,q_1, 0. So \mathbf{v}_1 = q_3, \mathbf{v}_2 = q_2, \mathbf{v}_3 = q_1 and \mathbf{u}_1 = q_2, \mathbf{u}_2 = q_1, \mathbf{u}_3 = q_3 give \displaystyle D\mathbf{v}_1 = 2\sqrt{15}\,\mathbf{u}_1, \displaystyle D\mathbf{v}_2 = 2\sqrt{3}\,\mathbf{u}_2, D\mathbf{v}_3 = 0. These are the singular values: by Result 3 of Adjoints and self-adjoint operators, the matrix of D^{*}D in (q_1, q_2, q_3) is [D]^{T}[D] = \operatorname{diag}(0, 12, 60).

By Result 4, \displaystyle \lVert p' \rVert \le 2\sqrt{15} when \lVert p \rVert = 1, with equality at \displaystyle p = \pm\sqrt{5}(6x^2 - 6x + 1). Yet D^3 = 0 on \mathcal{P}_2(\mathbb{R}), so 0 is the only eigenvalue of D.

Example 4

The adjoint has the same positive singular values

Prove that T^{*} \in \mathcal{L}(W, V) has singular values \sigma_1, \dots, \sigma_r followed by m - r zeros.

Solution

Take a singular value decomposition of T. By Result 2, T^{*}\mathbf{u}_k = \sigma_k\mathbf{v}_k for k \le r and T^{*}\mathbf{u}_k = \mathbf{0} for k > r. The singular values of T^{*} come from (T^{*})^{*}T^{*} = TT^{*} (Result 2 of Adjoints and self-adjoint operators), and TT^{*}\mathbf{u}_k = \sigma_kT\mathbf{v}_k = \sigma_k^2\mathbf{u}_k for k \le r, while TT^{*}\mathbf{u}_k = \mathbf{0} for k > r. So (\mathbf{u}_1, \dots, \mathbf{u}_m) is an orthonormal eigenbasis of TT^{*} with eigenvalues \sigma_1^2, \dots, \sigma_r^2 and m - r zeros, in decreasing order, and Result 1 for T^{*} gives the claim.

So for a wide A, the smaller matrix AA^{*} yields the \mathbf{u}_k, then \mathbf{v}_k = A^{*}\mathbf{u}_k/\sigma_k for k \le r, completed by a basis of \ker A.

Example 5

Eigenvalue one, stretch above four

Let A = \begin{bmatrix} 1 & 4 \\ 0 & 1 \end{bmatrix}. Find its singular values and vectors and compare them with its eigenvalues.

Solution

A^{T}A = \begin{bmatrix} 1 & 4 \\ 4 & 17 \end{bmatrix} has characteristic equation \lambda^2 - 18\lambda + 1 = 0, so \displaystyle \lambda = 9 \pm 4\sqrt{5} = (\sqrt{5} \pm 2)^2. Hence \displaystyle \sigma_1 = \sqrt{5} + 2 \approx 4.24 and \displaystyle \sigma_2 = \sqrt{5} - 2 \approx 0.24.

For \lambda_1, the first row of A^{T}A - \lambda_1I gives \displaystyle (-8 - 4\sqrt{5})x_1 + 4x_2 = 0, so x_2 = cx_1 with \displaystyle c = 2 + \sqrt{5}. As c^2 = 1 + 4c,

A\begin{bmatrix} 1 \\ c \end{bmatrix} = \begin{bmatrix} 1 + 4c \\ c \end{bmatrix} = c\begin{bmatrix} c \\ 1 \end{bmatrix}.

With \displaystyle N = \sqrt{1 + c^2}, \mathbf{v}_1 = (1, c)/N and \mathbf{u}_1 = (c, 1)/N. Likewise \mathbf{v}_2 = (c, -1)/N, and since c - 4 = 1/c, A(c, -1) = \tfrac{1}{c}(1, -c), so \mathbf{u}_2 = (1, -c)/N.

So \displaystyle \lVert A \rVert = \sqrt{5} + 2, and \mathbf{v}_2 shrinks to length \displaystyle \sqrt{5} - 2, though the only eigenvalue is 1. Result 6 does not apply: AA^{T} and A^{T}A have (1, 1) entries 17 and 1, so A is not normal. And \sigma_1\sigma_2 = 1 = \det A, as Exercise 16 predicts.

Example 6

A rank-one model at a turnpike

Jasmine and Isaac study a turnpike. Row i of A = \begin{bmatrix} 26 & 18 \\ 40 & 45 \\ 28 & 54 \end{bmatrix} holds the cars, in hundreds, passing interchange i in a week at weekday and at weekend rates. If \mathbf{x} lists the two fares in dollars, A\mathbf{x} lists each interchange’s weekly takings in hundreds of dollars. Find a B of rank at most one, every entry an interchange factor times a day factor, that makes \lVert A - B \rVert smallest.

Solution

A^{T}A = \begin{bmatrix} 3060 & 3780 \\ 3780 & 5265 \end{bmatrix} has characteristic equation

\begin{aligned} &\lambda^2 - 8325\lambda + 1{,}822{,}500 \\ &= (\lambda - 8100)(\lambda - 225) = 0, \end{aligned}

so \sigma_1 = 90, \sigma_2 = 15. The first row of A^{T}A - 8100I gives -5040x_1 + 3780x_2 = 0, so \mathbf{v}_1 = \tfrac{1}{5}(3, 4) and \mathbf{v}_2 = \tfrac{1}{5}(4, -3). Then

\begin{aligned} A\mathbf{v}_1 &= (30, 60, 60) = 90 \cdot \tfrac{1}{3}(1, 2, 2), \\ A\mathbf{v}_2 &= (10, 5, -10) = 15 \cdot \tfrac{1}{3}(2, 1, -2). \end{aligned}

By Result 5 with k = 1, the best choice is A_1 = 90\,\mathbf{u}_1\mathbf{v}_1^{T}:

A_1 = 6\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}\begin{bmatrix} 3 & 4 \end{bmatrix} = \begin{bmatrix} 18 & 24 \\ 36 & 48 \\ 36 & 48 \end{bmatrix},

with \lVert A - A_1 \rVert = 15, and no table of rank at most one does better. Row i of A_1 is 1, 2 or 2 times the day factor (18, 24). For any fares, \lVert A\mathbf{x} - A_1\mathbf{x} \rVert \le 15\lVert \mathbf{x} \rVert, while \lVert A\mathbf{x} \rVert reaches 90\lVert \mathbf{x} \rVert.

Boundaries

  • Singular vectors are not unique, and they come in pairs. Replacing \mathbf{v}_k by -\mathbf{v}_k forces \mathbf{u}_k to -\mathbf{u}_k, and a repeated singular value allows any orthonormal basis of its eigenspace of T^{*}T (Exercise 6). Only the singular values are fixed (Result 3). For k \le r, \mathbf{u}_k must be T\mathbf{v}_k/\sigma_k: in Example 1, \mathbf{v}_1 with -\mathbf{u}_1 flips the first term of the reduced form.
  • Singular values are not eigenvalues. They agree in absolute value for normal operators (Result 6) and can be far apart otherwise (Examples 3 and 5). What survives is \sigma_n \le |\lambda| \le \sigma_1 (Exercise 14).
  • Finite dimension is used. On C[0, 1] with the integral inner product, the map (Mf)(x) = xf(x) from the Boundaries of The spectral theorem has M^{*}M = M^2, with no eigenvalue by the argument there, so no singular vectors. Result 4 fails too: \lVert f \rVert^2 - \lVert Mf \rVert^2 is \int_0^1 (1 - x^2)f(x)^2\,dx > 0 for f \neq 0, by Continuity, while f(x) = x^N gives \displaystyle \lVert Mf \rVert^2/\lVert f \rVert^2 = \frac{2N + 1}{2N + 3} \to 1. No unit vector has the largest stretch.

Where this goes next

Least squares: the best approximate solution of Ax = b needed independent columns for the normal equations. The pseudo-inverse A^{+} = \sum_{k \le r} \sigma_k^{-1}\mathbf{v}_k\mathbf{u}_k^{*} (Exercise 9) works for every matrix: A^{+}\mathbf{b} is the least-squares solution of smallest length (not proved here). Dropping small singular values compresses data at the cost Result 5 measures, and Exercise 17 gives the polar form A = QP.

The decomposition uses two bases, so it says nothing about powers T^k. Keeping one basis for an operator that is not normal leads to Generalized eigenvectors and the Jordan canonical form.

Exercises

Computing decompositions

  1. Find a singular value decomposition of B = \begin{bmatrix} 5 & 5 \\ -1 & 7 \end{bmatrix}.
  2. Find the singular values of C = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} through CC^{T}, as in Example 4, then a full singular value decomposition.
  3. Let F = \begin{bmatrix} 1 & i \\ i & -1 \end{bmatrix} act on \mathbb{C}^2. Show that 0 is its only eigenvalue, and find its singular values and a reduced singular value decomposition.
  4. Use Result 6 to find the singular values of N = \begin{bmatrix} 2 & -3 \\ 3 & 2 \end{bmatrix} and of S = \begin{bmatrix} 1 & 2 \\ 2 & -2 \end{bmatrix}.
  5. Find a full singular value decomposition of P = \begin{bmatrix} 1 & 2 \\ 2 & -1 \\ 2 & 0 \end{bmatrix}, whose columns are orthogonal.
  6. Show that both singular values of G = \begin{bmatrix} 2 & 1 \\ 2 & -2 \\ 1 & 2 \end{bmatrix} equal 3, that every orthonormal basis of \mathbb{R}^2 can serve as (\mathbf{v}_1, \mathbf{v}_2), and give \mathbf{u}_3.

Stretch, norm and approximation

  1. Find the largest and smallest values of \lVert M\mathbf{x} \rVert over unit \mathbf{x} \in \mathbb{R}^2 for M = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix}, and where they occur.
  2. For B of Exercise 1, describe the image of the unit circle, find the closest B_1 of rank at most one (Result 5) and \lVert B - B_1 \rVert, and check that |\det B| = \sigma_1\sigma_2.
  3. For C of Exercise 2, compute the pseudo-inverse C^{+} = \sum_{k \le r} \sigma_k^{-1}\mathbf{v}_k\mathbf{u}_k^{T} and check that CC^{+} = I_2.
  4. On \mathcal{P}_2(\mathbb{R}) with the inner product of Example 3, find the singular values of \varphi(p) = p(1), a linear map to \mathbb{R}, and the unit p that makes p(1) largest.

Proofs

In these, V and W are finite-dimensional inner product spaces, n = \dim V \ge 1, m = \dim W, and T \in \mathcal{L}(V, W) has singular values \sigma_1 \ge \dots \ge \sigma_n.

  1. Prove that T is injective if and only if \sigma_n > 0, and surjective if and only if exactly m singular values are positive.
  2. Prove that \lVert T\mathbf{x} \rVert = \lVert \mathbf{x} \rVert for every \mathbf{x} if and only if every singular value of T is 1.
  3. Let R \in \mathcal{L}(V) and S \in \mathcal{L}(W) with R^{*}R = I and S^{*}S = I. Prove that STR has the same singular values as T.
  4. Let W = V and let \lambda be an eigenvalue of T. Prove that \sigma_n \le |\lambda| \le \sigma_1.
  5. Let \mathbf{w} \in V and \varphi(\mathbf{v}) = \langle \mathbf{v}, \mathbf{w} \rangle, a map to \mathbb{F} with \langle a, b \rangle = a\bar{b}. Prove that the singular values of \varphi are \lVert \mathbf{w} \rVert and n - 1 zeros.
  6. Let A \in \mathbb{R}^{n \times n}. Prove that |\det A| = \sigma_1\sigma_2\cdots\sigma_n.
  7. Let A \in \mathbb{F}^{n \times n}. Prove that A = QP with Q unitary and P Hermitian with \mathbf{x}^{*}P\mathbf{x} \ge 0 for all \mathbf{x} (a polar decomposition).
Answers
  1. B^{T}B = \begin{bmatrix} 26 & 18 \\ 18 & 74 \end{bmatrix}, with \lambda^2 - 100\lambda + 1600 = 0, has 80 with \displaystyle \mathbf{v}_1 = \tfrac{1}{\sqrt{10}}(1, 3) and 20 with \displaystyle \mathbf{v}_2 = \tfrac{1}{\sqrt{10}}(3, -1). Then \mathbf{u}_k = B\mathbf{v}_k/\sigma_k gives \displaystyle U = \tfrac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, \displaystyle \Sigma = \operatorname{diag}(4\sqrt{5}, 2\sqrt{5}), \displaystyle V = \tfrac{1}{\sqrt{10}}\begin{bmatrix} 1 & 3 \\ 3 & -1 \end{bmatrix}.
  2. CC^{T} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} has eigenvalues 3 and 1, with \displaystyle \mathbf{u}_1 = \tfrac{1}{\sqrt{2}}(1, 1), \displaystyle \mathbf{u}_2 = \tfrac{1}{\sqrt{2}}(1, -1). By Example 4 applied to C^{T}, the singular values of C are \displaystyle \sqrt{3}, 1, 0. Then \displaystyle \mathbf{v}_1 = C^{T}\mathbf{u}_1/\sqrt{3} = \tfrac{1}{\sqrt{6}}(1, 2, 1), \displaystyle \mathbf{v}_2 = C^{T}\mathbf{u}_2 = \tfrac{1}{\sqrt{2}}(1, 0, -1), and \displaystyle \mathbf{v}_3 = \tfrac{1}{\sqrt{3}}(1, -1, 1) spans \ker C, with \displaystyle \Sigma = \begin{bmatrix} \sqrt{3} & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}.
  3. \operatorname{tr} F = 0 and \det F = -1 - i^2 = 0, so the characteristic equation is \lambda^2 = 0. F^{*}F = \begin{bmatrix} 2 & 2i \\ -2i & 2 \end{bmatrix} has eigenvalues 4 and 0, so the singular values are 2 and 0. For 4, \displaystyle \mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(1, -i) and \displaystyle F\mathbf{v}_1 = \tfrac{1}{\sqrt{2}}(2, 2i), so \displaystyle \mathbf{u}_1 = \tfrac{1}{\sqrt{2}}(1, i) and F = 2\mathbf{u}_1\mathbf{v}_1^{*}.
  4. N^{T}N = NN^{T} = 13I, so N is normal with eigenvalues 2 \pm 3i, and by Result 6 its singular values are \displaystyle \sqrt{13}, \displaystyle \sqrt{13}. S is symmetric with eigenvalues 2 and -3, so its singular values are 3 and 2.
  5. P^{T}P = \operatorname{diag}(9, 5), so \sigma_1 = 3, \displaystyle \sigma_2 = \sqrt{5}, V = I_2, \mathbf{u}_1 = \tfrac{1}{3}(1, 2, 2), \displaystyle \mathbf{u}_2 = \tfrac{1}{\sqrt{5}}(2, -1, 0), completed by \displaystyle \mathbf{u}_3 = \tfrac{1}{3\sqrt{5}}(2, 4, -5), and \Sigma has rows (3, 0), \displaystyle (0, \sqrt{5}), (0, 0).
  6. The columns (2, 2, 1) and (1, -2, 2) are orthogonal of length 3, so G^{T}G = 9I and both singular values are 3. Every orthonormal basis of \mathbb{R}^2 is an eigenbasis of 9I, and \mathbf{u}_k = G\mathbf{v}_k/3 are orthonormal by the proof of Result 2. Both lie in \operatorname{im} G, so \mathbf{u}_3 = \pm\tfrac{1}{3}(2, -1, -2), orthogonal to both columns.
  7. M^{T}M = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix} has eigenvalues 4 with \displaystyle \tfrac{1}{\sqrt{2}}(1, 1) and 2 with \displaystyle \tfrac{1}{\sqrt{2}}(1, -1). By Result 4 the largest value is 2 at \displaystyle \pm\tfrac{1}{\sqrt{2}}(1, 1) and the smallest is \displaystyle \sqrt{2} at \displaystyle \pm\tfrac{1}{\sqrt{2}}(1, -1).
  8. An ellipse with semi-axes \displaystyle 4\sqrt{5} along (1, 1) and \displaystyle 2\sqrt{5} along (1, -1). \displaystyle B_1 = 4\sqrt{5}\,\mathbf{u}_1\mathbf{v}_1^{T} = \begin{bmatrix} 2 & 6 \\ 2 & 6 \end{bmatrix} and \displaystyle \lVert B - B_1 \rVert = 2\sqrt{5}. Also \displaystyle \det B = 40 = 4\sqrt{5} \cdot 2\sqrt{5}.
  9. \displaystyle C^{+} = \tfrac{1}{\sqrt{3}}\mathbf{v}_1\mathbf{u}_1^{T} + \mathbf{v}_2\mathbf{u}_2^{T}, that is, \tfrac{1}{3}\begin{bmatrix} 2 & -1 \\ 1 & 1 \\ -1 & 2 \end{bmatrix}, and multiplying gives CC^{+} = I_2.
  10. By the Riesz representation theorem (Result 7 of Orthonormal bases and Gram-Schmidt, proved), p(1) = \langle p, w \rangle with \displaystyle w = \sum_k q_k(1)q_k = q_1 + \sqrt{3}\,q_2 + \sqrt{5}\,q_3, that is, 30x^2 - 24x + 3, and \lVert w \rVert^2 = 1 + 3 + 5 = 9. As \varphi(p)c = \langle p, cw \rangle, \varphi^{*}c = cw and \varphi^{*}\varphi p = p(1)w: eigenvalue 9 on w, 0 on the plane orthogonal to w. So the singular values are 3, 0, 0, and by Result 4 the largest p(1) for unit p is 3, at w/3 = 10x^2 - 8x + 1.
  11. By Result 1, r = \operatorname{rank} T. T is injective exactly when \dim \ker T = 0, that is, by the fundamental theorem of linear maps, when r = n, which for a decreasing list means \sigma_n > 0. T is surjective exactly when \operatorname{rank} T = m, that is, when r = m.
  12. If every \sigma_k = 1, Result 4 gives \lVert T\mathbf{x} \rVert^2 = \sum_k |\langle \mathbf{x}, \mathbf{v}_k \rangle|^2 = \lVert \mathbf{x} \rVert^2. Conversely, if T keeps lengths, Result 1 gives \sigma_k = \lVert T\mathbf{v}_k \rVert = \lVert \mathbf{v}_k \rVert = 1.
  13. If R\mathbf{x} = \mathbf{0}, then \mathbf{x} = R^{*}R\mathbf{x} = \mathbf{0}, so R is injective, hence invertible on the finite-dimensional V (Invertibility and isomorphic spaces) with R^{-1} = R^{*}. By Result 2 of Adjoints and self-adjoint operators, (STR)^{*}(STR) = R^{*}T^{*}S^{*}STR, that is, R^{-1}(T^{*}T)R. If T^{*}T\mathbf{y} = \lambda\mathbf{y}, then R^{-1}T^{*}TR(R^{-1}\mathbf{y}) = \lambda R^{-1}\mathbf{y}, so R^{-1} maps E_\lambda(T^{*}T) injectively into the \lambda-eigenspace of R^{-1}T^{*}TR, and R maps back the same way. Equal eigenvalues with eigenspaces of equal dimension give equal singular values.
  14. Let T\mathbf{v} = \lambda\mathbf{v} with \lVert \mathbf{v} \rVert = 1. Then \lVert T\mathbf{v} \rVert = |\lambda|, and Result 4 gives \sigma_n \le |\lambda| \le \sigma_1.
  15. \langle \varphi(\mathbf{v}), c \rangle = \langle \mathbf{v}, \mathbf{w} \rangle\bar{c} = \langle \mathbf{v}, c\mathbf{w} \rangle, so \varphi^{*}c = c\mathbf{w} and \varphi^{*}\varphi\mathbf{v} = \langle \mathbf{v}, \mathbf{w} \rangle\mathbf{w}. If \mathbf{w} = \mathbf{0}, every singular value is 0 = \lVert \mathbf{w} \rVert. Otherwise \varphi^{*}\varphi\mathbf{w} = \lVert \mathbf{w} \rVert^2\mathbf{w} and \varphi^{*}\varphi\mathbf{v} = \mathbf{0} for \mathbf{v} \perp \mathbf{w}. By Result 6 of Orthonormal bases and Gram-Schmidt, proved, \mathbf{w}/\lVert \mathbf{w} \rVert followed by an orthonormal basis of the (n - 1)-dimensional \operatorname{span}\{\mathbf{w}\}^{\perp} is an orthonormal eigenbasis with eigenvalues \lVert \mathbf{w} \rVert^2, 0, \dots, 0.
  16. By Result 3, A = U\Sigma V^{T} with U, V real orthogonal and \Sigma = \operatorname{diag}(\sigma_1, \dots, \sigma_n). By the product and transpose rules of Properties of determinants: row operations, products, transposes, 1 = \det(U^{T}U) = (\det U)^2, so |\det U| = 1, and likewise |\det V^{T}| = 1. Hence |\det A| = \det \Sigma = \sigma_1\cdots\sigma_n.
  17. Take A = U\Sigma V^{*} (Result 3), with \Sigma square, real and diagonal with entries \sigma_k \ge 0. Put Q = UV^{*} and P = V\Sigma V^{*}. Then Q^{*}Q = VU^{*}UV^{*} = I; P^{*} = V\Sigma^{*}V^{*} = P; with \mathbf{y} = V^{*}\mathbf{x}, \mathbf{x}^{*}P\mathbf{x} = \mathbf{y}^{*}\Sigma\mathbf{y} = \sum_k \sigma_k|y_k|^2 \ge 0; and QP = UV^{*}V\Sigma V^{*} = A.
math.wiki · CC-BY-SA-4.0