Chapter 10 — Singular Value Decomposition

Linear Algebra and its Applications · IISc 2024 · typeset reproduction

Truncated SVD

Let \( A \in \R^{m\times n} \). Diagonalization can only be performed on square matrices, and even then not all square matrices can be diagonalized. The next best thing is the SVD.

Theorem 18 — Partial / compact SVD

Let \( A \in \R^{m\times n} \) (this also works for \( A \in \C^{m\times n} \)) and \( r = \rank(A) \ge 1 \). Then there exist orthonormal vectors \( v_1, \dots, v_r \in \R^n \), orthonormal vectors \( u_1, \dots, u_r \in \R^m \), and \( \sigma_1 \ge \dots \ge \sigma_r > 0 \) such that \[ A = \sigma_1 u_1 v_1\T + \dots + \sigma_r u_r v_r\T, \] and for \( A \in \C^{m\times n} \), \[ A = \sum_{i=1}^{r} \sigma_i u_i v_i\herm. \]

We call \( \sigma_1, \dots, \sigma_r \) the singular values of \(A\); \( u_1, \dots, u_r \) the left singular vectors of \(A\); and \( v_1, \dots, v_r \) the right singular vectors of \(A\).

Proof

Consider \( A \in \C^{m\times n} \). Let \( B = A\herm A \). Then \( B\herm = B \), so \( B \) is Hermitian, with \( B \in \C^{n\times n} \). For any \( x \in \C^n \) (scan: ℝⁿ), \[ \langle x, Bx \rangle = \langle x, A\herm A x \rangle = \langle Ax, Ax \rangle = \|Ax\|^2 \ge 0, \] so \( B \) is PSD (positive semi-definite).

Since \( \rank(A) = r \ge 1 \), we have \( \rank(B) = r \): with \( B = A\herm A \), \( \Null(A\herm A) = \Null(A) \) and \( \Range(A\herm A) = \Range(A\herm) \) (Ch. 5, Theorem 9), so \[ \rank(A\herm A) = \rank(A\herm) = \rank(A) \] (transposing and conjugating does not change the rank of a matrix).

Consider the eigenvalue decomposition of \( B = A\herm A \): \[ B = V \Lambda V\herm, \] where \( \Lambda = \diag(\lambda_1, \dots, \lambda_n) \) holds the eigenvalues of \(B\) (which are real) and \( V = [\,v_1 \ \cdots \ v_n\,] \) is unitary with columns an ONB of eigenvectors of \(B\). Since \(B\) is PSD with \( \rank(B) = r \), WLOG \[ \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_r > 0, \qquad \lambda_{r+1} = \dots = \lambda_n = 0. \] So \[ B = V \Lambda V\herm = \sum_{j=1}^{r} \lambda_j v_j v_j\herm. \]

Put \( \sigma_i = \sqrt{\lambda_i} \) and \( u_i = \dfrac{1}{\sigma_i} A v_i \), \( i = 1, \dots, r \). The \( v_1, \dots, v_r \) are orthonormal by construction. For the \( u_i \): \[\begin{aligned} \langle u_i, u_j \rangle &= \Big\langle \tfrac{1}{\sqrt{\lambda_i}} A v_i,\ \tfrac{1}{\sqrt{\lambda_j}} A v_j \Big\rangle \\ &= \tfrac{1}{\sqrt{\lambda_i}\sqrt{\lambda_j}} \langle v_i, A\herm A v_j \rangle \\ &= \tfrac{1}{\sqrt{\lambda_i \lambda_j}} \langle v_i, \lambda_j v_j \rangle = \tfrac{\lambda_j}{\sqrt{\lambda_i \lambda_j}} \langle v_i, v_j \rangle, \end{aligned}\] so \( \langle u_i, u_j \rangle = \dfrac{\sqrt{\lambda_j}}{\sqrt{\lambda_i}}\, \delta_{ij} = \dfrac{\sigma_j}{\sigma_i}\, \delta_{ij} \). Hence \( u_1, \dots, u_r \) are orthonormal.

Claim: \( A = \displaystyle\sum_{j=1}^{r} \sigma_j u_j v_j\herm \). (A matrix is specified by its action on all vectors.) For \( x \in \C^n \), the claim gives \[ Ax = \sum_{j=1}^{r} \sigma_j u_j v_j\herm x = \sum_{j=1}^{r} \sigma_j \langle v_j, x \rangle u_j. \] Since \( v_1, \dots, v_n \) form an ONB, any \( x \in \C^n \) can be written as \( x = \sum_{i=1}^{n} \langle v_i, x \rangle v_i \) (Ch. 4, Ex 51). Therefore \[ Ax = \sum_{i=1}^{n} \langle v_i, x \rangle A v_i. \] Now \( v_{r+1}, \dots, v_n \) are eigenvectors of \( A\herm A \) for the zero eigenvalue, so \( v_{r+1}, \dots, v_n \in \Null(A\herm A) = \Null(A) \), giving \( A v_j = 0 \) for \( j = r+1, \dots, n \). Thus \[ Ax = \sum_{i=1}^{r} \langle v_i, x \rangle A v_i, \quad\text{and since } u_i = \tfrac{1}{\sigma_i} A v_i \implies A v_i = \sigma_i u_i, \] \[ Ax = \sum_{i=1}^{r} \langle v_i, x \rangle \sigma_i u_i = \sum_{i=1}^{r} \sigma_i u_i v_i\herm x, \] which proves the claim, and hence the theorem.

The idea of the proof. We wanted \( A = \sum_{j=1}^{r} \sigma_j u_j v_j\herm \). Suppose it were so. Then \[ A\herm A = \Big(\sum_i \sigma_i v_i u_i\herm\Big)\Big(\sum_j \sigma_j u_j v_j\herm\Big) = \sum_{i=1}^{r} \sigma_i^2 v_i v_i\herm. \] So we get the singular values and right singular vectors from \( A\herm A \); setting \( u_j \) appropriately gave us what we needed.

View original handwritten scans — Truncated SVD & proof (pages 1–5)
Original handwritten page 1 Original handwritten page 2 Original handwritten page 3 Original handwritten page 4 Original handwritten page 5

Full SVD

By extending the orthonormal vectors into an ONB, we can write \[ A = U \Sigma V\T \qquad (\text{Full SVD of } A). \] Here \( A \in \C^{m\times n} \), \( U \in \C^{m\times m} \), \( V \in \C^{n\times n} \), and \( \rank(A) = r \). \( \Sigma \) is a diagonal matrix with \[ \Sigma_{ij} = \begin{cases} \sigma_i & 1 \le i = j \le r \\ 0 & \text{otherwise} \end{cases} \]

Remark

SVD and the eigen-decomposition of \(A\) may not be the same, even if \(A\) is Hermitian: eigenvalues can be negative, but singular values are non-negative by construction. However, they are the same if \(A\) is PSD.

Ex 96

Prove that for \( A \in \R^{m\times n} \), \[ \sigma_1(A) = \max\big\{ \|Ax\|_{\R^m} : \|x\|_{\R^n} = 1 \big\}, \] where \( \|\cdot\|_{\R^m} \) and \( \|\cdot\|_{\R^n} \) are the Euclidean norms on \( \R^m \) and \( \R^n \). In other words, \( \sigma_1(A) = \|A\|_2 \), the spectral norm of \(A\) — the matrix norm induced by the standard Euclidean norms.

Solution

Let \( x \in \R^n \), \( \|x\| = 1 \), and \( A = \sum_{i=1}^{r} \sigma_i u_i v_i\herm \) where \( r = \rank(A) \), \( \sigma_1 \ge \dots \ge \sigma_r > 0 \). Then \[ Ax = \sum_{i=1}^{r} \sigma_i u_i v_i\herm x = \sum_{i=1}^{r} \sigma_i \langle v_i, x \rangle u_i. \]

So \[\begin{aligned} \|Ax\|^2 &= \langle Ax, Ax \rangle \\ &= \Big\langle \sum_{i=1}^{r} \sigma_i \langle v_i,x\rangle u_i,\ \sum_{j=1}^{r} \sigma_j \langle v_j,x\rangle u_j \Big\rangle \\ &= \sum_{i=1}^{r}\sum_{j=1}^{r} \sigma_i \sigma_j \langle v_i,x\rangle \langle v_j,x\rangle \underbrace{\langle u_i,u_j\rangle}_{\delta_{ij}} \\ &= \sum_{i=1}^{r} \sigma_i^2 \langle v_i,x\rangle^2 \\ &\le \sigma_1^2 \sum_{i=1}^{r} \langle v_i,x\rangle^2 \\ &\le \sigma_1^2 \underbrace{\sum_{i=1}^{n} \langle v_i,x\rangle^2}_{=\,\|x\|^2 =\, 1} = \sigma_1^2, \end{aligned}\] using \( \sum_{i=1}^{r} \langle v_i,x\rangle^2 \le \sum_{i=1}^{n} \langle v_i,x\rangle^2 = \|x\|^2 = 1 \) (the \( v_1, \dots, v_n \) are a full ONB of \( \R^n \)). Thus \( \|Ax\|^2 \le \sigma_1^2 \ \forall\, x \in \R^n,\ \|x\|=1 \), with equality at \( x = \pm v_1 \) (then \( \langle v_1,x\rangle^2 = 1 \) and \( \langle v_i,x\rangle = 0,\ i \ge 2 \)). So \[ \max_{\|x\|=1} \|Ax\| = \sigma_1(A) \implies \sigma_1(A) = \|A\|_2. \]

Correction

The scan (pages 7–8) writes the bound without the square — \( \|Ax\|^2 \le \sigma_1 \) — but pulling the largest singular value out of \( \sum_{i=1}^{r} \sigma_i^2 \langle v_i,x\rangle^2 \) leaves \( \le \sigma_1^2 \sum_{i=1}^{r}\langle v_i,x\rangle^2 = \sigma_1^2 \). Taking square roots recovers \( \|Ax\| \le \sigma_1 \), so the conclusion \( \sigma_1 = \|A\|_2 \) is unaffected.

Consider the full SVD, \( A = U\Sigma V\herm \) (or \( A = U\Sigma V\T \) for \( A \in \R^{m\times n} \)). Let \( A \in \R^{m\times n} \), let \( v_1, \dots, v_n \in \R^n \) be the columns of \(V\) and \( u_1, \dots, u_m \in \R^m \) the columns of \(U\). The following result relates these to the four fundamental subspaces of \(A\).

Ex 97

Show that \( \Range(A) = \operatorname{span}(u_1, \dots, u_r) \) and \( \Null(A) = \operatorname{span}(v_{r+1}, \dots, v_n) \). Equivalently, \( \Range(A\T) = \operatorname{span}(v_1, \dots, v_r) \) and \( \Null(A\T) = \operatorname{span}(u_{r+1}, \dots, u_m) \).

Solution

Consider any \( x \in \R^n \); \( v_1, \dots, v_n \) forms an ONB of \( \R^n \). With \( A = U\Sigma V\T \) and \(V\) orthogonal, \( V\T = V^{-1} \), hence \( AV = U\Sigma \). So \[ A[\,v_1 \ \cdots \ v_n\,] = [\,u_1 \ \cdots \ u_m\,]\,\Sigma \implies [\,Av_1 \ \cdots \ Av_n\,] = [\,\sigma_1 u_1 \ \cdots \ \sigma_r u_r \ 0 \ \cdots \ 0\,], \] giving \( A v_i = \sigma_i u_i \) (\( i = 1, \dots, r \)) and \( A v_j = 0 \) (\( j = r+1, \dots, n \)).

So \( v_{r+1}, \dots, v_n \in \Null(A) \); they are LI (by construction) with \( \dim \operatorname{span}(v_{r+1}, \dots, v_n) = n - r \). Since \( \rank(A) = r \), by rank–nullity \( \dim \R^n = \rank(A) + \nullity(A) \), so \( n = r + \nullity(A) \), i.e. \( \nullity(A) = n - r \). Hence \( v_{r+1}, \dots, v_n \) is a list of LI vectors of the right length, so they form a basis of \( \Null(A) \): \[ \Null(A) = \operatorname{span}(v_{r+1}, \dots, v_n). \]

Since \( v_1, \dots, v_n \) form an ONB of \( \R^n \), any \( x \in \R^n \) is \( x = a_1 v_1 + \dots + a_n v_n \), \( a_i \in \R \). Then \[ Ax = a_1 A v_1 + \dots + a_n A v_n = a_1 \sigma_1 u_1 + \dots + a_r \sigma_r u_r + 0 + \dots + 0 = \sum_{i=1}^{r} a_i \sigma_i u_i. \] So any \( Ax \in \R^m \) is a linear combination of \( u_1, \dots, u_r \); these are LI and, since \( \rank(A) = r \), they form a basis of \( \Range(A) \): \[ \Range(A) = \operatorname{span}(u_1, \dots, u_r). \]

Remark

Similar to Theorem 17 (variational characterization / Courant–Fischer), we have the following min–max characterization.

Ex 98

Show that, for all \( 1 \le k \le r \), \[ \sigma_k = \max_{\dim U = k} \ \min\big\{ \|Ax\|_2 : x \in U,\ \|x\|_2 = 1 \big\}, \] where \(U\) is a subspace of \( V = \R^n \).

Solution

From Theorem 17, for a self-adjoint \(T\) with eigenvalues \( \lambda_1 \ge \dots \ge \lambda_n \), \[ \lambda_k = \max_{\dim U = k} \ \min\big\{ \langle x, Tx \rangle : x \in U,\ \|x\| = 1 \big\}. \] Here \( A \in \R^{m\times n} \) and \( \|Ax\|^2 = \langle Ax, Ax \rangle = \langle x, A\T A x \rangle \). Since \( B = A\T A \) is symmetric, we can use Theorem 17: \[ \lambda_k = \max_{\dim U = k} \ \min_{\substack{x \in U \\ \|x\|=1}} \langle x, A\T A x \rangle, \] where the \( \lambda_k \) are eigenvalues of \( A\T A \). From the proof of the SVD (Theorem 18), \( \sigma_k = \sqrt{\lambda_k} \). Hence \[ \sigma_k = \max_{\dim U = k} \ \min_{\substack{x \in U \\ \|x\|=1}} \|Ax\|. \]

Remark

An important special case is that the largest singular value is simply the spectral norm of the matrix: \( \sigma_1(A) = \|A\|_2 \).

Ex 99

Let \( A \in \R^{m\times n} \) with \( \rank(A) = r \) and singular values \( \sigma_1 \ge \dots \ge \sigma_r \). If \( \|E\|_2 < \sigma_r \), prove that \( \rank(A + E) \ge r \). (A "small" perturbation cannot reduce the rank of a matrix.)

Solution

For any \( x \) with \( \|x\| = 1 \), the triangle inequality gives \( \|(A+E)x\| \ge \|Ax\| - \|Ex\| \ge \|Ax\| - \|E\|_2 \) (since \( \|Ex\| \le \|E\|_2 \)). Taking the \( \min \) over a \(k\)-dimensional subspace and then the \( \max \) over such subspaces, the min–max characterization (Ex 98 (scan: Ex 97)) yields the Weyl bound \[ \sigma_k(A+E) \ \ge\ \sigma_k(A) - \|E\|_2 \qquad (1 \le k \le r). \] For each \( k = 1, \dots, r \), \( \sigma_k(A) \ge \sigma_r(A) > \|E\|_2 \) (given), so \( \sigma_k(A+E) \ge \sigma_k(A) - \|E\|_2 > 0 \). Thus \( A+E \) has at least \(r\) strictly positive singular values, i.e. \( \rank(A+E) \ge r \).

Correction — Ex 99 bound

The original bounded \( \|Ex\| \) by \( \sigma_r(A) \) (the limit in the hypothesis) rather than by the actual perturbation size \( \|E\|_2 \), arriving at \( \sigma_k(A+E) \ge \sigma_k(A) - \sigma_r(A) \). For \( k = r \) that only gives \( \sigma_r(A+E) \ge 0 \), which does not force the rank to stay \( \ge r \). Using \( \|E\|_2 \) gives \( \sigma_k(A+E) \ge \sigma_k(A) - \|E\|_2 > 0 \) for all \( k \le r \) (as \( \sigma_k(A) \ge \sigma_r(A) > \|E\|_2 \)) — the strict positivity the conclusion needs.

We can use the SVD to define two important matrix norms:

Ex 100

Let the SVD of \(A\) be \( A = \sum_{i=1}^{r} \sigma_i u_i v_i\T \) for \( A \in \R^{m\times n} \). Define \( \|A\|_2 = \sigma_1 \) and \( \|A\|_* = \sigma_1 + \dots + \sigma_r \). Verify that these are matrix norms on \( \R^{m\times n} \). Moreover, prove that they are dual to each other, in the sense that \[ \|A\|_* = \max_{\|X\|_2 \le 1} \tr(X\T A), \qquad \|A\|_2 = \max_{\|X\|_* \le 1} \tr(X\T A), \] where the variable \( X \in \R^{m\times n} \). [The original left the two duals and nuclear-norm submultiplicativity incomplete, and its triangle-inequality argument was flawed; both are corrected/completed in review below.]

Solution

\( \|A\|_2 = \sigma_1 \) is a matrix norm.

\( \|A\|_* = \sigma_1 + \dots + \sigma_r \) is a matrix norm.

Correction — Ex 100 nuclear-norm triangle inequality

The original proof of \( \|A+B\|_*\le\|A\|_*+\|B\|_* \) summed a per-singular-value bound \( \sigma_k(A+B)\le\sigma_k(A)+\sigma_k(B) \). That bound is false: with \( A=\diag(1,0) \), \( B=\diag(0,1) \), \( \sigma_2(A+B)=1 \) but \( \sigma_2(A)+\sigma_2(B)=0 \). The nuclear-norm triangle inequality is nevertheless true; it follows from the dual characterization (below).

Solution — Ex 100 duals & remaining parts, added in review

Write \( A=\sum_{i=1}^r\sigma_i u_i v_i\T \) (SVD); the trace pairing is \( \tr(X\T A)=\sum_{i,j}X_{ij}A_{ij} \).

Dual of the nuclear norm: \( \|A\|_* = \displaystyle\max_{\|X\|_2\le1}\tr(X\T A) \). (\(\le\)) \( \tr(X\T A)=\sum_i\sigma_i\,(u_i\T X v_i) \), and \( |u_i\T X v_i|\le\|u_i\|\,\|Xv_i\|\le\|X\|_2\le1 \), so \( \tr(X\T A)\le\sum_i\sigma_i=\|A\|_* \). (\(\ge\)) Take \( X_0=\sum_i u_i v_i\T \); its singular values are all \(1\), so \( \|X_0\|_2=1 \), and \( \tr(X_0\T A)=\sum_{i,j}\sigma_j(u_i\T u_j)(v_j\T v_i)=\sum_i\sigma_i=\|A\|_* \). Hence the maximum is \( \|A\|_* \).

Triangle inequality. \( \|A+B\|_*=\displaystyle\max_{\|X\|_2\le1}\tr\big(X\T(A+B)\big)\le\max_{\|X\|_2\le1}\tr(X\T A)+\max_{\|X\|_2\le1}\tr(X\T B)=\|A\|_*+\|B\|_* \).

Dual of the spectral norm: \( \|A\|_2 = \displaystyle\max_{\|X\|_*\le1}\tr(X\T A) \). (\(\le\)) With \( X=\sum_k\tau_k a_k b_k\T \) (SVD of \(X\), \( \sum_k\tau_k=\|X\|_* \)), \( \tr(X\T A)=\sum_k\tau_k\,(a_k\T A b_k)\le\sum_k\tau_k\|A\|_2=\|X\|_*\|A\|_2\le\|A\|_2 \). (\(\ge\)) Take \( X=u_1 v_1\T \), so \( \|X\|_*=1 \) and \( \tr(X\T A)=u_1\T A v_1=\sigma_1=\|A\|_2 \).

Submultiplicativity of \( \|\cdot\|_* \). By the min–max form (Ex 98), \( \sigma_k(AB)=\max_{\dim U=k}\min_{x\in U,\,\|x\|=1}\|ABx\|\le\|A\|_2\,\sigma_k(B) \) (as \( \|ABx\|\le\|A\|_2\|Bx\| \)). Summing over \(k\), \( \|AB\|_*=\sum_k\sigma_k(AB)\le\|A\|_2\sum_k\sigma_k(B)=\|A\|_2\,\|B\|_*\le\|A\|_*\,\|B\|_* \), using \( \|A\|_2=\sigma_1(A)\le\sum_i\sigma_i(A)=\|A\|_* \).

View original handwritten scans — Full SVD, spectral & nuclear norms (pages 6–16)
Original handwritten page 6 Original handwritten page 7 Original handwritten page 8 Original handwritten page 9 Original handwritten page 10 Original handwritten page 11 Original handwritten page 12 Original handwritten page 13 Original handwritten page 14 Original handwritten page 15 Original handwritten page 16

Moore–Penrose Pseudoinverse

The Moore–Penrose pseudoinverse \( A^{+} \) is characterized by four properties:

For a given matrix \(A\), the Moore–Penrose pseudoinverse \( A^{+} \) is unique.

Ex 101

Let \( A \in \R^{m\times n} \) with partial SVD \( A = \sum_{j=1}^{r} \sigma_j u_j v_j\T \). Verify that \[ A^{+} = \sigma_1^{-1} v_1 u_1\T + \dots + \sigma_r^{-1} v_r u_r\T \] satisfies the four defining properties of the Moore–Penrose pseudoinverse of \(A\). Moreover, for all \( A \in \R^{m\times n} \) and \( b \in \R^m \):

  1. Verify that \( x_0 = A^{+}b \) is a solution of the normal equation \( A\T A x = A\T b \).
  2. If \(x\) is any solution of the normal equation, prove that \( x - x_0 \perp x_0 \).
  3. Of all solutions of the normal equation, prove that \( x_0 \) has the smallest \( \|\cdot\|_2 \)-norm.

Solution — verifying the four properties

With \( A = \sigma_1 u_1 v_1\T + \dots + \sigma_r u_r v_r\T \) and \( A^{+} = \sigma_1^{-1} v_1 u_1\T + \dots + \sigma_r^{-1} v_r u_r\T \):

(i) \( AA^{+} \) is symmetric. \[\begin{aligned} AA^{+} &= \Big(\sum_{i=1}^{r}\sigma_i u_i v_i\T\Big)\Big(\sum_{j=1}^{r}\sigma_j^{-1} v_j u_j\T\Big) \\ &= \sum_{i=1}^{r}\sum_{j=1}^{r} \sigma_i \sigma_j^{-1} u_i \underbrace{v_i\T v_j}_{\delta_{ij}} u_j\T \\ &= \sum_{i=1}^{r} \sigma_i \sigma_i^{-1} u_i u_i\T, \end{aligned}\] so \( AA^{+} = \sum_{i=1}^{r} u_i u_i\T \) and \( (AA^{+})\T = \sum_{i=1}^{r} u_i u_i\T = AA^{+} \). Hence \( AA^{+} \) is symmetric.

(ii) \( A^{+}A \) is symmetric. \[ A^{+}A = \sum_{i=1}^{r}\sum_{j=1}^{r} \sigma_i^{-1}\sigma_j v_i \underbrace{u_i\T u_j}_{\delta_{ij}} v_j\T = \sum_{i=1}^{r} v_i v_i\T, \] and \( (A^{+}A)\T = \sum_{i=1}^{r} v_i v_i\T = A^{+}A \). Hence \( A^{+}A \) is symmetric.

Alternate way. With \( A = U\Sigma V\T \), \( A^{+} = V\Sigma^{+}U\T \), \( \Sigma = \diag(\sigma_1, \dots, \sigma_r, 0, \dots) \), \( \Sigma^{+} = \diag(\sigma_1^{-1}, \dots, \sigma_r^{-1}, 0, \dots) \): \[ AA^{+} = U\Sigma V\T V\Sigma^{+}U\T = U\Sigma\Sigma^{+}U\T = U\begin{bmatrix}1 & & & \\ & \ddots & & \\ & & 1 & \\ & & & 0\end{bmatrix}U\T, \qquad A^{+}A = V\Sigma^{+}\Sigma V\T = V\begin{bmatrix}1 & & & \\ & \ddots & & \\ & & 1 & \\ & & & 0\end{bmatrix}V\T. \]

(iii) \( AA^{+}A = A \). \[\begin{aligned} AA^{+}A &= \Big(\sum_{i=1}^{r} u_i u_i\T\Big)\Big(\sum_{j=1}^{r}\sigma_j u_j v_j\T\Big) \\ &= \sum_{i=1}^{r}\sum_{j=1}^{r} \sigma_j u_i \underbrace{u_i\T u_j}_{\delta_{ij}} v_j\T \\ &= \sum_{i=1}^{r}\sigma_i u_i v_i\T = A. \end{aligned}\]

(iv) \( A^{+}AA^{+} = A^{+} \). \[\begin{aligned} A^{+}AA^{+} &= \Big(\sum_{i=1}^{r} v_i v_i\T\Big)\Big(\sum_{j=1}^{r}\sigma_j^{-1} v_j u_j\T\Big) \\ &= \sum_{i=1}^{r}\sum_{j=1}^{r} \sigma_j^{-1} v_i \underbrace{v_i\T v_j}_{\delta_{ij}} u_j\T \\ &= \sum_{i=1}^{r}\sigma_i^{-1} v_i u_i\T = A^{+}. \end{aligned}\]

Alternately, in matrix notation: \[\begin{aligned} AA^{+}A &= (U\Sigma\Sigma^{+}U\T)(U\Sigma V\T) = U\Sigma\Sigma^{+}\Sigma V\T = U\Sigma V\T = A, \\ A^{+}AA^{+} &= (V\Sigma^{+}\Sigma V\T)(V\Sigma^{+}U\T) = V\Sigma^{+}\Sigma\Sigma^{+}U\T = V\Sigma^{+}U\T = A^{+}. \end{aligned}\] Hence \( A^{+} \) is a Moore–Penrose pseudoinverse.

Solution — (1) \( x_0 = A^{+}b \) solves \( A\T A x = A\T b \)

With \( A = U\Sigma V\T \), \( A^{+} = V\Sigma^{+}U\T \), put \( x_0 = A^{+}b \) into the LHS: \[ A\T A A^{+}b = (V\Sigma U\T)(UU\T)b = V\Sigma\,\underbrace{(U\T U)}_{I}\,U\T b = V\Sigma U\T b = A\T b = \text{RHS}. \] Therefore \( x_0 = A^{+}b \) is indeed a solution of \( A\T A x = A\T b \).

Solution — (2) \( x - x_0 \perp x_0 \)

If \(x\) is any solution, \( A\T A x_0 = A\T b \) and \( A\T A x = A\T b \), so \( A\T A x_0 = A\T A x \), giving \( A\T A (x - x_0) = 0 \), i.e. \( x - x_0 \in \Null(A) \).

Now we show \( A^{+} = (A\T A)^{+} A\T \). With \( A = U\Sigma V\T \), \( A^{+} = V\Sigma^{+}U\T \): \[\begin{aligned} (A\T A)^{+} A\T &= (V\Sigma U\T U\Sigma V\T)^{+}(V\Sigma U\T) \\ &= (V\Sigma^2 V\T)^{+}(V\Sigma U\T) \\ &= V(\Sigma^{+})^2 V\T V\Sigma U\T \\ &= V\Sigma^{+}\Sigma\Sigma^{+}U\T = V\Sigma^{+}U\T = A^{+}, \end{aligned}\] using that for diagonal \( A, B, C \), \( ABC = ACB \), so \( \Sigma^{+}\Sigma^{+}\Sigma = \Sigma^{+}\Sigma\Sigma^{+} \).

Then \[ x_0 = A^{+}b = (A\T A)^{+} A\T b = (A\T A)^{+} A\T A x. \] Let \( B = A\T A = V\Sigma^2 V\T \), \( B^{+} = V(\Sigma^{+})^2 V\T \). Since \( \Sigma, \Sigma^{+} \) are diagonal (so their products commute), \[\begin{aligned} BB^{+} &= V\Sigma^2 V\T V(\Sigma^{+})^2 V\T \\ &= V\Sigma^2(\Sigma^{+})^2 V\T = V(\Sigma^{+})^2\Sigma^2 V\T = B^{+}B, \end{aligned}\] hence \( x_0 = (A\T A)^{+} A\T A x = (A\T A)(A\T A)^{+} x \). Therefore \[\begin{aligned} \langle x - x_0, x_0 \rangle &= \langle x - x_0, (A\T A)(A\T A)^{+}x \rangle \\ &= \langle (A\T A)\T(x - x_0), (A\T A)^{+}x \rangle \\ &= \big\langle \underbrace{(A\T A)(x - x_0)}_{=\,0\ \text{as } x - x_0 \in \Null(A\T A)}, (A\T A)^{+}x \big\rangle = 0. \end{aligned}\] So \( \langle x - x_0, x_0 \rangle = 0 \implies x - x_0 \perp x_0 \). Thus if \(x\) is any solution of the normal equation, \( x - x_0 \perp x_0 \).

Solution — (3) \( x_0 \) has the smallest norm

Let \(x\) be any solution to \( A\T A x = A\T b \). Then \( x - x_0 \perp x_0 \), so \[ \|x\|^2 = \|x - x_0 + x_0\|^2 = \|x - x_0\|^2 + \|x_0\|^2 \quad\text{(by the Pythagoras theorem)}, \] hence \( \|x\|^2 \ge \|x_0\|^2 \). So \( \|x\|_2 \) is minimized when \( x = x_0 \); that is, \( x_0 \) has the smallest \( \|\cdot\|_2 \)-norm.

View original handwritten scans — Moore–Penrose pseudoinverse (pages 17–23)
Original handwritten page 17 Original handwritten page 18 Original handwritten page 19 Original handwritten page 20 Original handwritten page 21 Original handwritten page 22 Original handwritten page 23