The Singular Value Decomposition in Statistics

One decomposition beneath principal components, latent semantic indexing, least squares and ridge regression. The SVD proved to exist without the spectral theorem; the trace maximum principle, the best low-rank approximation with a uniqueness condition, and how singular values move under perturbation and centering; principal components proved to be the SVD of the centered data, on seven NHANES body measurements; LSI as the uncentered SVD of the Cranfield matrix; the pseudo-inverse and ridge as filters on singular values. Worked problems compute a decomposition, a pseudo-inverse and its ridge path, and the effect of centering by hand.

The National Health and Nutrition Examination Survey (NHANES) of 2017 to 2018 measured the bodies of its examined adults (National Center for Health Statistics, 2020). For 4,913 adults all seven of the measurements used here are recorded: height, weight, upper leg length, upper arm length, arm circumference, waist and hip. They move together. Weight correlates 0.47 with height and waist correlates 0.86 with hip, yet height and waist correlate only 0.20. Principal Component Analysis would summarize such data by the eigenvectors of their correlation matrix. Latent Semantic Indexing summarizes a matrix of 4,803 terms by 1,400 Cranfield abstracts with the singular value decomposition. The Geometry of Least Squares and Ridge and Lasso Regression solve regressions through the same decomposition. Is there one result beneath all four, and what exactly does it guarantee about each? There is. Every matrix is a sum of rank-one layers ordered by size, keeping the largest layers gives the best approximation of any given rank, and each of the four methods is a choice of which matrix to decompose and which layers to keep or reweight.

The singular value decomposition (SVD) of an $n \times p$ matrix $A$ of rank $r$ writes it as $A = UDV^{\mathsf T}$. The matrix $U$ is $n \times r$ with orthonormal columns, $V$ is $p \times r$ with orthonormal columns, and $D = \operatorname{diag}(d_1, \ldots, d_r)$ holds the singular values $d_1 \ge d_2 \ge \cdots \ge d_r > 0$. This article is the statistics collection's home for the decomposition, as The Geometry of Least Squares anticipates; Latent Semantic Indexing remains the home of its use in retrieval.

Here is the route. First we prove that the decomposition exists, by an argument that needs no spectral theorem. Then we take the best low-rank approximation theorem from Latent Semantic Indexing, which proves it in both norms, and add what statistics needs: the trace maximum principle with its equality case, a second proof of the Frobenius statement that also settles when the best approximation is unique, and the inequalities that say how singular values move when the matrix is perturbed or centered. Next we prove that principal components are the decomposition of the centered data, on the seven body measurements. Then we read latent semantic indexing as the decomposition of an uncentered matrix, on Cranfield. Finally we write least squares, the pseudo-inverse and ridge regression as operations on the singular values. The article assumes vectors, matrices, orthonormal bases and rank, and the covariance matrix of Covariance Matrices and Quadratic Forms.

Notation and the two datasets

Vectors are columns, written in bold lowercase; matrices are capitals; $^{\mathsf T}$ is the transpose. The unit's notation is kept (Multivariate Statistics): $n$ observations of $p$ variables form the rows of an $n \times p$ data matrix $X$, $\bar{\mathbf x}$ is the vector of column means, $S = \frac{1}{n-1}\sum_i (\mathbf x_i - \bar{\mathbf x})(\mathbf x_i - \bar{\mathbf x})^{\mathsf T}$ is the sample covariance matrix, and $\Sigma$ is a population covariance matrix. Because $\Sigma$ is taken, the diagonal matrix of singular values is $D$, as in Principal Component Analysis and Ridge and Lasso Regression; Latent Semantic Indexing writes $\Sigma$ and $\sigma_k$ for the same objects. For a general matrix we write $A$, and $d_j(A)$ for its $j$th singular value, with $d_j(A) = 0$ for $j > r$. The centered data matrix is $\tilde X$, with rows $(\mathbf x_i - \bar{\mathbf x})^{\mathsf T}$, so $S = \tilde X^{\mathsf T}\tilde X/(n-1)$.

Two norms measure a matrix. The Frobenius norm $\lVert A \rVert_F$ is the square root of the sum of its squared entries; $\lVert A \rVert_F^2 = \operatorname{tr}(A^{\mathsf T}A)$. The spectral norm $\lVert A \rVert_2 = \max_{\lVert \mathbf x \rVert = 1}\lVert A\mathbf x \rVert$ is the largest factor by which $A$ stretches a vector.

The body measurements. NHANES files DEMO_J, BPX_J and BMX_J give, for the 5,247 examined adults with a blood pressure reading that the statistics collection uses throughout, the seven measurements above in centimeters (weight in kilograms). The 4,913 with all seven recorded form $X$, $4{,}913 \times 7$. The adults are treated as a finite population, without the survey's sampling weights, as in the collection's other units.

The Cranfield matrix. The 1,400 Cranfield abstracts (Cleverdon, 1967), stemmed and stopped as in Latent Semantic Indexing, give a term–document matrix $C$ of 4,803 terms by 1,400 documents. Each entry is the weight $(1 + \log_{10}\mathit{tf})\log_{10}(N/\mathit{df})$ and each document column is scaled to length 1, exactly as in that article's Cranfield experiment. Two abstracts contain no indexed term, so their columns are zero; the other 1,398 columns are linearly independent (the script computes the rank), so the rank of $C$ is 1,398.

The decomposition exists

Latent Semantic Indexing builds the SVD from the eigenvectors of $A^{\mathsf T}A$, taking the spectral theorem for symmetric matrices as given. Here is a proof that assumes nothing beyond the fact that a continuous function on a closed bounded set attains its maximum. The idea in plain words: find the direction that $A$ stretches most, show that $A$ maps everything perpendicular to that direction to something perpendicular to its image, and repeat on what is left. The first singular value is the largest stretch, and every later one is the largest stretch among directions perpendicular to the earlier ones.

Lemma 1 (the largest stretch). Let $A$ be $n \times p$ and not zero. Let $\mathbf v$ be a unit vector at which $\lVert A\mathbf x \rVert$ attains its maximum $d > 0$ over unit vectors, and put $\mathbf u = A\mathbf v/d$. Then for every $\mathbf w$ orthogonal to $\mathbf v$, $A\mathbf w$ is orthogonal to $\mathbf u$. Consequently $A^{\mathsf T}\mathbf u = d\,\mathbf v$.

Proof. The maximum exists because the unit sphere is closed and bounded and $\mathbf x \mapsto \lVert A\mathbf x \rVert$ is continuous. Take $\mathbf w \perp \mathbf v$ and a real $t$. The vector $\mathbf v + t\mathbf w$ has squared length $1 + t^2\lVert \mathbf w \rVert^2$, so by the maximality of $d$, $$\lVert A(\mathbf v + t\mathbf w) \rVert^2 \le d^2(1 + t^2\lVert \mathbf w \rVert^2).$$ The left side is $d^2 + 2t\,(A\mathbf v)^{\mathsf T}A\mathbf w + t^2\lVert A\mathbf w \rVert^2$, and $A\mathbf v = d\mathbf u$. Cancelling $d^2$, $$2td\,\mathbf u^{\mathsf T}A\mathbf w \le t^2\big(d^2\lVert \mathbf w \rVert^2 - \lVert A\mathbf w \rVert^2\big) \quad \text{for every real } t.$$ Divide by $t > 0$ and let $t \to 0$: $\mathbf u^{\mathsf T}A\mathbf w \le 0$. Divide by $t < 0$, which reverses the inequality, and let $t \to 0$: $\mathbf u^{\mathsf T}A\mathbf w \ge 0$. So $\mathbf u^{\mathsf T}A\mathbf w = 0$. For the last claim, $A^{\mathsf T}\mathbf u$ has inner product $\mathbf u^{\mathsf T}A\mathbf w = 0$ with every $\mathbf w \perp \mathbf v$, so it is a multiple of $\mathbf v$, namely $(\mathbf v^{\mathsf T}A^{\mathsf T}\mathbf u)\mathbf v = (A\mathbf v)^{\mathsf T}\mathbf u\,\mathbf v = d\,\mathbf v$. $\square$

Theorem 1 (existence of the SVD). Every real $n \times p$ matrix $A$ of rank $r \ge 1$ can be written $$A = \sum_{j=1}^{r} d_j\,\mathbf u_j\mathbf v_j^{\mathsf T} = UDV^{\mathsf T},$$ with $\mathbf u_1, \ldots, \mathbf u_r$ orthonormal in $\mathbb R^n$, $\mathbf v_1, \ldots, \mathbf v_r$ orthonormal in $\mathbb R^p$ and $d_1 \ge \cdots \ge d_r > 0$. In addition, $A\mathbf v_j = d_j\mathbf u_j$, $A^{\mathsf T}\mathbf u_j = d_j\mathbf v_j$, $d_1 = \lVert A \rVert_2$, and $d_j$ is the largest value of $\lVert A\mathbf x \rVert$ over unit vectors $\mathbf x$ orthogonal to $\mathbf v_1, \ldots, \mathbf v_{j-1}$.

Proof. Build the vectors one at a time. Put $A_1 = A$. At step $j$, with $\mathbf v_1, \ldots, \mathbf v_{j-1}$ and $\mathbf u_1, \ldots, \mathbf u_{j-1}$ already chosen, put $A_j = A - \sum_{i<j} d_i\mathbf u_i\mathbf v_i^{\mathsf T}$. If $A_j = 0$, stop. Otherwise let $d_j$ be the maximum of $\lVert A_j\mathbf x \rVert$ over unit vectors, attained at $\mathbf v_j$, and $\mathbf u_j = A_j\mathbf v_j/d_j$. Four claims finish the proof; they are proved together by induction on $j$, so at step $j$ the earlier $\mathbf v_i$ are already known to be orthonormal (claim 2 at the earlier steps).

  1. $A_j\mathbf v_i = \mathbf 0$ for $i < j$, and $A_j\mathbf x = A\mathbf x$ for every $\mathbf x$ orthogonal to $\mathbf v_1, \ldots, \mathbf v_{j-1}$. The second is immediate from the definition of $A_j$, since $\mathbf v_i^{\mathsf T}\mathbf x = 0$ kills every subtracted term. For the first, $A_j\mathbf v_i = A\mathbf v_i - d_i\mathbf u_i$ by orthonormality, and $A\mathbf v_i = A_i\mathbf v_i = d_i\mathbf u_i$ by the second part applied at step $i$ (where $\mathbf v_i$ is orthogonal to the earlier vectors) and the definition of $\mathbf u_i$.
  2. $\mathbf v_j$ can be taken orthogonal to $\mathbf v_1, \ldots, \mathbf v_{j-1}$. Write any unit $\mathbf x$ as $\mathbf y + \sum_{i<j} c_i\mathbf v_i$ with $\mathbf y$ orthogonal to the earlier $\mathbf v_i$. By claim 1, $A_j\mathbf x = A_j\mathbf y$, and $\lVert \mathbf y \rVert \le 1$. So $\lVert A_j\mathbf x \rVert \le \lVert A_j(\mathbf y/\lVert \mathbf y \rVert) \rVert$ when $\mathbf y \ne \mathbf 0$, and $A_j\mathbf x = \mathbf 0$ when $\mathbf y = \mathbf 0$. The maximum is therefore attained at a unit vector orthogonal to the earlier $\mathbf v_i$; choose $\mathbf v_j$ there.
  3. $\mathbf u_j$ is orthogonal to $\mathbf u_1, \ldots, \mathbf u_{j-1}$. Let $i < j$. The vector $\mathbf v_j$ is orthogonal to $\mathbf v_1, \ldots, \mathbf v_i$, so by claim 1 (at steps $j$ and $i$) $A_j\mathbf v_j = A\mathbf v_j = A_i\mathbf v_j$. Lemma 1 applied to $A_i$, whose largest stretch is at $\mathbf v_i$, says that $A_i\mathbf v_j$ is orthogonal to $\mathbf u_i$ because $\mathbf v_j \perp \mathbf v_i$. So $d_j\mathbf u_j = A_j\mathbf v_j \perp \mathbf u_i$.
  4. The values do not increase, and the process stops with $A = \sum_j d_j\mathbf u_j\mathbf v_j^{\mathsf T}$. By claim 2, $d_j$ is the largest stretch of $A$ over unit vectors orthogonal to $\mathbf v_1, \ldots, \mathbf v_{j-1}$, a smaller set than at step $j - 1$, so $d_j \le d_{j-1}$. The $\mathbf v_j$ are orthonormal in $\mathbb R^p$, so there are at most $p$ steps. At the stop, $A_{m+1} = 0$, which is the displayed sum with $m$ terms.

The number of terms is the rank. The image of $A = \sum_{j \le m} d_j\mathbf u_j\mathbf v_j^{\mathsf T}$ lies in the span of $\mathbf u_1, \ldots, \mathbf u_m$ and contains each $\mathbf u_j = A\mathbf v_j/d_j$, so it is that span, of dimension $m$; hence $m = r$. Finally $A^{\mathsf T}\mathbf u_j = \sum_i d_i\mathbf v_i\mathbf u_i^{\mathsf T}\mathbf u_j = d_j\mathbf v_j$, and $d_1 = \lVert A \rVert_2$ by definition. $\square$

Two consequences are used below. First, $A^{\mathsf T}A\mathbf v_j = d_jA^{\mathsf T}\mathbf u_j = d_j^2\mathbf v_j$: the right singular vectors are eigenvectors of $A^{\mathsf T}A$ with eigenvalues $d_j^2$. Completing $\mathbf v_1, \ldots, \mathbf v_r$ to an orthonormal basis of $\mathbb R^p$ with vectors that $A$ sends to zero (any orthonormal basis of the orthogonal complement will do, by the formula for $A$) gives the full eigendecomposition $A^{\mathsf T}A = \sum_{j=1}^{p} d_j^2\mathbf v_j\mathbf v_j^{\mathsf T}$. Every sample covariance matrix has the form $\tilde X^{\mathsf T}\tilde X/(n-1)$, so this is the spectral decomposition of $S$, obtained without the spectral theorem; Covariance Matrices and Quadratic Forms treats the decomposition of a general symmetric matrix. Second, the layers $d_j\mathbf u_j\mathbf v_j^{\mathsf T}$ are orthogonal as matrices, so $\lVert A \rVert_F^2 = \sum_j d_j^2$; Latent Semantic Indexing proves this from the same formula.

How unique is it? The singular values are unique: they are the square roots of the positive eigenvalues of $A^{\mathsf T}A$, and the eigenvalues of a matrix are the roots of its characteristic polynomial. The vectors are not. Replacing $(\mathbf u_j, \mathbf v_j)$ by $(-\mathbf u_j, -\mathbf v_j)$ leaves every layer unchanged, which is the sign ambiguity Principal Component Analysis warns about; when $d_j = d_{j+1}$, rotating the pair $(\mathbf u_j, \mathbf u_{j+1})$ and the pair $(\mathbf v_j, \mathbf v_{j+1})$ by the same $2 \times 2$ orthogonal matrix gives another decomposition. The history of the decomposition, with the contributions of Beltrami, Jordan, Sylvester, Schmidt and Weyl, is surveyed by Stewart (1993).

Example (the body measurements). For the standardized seven measurements (each column centered and divided by its standard deviation), the singular values are 143.14, 99.52, 39.70, 30.55, 28.16, 23.47 and 11.71. Their squares sum to $(n - 1)p = 4{,}912 \times 7$, because every standardized column has squared length $n - 1$. The script checks that $d_j^2/(n-1)$ are the eigenvalues of the correlation matrix to $10^{-12}$.

The best low-rank approximation

Write $A_k = \sum_{j \le k} d_j\mathbf u_j\mathbf v_j^{\mathsf T}$ for the sum of the $k$ largest layers.

The Eckart–Young theorem. For every matrix $Z$ of rank at most $k$, $$\lVert A - Z \rVert_2 \ge d_{k+1} = \lVert A - A_k \rVert_2 \qquad \text{and} \qquad \lVert A - Z \rVert_F^2 \ge \sum_{j > k} d_j^2 = \lVert A - A_k \rVert_F^2.$$

Latent Semantic Indexing proves both inequalities in full, the spectral one by a dimension count and the Frobenius one from the spectral one, and this article uses them from there. Eckart and Young (1936) treated the problem for matrices under the least-squares (Frobenius) criterion and found, in the words of their abstract, that it "always has a solution which is usually unique". Stewart (1993) reports that Schmidt had already proved the approximation result in 1907, for integral equations, and that the name Eckart–Young is historically inaccurate; we keep it because it is standard and is the name used in Latent Semantic Indexing. What follows adds two things a statistician needs: a proof that comes from maximizing variance, which is the form in which principal components are usually derived, and a condition for uniqueness, $d_k > d_{k+1}$, which is sufficient and, whenever $d_{k+1} > 0$, also necessary.

The trace maximum principle

Here is the idea in plain words. A $k$-dimensional subspace captures, from a symmetric matrix with eigenvalues $\lambda_1 \ge \cdots \ge \lambda_p$, a weighted sum of the eigenvalues, with weights between 0 and 1 that add to $k$. The largest such sum puts weight 1 on the $k$ largest eigenvalues.

Theorem 2 (trace maximum). Let $B = \sum_{j=1}^p \lambda_j\mathbf q_j\mathbf q_j^{\mathsf T}$ with $\mathbf q_1, \ldots, \mathbf q_p$ orthonormal and $\lambda_1 \ge \cdots \ge \lambda_p$. For every $p \times k$ matrix $W$ with orthonormal columns, $$\operatorname{tr}(W^{\mathsf T}BW) \le \lambda_1 + \cdots + \lambda_k,$$ with equality when the columns of $W$ span $\mathbf q_1, \ldots, \mathbf q_k$. If $\lambda_k > \lambda_{k+1}$, equality holds only then.

Proof. Put $c_j = \lVert W^{\mathsf T}\mathbf q_j \rVert^2$. Then $\operatorname{tr}(W^{\mathsf T}BW) = \sum_j \lambda_j\operatorname{tr}(W^{\mathsf T}\mathbf q_j\mathbf q_j^{\mathsf T}W) = \sum_j \lambda_jc_j$. Two facts bound the weights. Each $c_j \le 1$: $WW^{\mathsf T}$ is the orthogonal projection onto the column space of $W$, so $c_j = \mathbf q_j^{\mathsf T}WW^{\mathsf T}\mathbf q_j = \lVert WW^{\mathsf T}\mathbf q_j \rVert^2 \le \lVert \mathbf q_j \rVert^2 = 1$; and $c_j \ge 0$. They sum to $k$: $\sum_j c_j = \sum_j \mathbf q_j^{\mathsf T}WW^{\mathsf T}\mathbf q_j = \operatorname{tr}(WW^{\mathsf T}\sum_j\mathbf q_j\mathbf q_j^{\mathsf T}) = \operatorname{tr}(WW^{\mathsf T}) = \operatorname{tr}(W^{\mathsf T}W) = k$. Now $$\sum_{j \le k}\lambda_j - \sum_j \lambda_jc_j = \sum_{j \le k}(\lambda_j - \lambda_k)(1 - c_j) + \sum_{j > k}(\lambda_k - \lambda_j)c_j + \lambda_k\Big(\sum_{j \le k}(1 - c_j) - \sum_{j > k}c_j\Big).$$ The last bracket is $k - \sum_j c_j = 0$, and the first two sums have nonnegative terms, so the difference is at least 0. If the columns of $W$ span $\mathbf q_1, \ldots, \mathbf q_k$, then $c_j = 1$ for $j \le k$ and $c_j = 0$ for $j > k$, and the difference is 0. Conversely, if the difference is 0 and $\lambda_k > \lambda_{k+1}$, the second sum forces $c_j = 0$ for every $j > k$, since $\lambda_k - \lambda_j \ge \lambda_k - \lambda_{k+1} > 0$ there. Then $W^{\mathsf T}\mathbf q_j = \mathbf 0$ for $j > k$: every column of $W$ is orthogonal to $\mathbf q_{k+1}, \ldots, \mathbf q_p$, so it lies in the span of $\mathbf q_1, \ldots, \mathbf q_k$, and $k$ orthonormal columns in a $k$-dimensional space span it. $\square$

Without the gap the conclusion fails: if $\lambda_k = \lambda_{k+1}$, then $\mathbf q_1, \ldots, \mathbf q_{k-1}, \mathbf q_{k+1}$ attain the same value.

Example (random planes). For the correlation matrix of the seven measurements, the two leading eigenvectors capture $\lambda_1 + \lambda_2 = 4.1711 + 2.0165 = 6.1876$. Thirty planes drawn at random (orthonormalized Gaussian pairs, seeds 1 to 30) capture a median of 2.15 (interquartile range 1.05 to 2.56), and the best of them 3.70. A random plane drawn this way has a distribution unchanged by every rotation (an orthogonal matrix $Q$ maps a Gaussian pair to a pair with the same distribution, and its plane to $Q$ times the plane), so $E[WW^{\mathsf T}]$ commutes with every orthogonal matrix; commuting with the reflections that change the sign of one coordinate makes it diagonal, and commuting with the permutation matrices makes its diagonal entries equal, so it is a multiple of $I_7$, with trace $\operatorname{tr}E[W^{\mathsf T}W] = 2$; hence $E[WW^{\mathsf T}] = \tfrac27 I_7$ and $E\operatorname{tr}(W^{\mathsf T}RW) = \operatorname{tr}(R\,E[WW^{\mathsf T}]) = \tfrac27\operatorname{tr}R = 2$ for the correlation matrix $R$. The observed median of 2.15 is near that, and the theorem says no plane holds more than 6.1876.

The Frobenius theorem again, with uniqueness

Corollary 1 (best rank-$k$ approximation, unique under a gap). For every $Z$ of rank at most $k$, $\lVert A - Z \rVert_F^2 \ge \sum_{j > k}d_j^2$. If $d_k > d_{k+1}$, the only $Z$ that attains the bound is $A_k$. If $d_k = d_{k+1} > 0$, the bound is attained by more than one $Z$.

Proof. Let $Z$ have rank at most $k$ and let $W$ be a $p \times k$ matrix with orthonormal columns whose span contains every row of $Z$ (pad an orthonormal basis of the row space with further orthonormal vectors if the rank is below $k$). Put $P = WW^{\mathsf T}$, so $ZP = Z$. Each row $\mathbf a_i^{\mathsf T}$ of $A$ and $\mathbf z_i^{\mathsf T}$ of $Z$ satisfies, by Pythagoras, $\lVert \mathbf a_i - \mathbf z_i \rVert^2 = \lVert (I - P)\mathbf a_i \rVert^2 + \lVert P\mathbf a_i - \mathbf z_i \rVert^2$, because $(I - P)\mathbf a_i$ is orthogonal to the column space of $W$, which contains $P\mathbf a_i - \mathbf z_i$. Summing over rows, $$\lVert A - Z \rVert_F^2 = \lVert A - AP \rVert_F^2 + \lVert AP - Z \rVert_F^2 \ge \lVert A - AP \rVert_F^2 = \lVert A \rVert_F^2 - \operatorname{tr}(W^{\mathsf T}A^{\mathsf T}AW).$$ The last step is the Pythagorean split $\lVert A \rVert_F^2 = \lVert A - AP \rVert_F^2 + \lVert AP \rVert_F^2$ with $\lVert AP \rVert_F^2 = \operatorname{tr}(PA^{\mathsf T}AP) = \operatorname{tr}(W^{\mathsf T}A^{\mathsf T}AW)$. Theorem 2, applied to $B = A^{\mathsf T}A = \sum_j d_j^2\mathbf v_j\mathbf v_j^{\mathsf T}$ (Theorem 1), bounds the trace by $d_1^2 + \cdots + d_k^2$, and $\lVert A \rVert_F^2 = \sum_j d_j^2$, which gives the inequality. If equality holds, both steps are equalities: $Z = AP$, and by the equality case of Theorem 2 with $d_k^2 > d_{k+1}^2$, the columns of $W$ span $\mathbf v_1, \ldots, \mathbf v_k$, so $P = \sum_{j \le k}\mathbf v_j\mathbf v_j^{\mathsf T}$ and $Z = AP = \sum_{j \le k}d_j\mathbf u_j\mathbf v_j^{\mathsf T} = A_k$. This proves the first two sentences; the last is proved in the next paragraph.

If $d_k = d_{k+1} > 0$, the minimizer is not unique: $Z' = A_k - d_k\mathbf u_k\mathbf v_k^{\mathsf T} + d_{k+1}\mathbf u_{k+1}\mathbf v_{k+1}^{\mathsf T}$ also has rank $k$ and differs from $A_k$, since $Z' - A_k = d_k(\mathbf u_{k+1}\mathbf v_{k+1}^{\mathsf T} - \mathbf u_k\mathbf v_k^{\mathsf T}) \ne 0$, and $A - Z'$ is the sum of the layers $j \ge k + 2$ and the layer $d_k\mathbf u_k\mathbf v_k^{\mathsf T}$, with squared Frobenius norm $d_k^2 + \sum_{j \ge k+2}d_j^2 = \sum_{j > k}d_j^2$ because $d_k = d_{k+1}$. If $d_k = 0$, the rank of $A$ is below $k$, $A_k = A$, and the only $Z$ with error 0 is $A$ itself, so the minimizer is unique without a gap. $\square$

The proof also says what a rank-$k$ approximation is: a choice of $k$-dimensional subspace for the rows, followed by projecting each row onto it. Eckart and Young's "usually unique" is consistent with this, in our reading: equal positive singular values at the cut are the exception.

How singular values move

The spectral half of the theorem says $d_{k+1}(A) = \min\{\lVert A - Z \rVert_2 : \operatorname{rank}Z \le k\}$, the minimum attained at $A_k$. That characterization makes three inequalities short.

Theorem 3 (perturbation and interlacing). For matrices $B$ and $E$ of the same shape and integers $i, j \ge 1$:

  1. $d_{i+j-1}(B + E) \le d_i(B) + d_j(E)$;
  2. $\lvert d_i(B + E) - d_i(B) \rvert \le \lVert E \rVert_2$ for every $i$;
  3. if $E$ has rank at most 1, then $d_{i+1}(B + E) \le d_i(B)$ and $d_{i+1}(B) \le d_i(B + E)$;
  4. if $P$ is an orthogonal projection (symmetric with $P^2 = P$) of the right size, then $d_i(PB) \le d_i(B)$.

Proof. (1) The matrix $B_{i-1} + E_{j-1}$ (the sums of the $i - 1$ and $j - 1$ largest layers) has rank at most $i + j - 2$. By the characterization and the triangle inequality for the spectral norm, $$d_{i+j-1}(B + E) \le \lVert B + E - B_{i-1} - E_{j-1} \rVert_2 \le \lVert B - B_{i-1} \rVert_2 + \lVert E - E_{j-1} \rVert_2 = d_i(B) + d_j(E).$$ (2) Part 1 with $j = 1$ gives $d_i(B + E) \le d_i(B) + d_1(E)$, and $d_1(E) = \lVert E \rVert_2$. Applied to $B + E$ and $-E$ it gives $d_i(B) \le d_i(B + E) + \lVert E \rVert_2$. (3) A matrix $E$ of rank at most 1 has $d_2(E) = 0$, so part 1 with $j = 2$ gives $d_{i+1}(B + E) \le d_i(B)$; the same with $B + E$ and $-E$ in place of $B$ and $E$ gives the other inequality. (4) $PB_{i-1}$ has rank at most $i - 1$, and $\lVert P\mathbf y \rVert \le \lVert \mathbf y \rVert$ for every $\mathbf y$, so $d_i(PB) \le \lVert PB - PB_{i-1} \rVert_2 \le \lVert B - B_{i-1} \rVert_2 = d_i(B)$. $\square$

Stewart (1993) traces parts 1 and 2 to Weyl (1912), who stated them for symmetric kernels. Part 2 says that singular values are stable: noise of spectral norm $\varepsilon$ moves none of them by more than $\varepsilon$. Singular vectors have no such guarantee. Their stability depends on the gaps between singular values, as the equality case of Theorem 2 already suggests, and the body measurements show it below.

Corollary 2 (centering). Let $\tilde X = X - \mathbf 1\bar{\mathbf x}^{\mathsf T}$ be the centered data. Then for every $i$, $$d_{i+1}(X) \le d_i(\tilde X) \le d_i(X).$$

Proof. $\tilde X = (I - \frac1n\mathbf 1\mathbf 1^{\mathsf T})X$, and $I - \frac1n\mathbf 1\mathbf 1^{\mathsf T}$ is an orthogonal projection (it is symmetric and squares to itself), so the right inequality is part 4. And $X = \tilde X + \mathbf 1\bar{\mathbf x}^{\mathsf T}$ adds a rank-one matrix, so the left inequality is part 3. $\square$

Centering removes at most one dimension's worth of size, and never adds any.

Principal components are the SVD of the centered data

Principal Component Analysis defines the components one at a time: the first is the unit direction of greatest variance, each later one the direction of greatest variance perpendicular to the earlier ones, and it reports from the textbook literature that the first $k$ span the closest $k$-dimensional plane. The next theorem proves the simultaneous version of both statements and identifies them with a truncated SVD.

Here is the idea. For a plane through a point $\mathbf a$, the squared distances of the data from the plane split into a part that depends only on how far $\mathbf a$ is from the mean and a part that depends only on the plane's direction. The first part vanishes at the mean, and the second is the total variance minus the variance the plane captures, which Theorem 2 maximizes.

Theorem 4 (principal components). Let $\tilde X = UDV^{\mathsf T}$ and let $1 \le k < p$. Among all affine $k$-dimensional planes $\{\mathbf a + W\mathbf z : \mathbf z \in \mathbb R^k\}$, with $W$ a $p \times k$ matrix with orthonormal columns:

  1. the sum of squared distances of $\mathbf x_1, \ldots, \mathbf x_n$ from the plane is at least $\sum_{j > k}d_j^2 = (n-1)\sum_{j > k}\lambda_j$, where $\lambda_j = d_j^2/(n-1)$ are the eigenvalues of $S$;
  2. the bound is attained by the plane through $\bar{\mathbf x}$ spanned by $\mathbf v_1, \ldots, \mathbf v_k$, and when $d_k > d_{k+1}$ by no other plane;
  3. among $k$-dimensional subspaces, the sample variance of the projected data, $\operatorname{tr}(W^{\mathsf T}SW)$, is at most $\lambda_1 + \cdots + \lambda_k$, attained at the same $W$; the projected data have total variance plus residual mean square equal to $\operatorname{tr}S$, so maximizing one minimizes the other;
  4. the coordinates of the projected points (the principal component scores) are $\tilde XV_k = U_kD_k$, and the fitted points are the rows of $\mathbf 1\bar{\mathbf x}^{\mathsf T} + \tilde X_k$, where $\tilde X_k = U_kD_kV_k^{\mathsf T}$ is the best rank-$k$ approximation of $\tilde X$.

Proof. Put $P = WW^{\mathsf T}$. The point of the plane nearest $\mathbf x_i$ is $\mathbf a + P(\mathbf x_i - \mathbf a)$, at squared distance $\lVert (I - P)(\mathbf x_i - \mathbf a) \rVert^2$. Write $\mathbf x_i - \mathbf a = (\mathbf x_i - \bar{\mathbf x}) + (\bar{\mathbf x} - \mathbf a)$ and expand: $$\sum_i \lVert (I - P)(\mathbf x_i - \mathbf a) \rVert^2 = \sum_i \lVert (I - P)(\mathbf x_i - \bar{\mathbf x}) \rVert^2 + n\lVert (I - P)(\bar{\mathbf x} - \mathbf a) \rVert^2,$$ because the cross term is $2(\bar{\mathbf x} - \mathbf a)^{\mathsf T}(I - P)\sum_i(\mathbf x_i - \bar{\mathbf x})$ and the deviations from the mean sum to zero. The second term is at least 0 and is 0 when $\mathbf a = \bar{\mathbf x}$. The first is $\lVert \tilde X(I - P) \rVert_F^2 = \lVert \tilde X \rVert_F^2 - \operatorname{tr}(W^{\mathsf T}\tilde X^{\mathsf T}\tilde XW)$, by the Pythagorean split in the proof of Corollary 1. Theorem 2 with $B = \tilde X^{\mathsf T}\tilde X = \sum_j d_j^2\mathbf v_j\mathbf v_j^{\mathsf T}$ bounds the trace by $d_1^2 + \cdots + d_k^2$, with equality for $W$ spanning $\mathbf v_1, \ldots, \mathbf v_k$ and, under the gap, only then; this proves parts 1 and 2 (gap or not, a minimizing plane must also have $(I - P)(\bar{\mathbf x} - \mathbf a) = \mathbf 0$, which says that $\bar{\mathbf x}$ lies on it). Dividing the same identity by $n - 1$ gives part 3: the projected points $P(\mathbf x_i - \bar{\mathbf x})$ have sample covariance $PSP$ with trace $\operatorname{tr}(W^{\mathsf T}SW)$, and $\operatorname{tr}S = \lVert \tilde X \rVert_F^2/(n-1)$. For part 4, with $V_k = (\mathbf v_1, \ldots, \mathbf v_k)$, $\tilde XV_k = \sum_j d_j\mathbf u_j\mathbf v_j^{\mathsf T}V_k = U_kD_k$, and $\tilde XV_kV_k^{\mathsf T} = U_kD_kV_k^{\mathsf T} = \tilde X_k$. $\square$

So the variance view and Pearson's (1901) closest-plane view are one optimization, solved for all $k$ at once by one decomposition. Principal Component Analysis's greedy derivation finds the same directions; Theorem 4 adds that no other $k$-dimensional choice, greedy or not, does better, and that the answer is unique when $\lambda_k > \lambda_{k+1}$.

The body measurements. Standardize the seven measurements and decompose. The eigenvalues of the correlation matrix are

Component 1 2 3 4 5 6 7
Eigenvalue $\lambda_j$ 4.171 2.016 0.321 0.190 0.161 0.112 0.028
Share of variance (%) 59.6 28.8 4.6 2.7 2.3 1.6 0.4

Two components hold 88.4% of the variance. The loadings (entries of $\mathbf v_1$ and $\mathbf v_2$, signs chosen so that height is positive) are

Measurement $\mathbf v_1$ $\mathbf v_2$
height 0.291 0.524
weight 0.475 −0.121
leg length 0.233 0.544
arm length 0.354 0.386
arm circumference 0.428 −0.216
waist 0.417 −0.300
hip 0.392 −0.359

Every measurement loads positively on the first component, so it grows with overall size. The second contrasts the three lengths with the four girths, a direction of build: long and slender at one end, short and broad at the other. The residual sum of squares of the best plane is $d_3^2 + \cdots + d_7^2 = 3{,}990.7$ out of a total of $34{,}384.0$, which the script checks against the entrywise residual of the rank-$k$ approximation for every $k$ from 1 to 6. Sex played no part in the decomposition, yet it shows in both components. The mean scores of men and women are 0.74 and −0.71 on the first component and 0.83 and −0.80 on the second, and the sign of the second score alone matches sex for 76.0% of the adults. That is an observation about these data: as Principal Component Analysis stresses, components are chosen for variance, and the direction that separates two groups best is the subject of Linear Discriminant Analysis.

Example (centering matters). On the raw measurements (centimeters and kilograms, not standardized) compare the best $k$-dimensional subspace through the origin, which is the truncated SVD of $X$ itself, with the best affine $k$-plane, the truncated SVD of $\tilde X$. Their residual sums of squares are $\sum_{j > k}d_j(X)^2$ and $\sum_{j > k}d_j(\tilde X)^2$:

$k$ Subspace through the origin Affine plane (principal components) Subspace of dimension $k + 1$
1 2,782,929 930,414 593,673
2 593,673 285,558 221,433

By Corollary 2 the affine plane never does worse than the subspace of the same dimension and never beats the subspace with one more dimension, and the table shows both, here with strict inequalities. The reason is visible in the first right singular vector of $X$: its cosine with the mean vector $\bar{\mathbf x}$ is 0.99997. Without centering, the first layer spends itself describing where the data are, not how they vary.

Example (which components are stable). Resample the 4,913 adults with replacement (seeds 1 to 30), standardize, decompose, and measure the angle between each resampled direction and the full-data one. The median angle is 0.44 degrees for the first component (interquartile range 0.26 to 0.57), 0.66 degrees for the second (0.41 to 0.82) and 2.37 degrees for the third (1.63 to 3.13). The eigenvalue gaps are $\lambda_1 - \lambda_2 = 2.155$, $\lambda_2 - \lambda_3 = 1.696$ and $\lambda_3 - \lambda_4 = 0.131$. In this experiment the direction bordered by the smallest gap moved most. Theorem 2's equality case is the reason a gap matters at all: with no gap the direction is not determined, and a small gap leaves it nearly undetermined.

Latent semantic indexing is the SVD of the uncentered term–document matrix

Latent Semantic Indexing decomposes the term–document matrix $C$ and keeps $k$ layers, $C_k = U_kD_kV_k^{\mathsf T}$, and compares queries and documents in the $k$-dimensional coordinates; its Cranfield experiment and its fold-in of queries are not repeated here. In the terms of this article, LSI is a truncated SVD of a matrix whose rows are terms and whose columns are documents, with no centering. Theorem 4 and Corollary 2 say what that choice gives up and what it keeps.

The rank-$k$ error, asserted. For the Cranfield matrix, $\lVert C \rVert_F^2 = 1{,}398$ (1,398 nonzero unit columns), and the largest singular values are $d_1 = 8.138$ and $d_2 = 3.809$. The script forms $C - C_k$ entry by entry and asserts that its squared Frobenius norm equals $\sum_{j > k}d_j^2$ to a relative $10^{-10}$, and that its spectral norm equals $d_{k+1}$ to $10^{-9}$:

$k$ $\lVert C - C_k \rVert_F^2$ Share of $\lVert C \rVert_F^2$ kept (%) $\lVert C - C_k \rVert_2 = d_{k+1}$
10 1,253.2 10.4 2.337
50 1,099.7 21.3 1.738
100 967.6 30.8 1.531
200 766.4 45.2 1.317
300 611.5 56.3 1.174
500 385.1 72.5 0.960

The shares agree with those Latent Semantic Indexing reports: at the hundred dimensions where it found its best retrieval, the approximation keeps less than a third of the matrix. That is not a failure of the theorem. Text matrices have slowly falling singular values, so no low rank is close in either norm; LSI's argument is that the discarded part is mostly noise in word choice, which the theorem neither supports nor refutes. At every $k$ in the table $d_k > d_{k+1}$, so by Corollary 1 each $C_k$ is the unique best approximation.

The first layer is the mean. Latent Semantic Indexing observes that Cranfield's first dimension mostly records the average document, because every column has unit length and positive entries. Corollary 2 and two numbers make this precise. The mean document $\bar{\mathbf c}$ (the mean of the $N = 1{,}400$ columns) accounts for 4.4% of $\lVert C \rVert_F^2$ (that share is $N\lVert \bar{\mathbf c} \rVert^2/\lVert C \rVert_F^2$), the first layer carries 4.7% ($d_1^2/\lVert C \rVert_F^2$), and the cosine between $\mathbf u_1$ and $\bar{\mathbf c}$ is 0.9976: the first LSI dimension is, almost exactly, the collection's average term profile. Centering the documents and decomposing again (principal components of the documents) gives leading singular values 3.878 and 3.653, which interlace with the uncentered ones as Corollary 2, applied to $C^{\mathsf T}$ (whose rows are the documents), requires ($d_2(C) = 3.809 \le 3.878 \le 8.138$, and so on; the script asserts the interlacing for the first 200). Whether centering would help or hurt retrieval was not tested here.

Example (noise moves singular values by less than its norm). Add to $C$ a matrix $E$ of independent normal entries with standard deviation 0.001 (seeds 1 to 30). The spectral norm of $E$ has median 0.107. The largest change in any of the 1,400 singular values, divided by $\lVert E \rVert_2$, has median 0.553 (interquartile range 0.550 to 0.555), inside the bound of 1 that Theorem 3 part 2 guarantees.

Example (randomized decomposition). A full SVD of a large matrix is expensive, and the rank-$k$ layers are often all that is wanted. Halko, Martinsson and Tropp (2011, Algorithms 4.1 and 5.1) find them from a random sketch: multiply $C$ by a Gaussian $1{,}400 \times (k + \ell)$ matrix $\Omega$, where $\ell$ is the oversampling (Halko and colleagues call it $p$, which here counts variables), take an orthonormal basis $Q$ of the columns of $C\Omega$, and decompose the small matrix $Q^{\mathsf T}C$. They recommend an oversampling of 5 or 10 (§4.2), and a power iteration, sketching $(CC^{\mathsf T})^qC$ instead, when the singular values fall slowly (their Algorithm 4.3, which they note is vulnerable to round-off errors and for which they recommend the implementation of their Algorithm 4.4). For $k = 100$ and $\ell = 10$ on Cranfield (seeds 1 to 30), the Frobenius error of the rank-100 truncation of $QQ^{\mathsf T}C$, divided by the Eckart–Young minimum of 31.11, has median 1.0900 (interquartile range 1.0897 to 1.0904) without a power iteration and 1.0297 (1.0295 to 1.0298) with $q = 1$. The ratio can never fall below 1, by the theorem, and the script asserts that it does not. Slowly falling singular values are exactly the case in which the authors advise the power iteration, and here it cut the excess error by about two thirds.

Least squares, the pseudo-inverse and ridge regression

Least squares, its minimum-length solution and ridge regression are three ways of inverting $X$ on the layers of its SVD. The Geometry of Least Squares proves the projection theorem and obtains the minimum-length solution from it; Ridge and Lasso Regression proves the shrinkage of each principal direction (its Theorem 2). Here the three are written side by side in the coordinates of the SVD, which is where their differences are plainest.

Theorem 5 (the shortest least-squares solution). Let $X$ be $n \times p$ of rank $r$ with $X = UDV^{\mathsf T}$, and complete $\mathbf v_1, \ldots, \mathbf v_r$ by $\mathbf v_{r+1}, \ldots, \mathbf v_p$ to an orthonormal basis of $\mathbb R^p$. Define the pseudo-inverse $X^{+} = VD^{-1}U^{\mathsf T} = \sum_{j \le r}d_j^{-1}\mathbf v_j\mathbf u_j^{\mathsf T}$. Then:

  1. $\boldsymbol\beta$ minimizes $\lVert \mathbf y - X\boldsymbol\beta \rVert^2$ exactly when $\mathbf v_j^{\mathsf T}\boldsymbol\beta = \mathbf u_j^{\mathsf T}\mathbf y/d_j$ for $j \le r$, with $\mathbf v_j^{\mathsf T}\boldsymbol\beta$ arbitrary for $j > r$;
  2. the shortest minimizer is $\boldsymbol\beta^{+} = X^{+}\mathbf y$;
  3. $X^{+}$ satisfies the four equations $XX^{+}X = X$, $X^{+}XX^{+} = X^{+}$, $(XX^{+})^{\mathsf T} = XX^{+}$ and $(X^{+}X)^{\mathsf T} = X^{+}X$, and it is the only matrix that does.

Proof. Write $\mathbf y = \sum_{j \le r}(\mathbf u_j^{\mathsf T}\mathbf y)\mathbf u_j + \mathbf y_\perp$ with $\mathbf y_\perp$ orthogonal to $\mathbf u_1, \ldots, \mathbf u_r$, and $\boldsymbol\beta = \sum_{j \le p}b_j\mathbf v_j$ with $b_j = \mathbf v_j^{\mathsf T}\boldsymbol\beta$. Then $X\boldsymbol\beta = \sum_{j \le r}d_jb_j\mathbf u_j$, and by Pythagoras $$\lVert \mathbf y - X\boldsymbol\beta \rVert^2 = \sum_{j \le r}(\mathbf u_j^{\mathsf T}\mathbf y - d_jb_j)^2 + \lVert \mathbf y_\perp \rVert^2,$$ which is smallest exactly when each bracket is zero, whatever $b_{r+1}, \ldots, b_p$ are; that is part 1. The length is $\lVert \boldsymbol\beta \rVert^2 = \sum_j b_j^2$, smallest with $b_j = 0$ for $j > r$, which is $\sum_{j \le r}(\mathbf u_j^{\mathsf T}\mathbf y/d_j)\mathbf v_j = X^{+}\mathbf y$. For part 3, $XX^{+} = \sum_{j \le r}\mathbf u_j\mathbf u_j^{\mathsf T}$ and $X^{+}X = \sum_{j \le r}\mathbf v_j\mathbf v_j^{\mathsf T}$ are symmetric, and $XX^{+}X = \sum_j\mathbf u_j\mathbf u_j^{\mathsf T}\sum_i d_i\mathbf u_i\mathbf v_i^{\mathsf T} = X$, and $X^{+}XX^{+} = \big(\sum_{j \le r}\mathbf v_j\mathbf v_j^{\mathsf T}\big)\sum_{i \le r}d_i^{-1}\mathbf v_i\mathbf u_i^{\mathsf T} = \sum_{i \le r}d_i^{-1}\mathbf v_i\mathbf u_i^{\mathsf T} = X^{+}$. Finally, at most one matrix satisfies the four equations. If $G$ and $H$ both do, then using each equation in turn, $$G = GXG = G(XG)^{\mathsf T} = GG^{\mathsf T}X^{\mathsf T} = GG^{\mathsf T}(XHX)^{\mathsf T} = G(XG)^{\mathsf T}(XH)^{\mathsf T} = GXGXH = GXH,$$ $$H = HXH = (HX)^{\mathsf T}H = X^{\mathsf T}H^{\mathsf T}H = (XGX)^{\mathsf T}H^{\mathsf T}H = (GX)^{\mathsf T}(HX)^{\mathsf T}H = GXHXH = GXH,$$ so $G = H$. $\square$

Penrose (1955) defined a generalized inverse as "the unique solution of a certain set of equations" (his abstract), and $X^{+}$ is the unique solution of the four above; the result agrees with the minimum-length solution that The Geometry of Least Squares obtains by projection. The SVD form adds one thing that the projection form hides: the coefficient along $\mathbf v_j$ is the data's coordinate $\mathbf u_j^{\mathsf T}\mathbf y$ divided by $d_j$. A small singular value multiplies whatever noise lies along $\mathbf u_j$ by $1/d_j$. The ratio $d_1/d_r$, the condition number, measures how unevenly the directions are determined.

Theorem 6 (ridge as a filter, and its limit). For $\lambda > 0$ the ridge estimate $\hat{\boldsymbol\beta}_\lambda = (X^{\mathsf T}X + \lambda I)^{-1}X^{\mathsf T}\mathbf y$ is $$\hat{\boldsymbol\beta}_\lambda = \sum_{j \le r}\frac{d_j}{d_j^2 + \lambda}(\mathbf u_j^{\mathsf T}\mathbf y)\,\mathbf v_j,$$ it has no component along $\mathbf v_{r+1}, \ldots, \mathbf v_p$, and $$\lVert \hat{\boldsymbol\beta}_\lambda - \boldsymbol\beta^{+} \rVert \le \frac{\lambda\,\lVert \mathbf y \rVert}{d_r^3},$$ so $\hat{\boldsymbol\beta}_\lambda \to X^{+}\mathbf y$ as $\lambda \to 0$, even when $X$ has rank below $p$.

Proof. With the completed basis, $X^{\mathsf T}X + \lambda I = \sum_{j \le p}(d_j^2 + \lambda)\mathbf v_j\mathbf v_j^{\mathsf T}$ with $d_j = 0$ for $j > r$, which is invertible with inverse $\sum_j(d_j^2 + \lambda)^{-1}\mathbf v_j\mathbf v_j^{\mathsf T}$ because every $d_j^2 + \lambda > 0$. Since $X^{\mathsf T}\mathbf y = \sum_{j \le r}d_j(\mathbf u_j^{\mathsf T}\mathbf y)\mathbf v_j$, the formula follows, and the directions $j > r$ receive nothing. The difference from $\boldsymbol\beta^{+}$ has coordinates $\big(\frac{d_j}{d_j^2 + \lambda} - \frac{1}{d_j}\big)\mathbf u_j^{\mathsf T}\mathbf y = -\frac{\lambda}{d_j(d_j^2 + \lambda)}\mathbf u_j^{\mathsf T}\mathbf y$, each at most $\frac{\lambda}{d_r^3}\lvert \mathbf u_j^{\mathsf T}\mathbf y \rvert$ in size, and $\sum_{j \le r}(\mathbf u_j^{\mathsf T}\mathbf y)^2 \le \lVert \mathbf y \rVert^2$. $\square$

The three estimators differ only in the factor applied to $\mathbf u_j^{\mathsf T}\mathbf y/d_j$: least squares (shortest) applies 1 to every direction with $d_j > 0$; truncated SVD, which is principal components regression, applies 1 to the $k$ largest and 0 to the rest; ridge applies $d_j^2/(d_j^2 + \lambda)$, which falls smoothly from near 1 to near 0 as $d_j$ falls. Summed over the directions, ridge's factors are the trace of its smoother matrix, its effective degrees of freedom, which Optimism and Effective Degrees of Freedom proves measure how strongly the fit follows its own responses (its Theorem 2). Ridge and Lasso Regression proves that a small enough penalty always beats least squares in mean squared error (the theorem of Hoerl and Kennard, 1970).

Example (a design with an exactly dependent column). Regress weight on the six other measurements and an intercept, and add height in inches as an eighth column, $\text{height}/2.54$. The design $A$ (playing the role of $X$ in Theorems 5 and 6) is $4{,}913 \times 8$ of rank 7: its smallest singular value is zero to rounding ($1.4 \times 10^{-12}$ against a largest of 16,838). The null direction pairs the two height columns. The shortest solution splits the height effect between them, 0.5494 kg per centimeter and 0.2163 kg per inch, which together are $0.5494 + 0.2163/2.54 = 0.6345$ kg per centimeter, exactly the height coefficient of the full-rank fit without the inch column (asserted to $10^{-6}$). Neither split coefficient means anything alone; their combination is estimable in the sense of The Geometry of Least Squares (its Theorem 6). The script checks the four Penrose equations and agrees with NumPy's least-squares solver. The fit has $R^2 = 0.961$. Ridge solutions, with the intercept penalized too as in Theorem 6 (unlike Ridge and Lasso Regression, which leaves it unpenalized), approach $\boldsymbol\beta^{+}$ at the rate of Theorem 6: the distance is about $1.2 \times 10^{-1}$ at $\lambda = 10^{-2}$, $1.2 \times 10^{-3}$ at $\lambda = 10^{-4}$ and $1.2 \times 10^{-5}$ at $\lambda = 10^{-6}$, falling in proportion to $\lambda$, and their component along the null direction is zero to rounding at every $\lambda$.

Example (conditioning is mostly units). Without the inch column the design has condition number 4,533. Center and standardize the six measurements (keeping the intercept) and it falls to 5.4: the fitted values are unchanged, because the columns span the same space, so in this design nearly all of the ill-conditioning came from the scales and the centers of the columns, not from the measurements' dependence on one another. The centers matter for the reason the first uncentered layer above is the mean: the column of ones and the uncentered measurements point in nearly the same direction.

What is proved, what is cited, what the experiment shows

Proved on this page: the existence of the SVD by maximizing a stretch, with the characterization of each singular value as a constrained maximum (Lemma 1, Theorem 1), and the eigendecomposition of $A^{\mathsf T}A$ as a consequence; the trace maximum principle with its equality case (Theorem 2); the Frobenius best-approximation theorem by a second route, with uniqueness under the gap $d_k > d_{k+1}$ and non-uniqueness without it when $d_{k+1} > 0$ (Corollary 1); the inequalities $d_{i+j-1}(B + E) \le d_i(B) + d_j(E)$, the perturbation bound, rank-one interlacing and the projection bound (Theorem 3), and the interlacing of centered and uncentered singular values (Corollary 2); principal components as the closest affine plane, the plane of greatest projected variance and the truncated SVD of the centered data, with uniqueness under a gap (Theorem 4); the minimum-length least-squares solution and the four Penrose equations and the uniqueness of their solution (Theorem 5); ridge regression as a filter with an explicit bound on its distance from the pseudo-inverse (Theorem 6).

Used from other pages: the Eckart–Young theorem in the spectral and Frobenius norms and $\lVert A \rVert_F^2 = \sum_j d_j^2$ (Latent Semantic Indexing); the projection theorem and estimable functions (The Geometry of Least Squares); the shrinkage of each principal direction and the theorem of Hoerl and Kennard (Ridge and Lasso Regression); the greedy derivation of principal components (Principal Component Analysis).

Cited: Eckart and Young (1936) for the problem for matrices and its solution, with Schmidt's earlier proof and Weyl's inequalities as Stewart (1993) reports them; Pearson (1901) for the closest-plane view; Hoerl and Kennard (1970), through Ridge and Lasso Regression, for the theorem that some ridge penalty beats least squares; Cleverdon (1967) for the Cranfield collection; Penrose (1955) for the generalized inverse as "the unique solution of a certain set of equations" (from his abstract); Stewart (1993) for the history; Halko, Martinsson and Tropp (2011) for the randomized range finder, the power iteration and their recommended oversampling.

Observed in the experiments: on the body measurements, the two-component share of 88.4%, the separation of the sexes on both components, the advantage of centering, and the bootstrap angles, which were largest for the component with the smallest gap; on Cranfield, the share of the matrix kept at each rank, the near-identity of the first layer and the mean document, the singular values' movement under noise (well inside the bound), and the error ratios of the randomized method. Every number on this page is computed by tools/experiments/statistics/svd-in-statistics.py, with the Cranfield numbers produced by svd_cranfield.py in the same folder.

Worked problems

These problems are posed for this article on small exact cases; the unit has no course assignments. The script recomputes every number.

Problem 1 (a decomposition by hand). Find the SVD of $A = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix}$, its best rank-one approximation, and both errors.

Solution. $A^{\mathsf T}A = \begin{pmatrix} 25 & 20 \\ 20 & 25 \end{pmatrix}$, with eigenvalues $45$ and $5$ (eigenvectors $(1, 1)/\sqrt2$ and $(1, -1)/\sqrt2$), so $d_1 = \sqrt{45} = 3\sqrt5$ and $d_2 = \sqrt5$, and $\mathbf v_1 = (1, 1)^{\mathsf T}/\sqrt2$, $\mathbf v_2 = (1, -1)^{\mathsf T}/\sqrt2$. Then $\mathbf u_1 = A\mathbf v_1/d_1 = (3, 9)^{\mathsf T}/(\sqrt2 \cdot 3\sqrt5) = (1, 3)^{\mathsf T}/\sqrt{10}$ and $\mathbf u_2 = A\mathbf v_2/d_2 = (3, -1)^{\mathsf T}/(\sqrt2\sqrt5) = (3, -1)^{\mathsf T}/\sqrt{10}$, which are orthonormal, as Theorem 1 promises. The largest stretch is $d_1 = \lVert A \rVert_2 = 3\sqrt5 = 6.708$, at $\mathbf v_1$. The best rank-one approximation is $$A_1 = d_1\mathbf u_1\mathbf v_1^{\mathsf T} = \frac{3\sqrt5}{\sqrt{20}}\begin{pmatrix} 1 & 1 \\ 3 & 3 \end{pmatrix} = \begin{pmatrix} 3/2 & 3/2 \\ 9/2 & 9/2 \end{pmatrix}, \qquad A - A_1 = \begin{pmatrix} 3/2 & -3/2 \\ -1/2 & 1/2 \end{pmatrix}.$$ The squared Frobenius error is $\frac94 + \frac94 + \frac14 + \frac14 = 5 = d_2^2$, and $A - A_1 = d_2\mathbf u_2\mathbf v_2^{\mathsf T}$ has spectral norm $d_2 = \sqrt5 = 2.236$. Because $d_1 > d_2$, Corollary 1 says $A_1$ is the only rank-one matrix with squared Frobenius error 5. Note that $A_1$ does not keep the zero in the corner: the best approximation of a matrix need not respect its pattern of zeros.

Problem 2 (a pseudo-inverse and its ridge path). Let $X = \begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$ and $\mathbf y = (1, 1)^{\mathsf T}$. Find all least-squares solutions, the shortest, $X^{+}$, and the ridge estimate for every $\lambda > 0$.

Solution. $X = \mathbf a\mathbf a^{\mathsf T}$ with $\mathbf a = (1, 2)^{\mathsf T}$ has rank 1, with $d_1 = \lVert \mathbf a \rVert^2 = 5$ and $\mathbf u_1 = \mathbf v_1 = (1, 2)^{\mathsf T}/\sqrt5$. So $X^{+} = d_1^{-1}\mathbf v_1\mathbf u_1^{\mathsf T} = \frac{1}{25}\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$, and $\boldsymbol\beta^{+} = X^{+}\mathbf y = (3/25, 6/25)^{\mathsf T}$. By Theorem 5 part 1 the minimizers are the $\boldsymbol\beta$ with $\mathbf v_1^{\mathsf T}\boldsymbol\beta = \mathbf u_1^{\mathsf T}\mathbf y/d_1 = (3/\sqrt5)/5$, that is $\beta_1 + 2\beta_2 = 3/5$: a line of solutions, all with fitted values $\frac35(1, 2)^{\mathsf T}$ and residual sum of squares $(1 - \frac35)^2 + (1 - \frac65)^2 = \frac15$. The shortest point of the line $\beta_1 + 2\beta_2 = 3/5$ is its foot from the origin, $\frac{3}{5}\cdot\frac{(1, 2)}{5} = (3/25, 6/25)$, the same answer. The four Penrose equations hold: $XX^{+} = X^{+}X = \frac15\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$ is symmetric, and $XX^{+}X = X$ because $\frac15\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$ fixes the columns of $X$, which are multiples of $(1, 2)^{\mathsf T}$. By Theorem 6, $\hat{\boldsymbol\beta}_\lambda = \frac{5}{25 + \lambda}\cdot\frac{3}{\sqrt5}\cdot\frac{(1, 2)}{\sqrt5} = \frac{3}{25 + \lambda}(1, 2)^{\mathsf T}$, which tends to $(3/25, 6/25)$ as $\lambda \to 0$, with $\lVert \hat{\boldsymbol\beta}_\lambda - \boldsymbol\beta^{+} \rVert = 3\sqrt5\big(\frac{1}{25} - \frac{1}{25 + \lambda}\big) = \frac{3\sqrt5\,\lambda}{25(25 + \lambda)}$, below the bound $\lambda\lVert \mathbf y \rVert/d_1^3 = \sqrt2\lambda/125$ of the theorem, since $3\sqrt5/(25 \cdot 25) = 0.0107 < \sqrt2/125 = 0.0113$.

Problem 3 (centering three points). For the points $(1, 2)$, $(2, 1)$ and $(3, 3)$, find the best line through the origin and the best line through any point, with their residual sums of squares, and check Corollary 2.

Solution. Uncentered: $X^{\mathsf T}X = \begin{pmatrix} 14 & 13 \\ 13 & 14 \end{pmatrix}$, with eigenvalues 27 and 1 and eigenvectors $(1, 1)/\sqrt2$ and $(1, -1)/\sqrt2$. The best line through the origin is the diagonal, with residual sum of squares $d_2(X)^2 = 1$: the squared distances of the three points from the diagonal are $\frac12, \frac12, 0$. Centered: the mean is $(2, 2)$, the deviations are $(-1, 0)$, $(0, -1)$ and $(1, 1)$, and $\tilde X^{\mathsf T}\tilde X = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$, with eigenvalues 3 and 1 and the same eigenvectors. The best line is again the diagonal, now through $(2, 2)$, which is the same line, with residual sum of squares $d_2(\tilde X)^2 = 1$. Corollary 2 reads $d_2(X)^2 = 1 \le d_1(\tilde X)^2 = 3 \le d_1(X)^2 = 27$ and $d_2(\tilde X)^2 = 1 \le d_2(X)^2 = 1$, with equality in the last. Centering costs nothing here because the mean $(2, 2)$ already lies on the best line through the origin; when it lies off that line, the affine fit is strictly better, because the proof of Theorem 4 shows that every best affine plane contains $\bar{\mathbf x}$ (the location term vanishes only there), so a line through the origin that misses $\bar{\mathbf x}$ is not a best affine line. That is the case of the body measurements.

Summary

  • Every real matrix is a sum $\sum_j d_j\mathbf u_j\mathbf v_j^{\mathsf T}$ of orthogonal rank-one layers with $d_1 \ge \cdots \ge d_r > 0$; each $d_j$ is the largest stretch perpendicular to the earlier directions (Theorem 1).
  • A $k$-dimensional subspace captures at most the $k$ largest eigenvalues of a symmetric matrix, uniquely when $\lambda_k > \lambda_{k+1}$ (Theorem 2). Hence $A_k$ is the best rank-$k$ approximation in the Frobenius norm, uniquely under $d_k > d_{k+1}$ (Corollary 1); the spectral statement is proved in Latent Semantic Indexing.
  • Singular values move by at most the spectral norm of a perturbation, interlace under a rank-one change, and do not grow under a projection (Theorem 3); centered and uncentered values interlace (Corollary 2).
  • Principal components are the truncated SVD of the centered data: the closest affine plane and the plane of greatest variance (Theorem 4). For the seven body measurements two components hold 88.4% of the variance, size and build.
  • Latent semantic indexing is the truncated SVD of the uncentered term–document matrix; on Cranfield the rank-$k$ error equals the discarded squared singular values (asserted), and the first layer is almost exactly the mean document.
  • Least squares, truncated SVD and ridge regression apply the factors 1, 0 or 1, and $d_j^2/(d_j^2 + \lambda)$ to the coordinates $\mathbf u_j^{\mathsf T}\mathbf y/d_j$; the pseudo-inverse gives the shortest least-squares solution (Theorem 5), and ridge tends to it (Theorem 6).

What we have learned

The singular value decomposition is the one fact beneath four methods that are usually taught apart. It exists for every matrix, it orders a matrix's content into layers, and keeping the largest layers is the best that any approximation of the same rank can do. Principal components keep the largest layers of the centered data, and centering matters: without it the first layer describes where the data are. Latent semantic indexing keeps the largest layers of an uncentered count matrix and accepts that cost. Least squares and ridge regression divide by the layers' sizes, and the small ones are where noise is amplified and where a penalty does its work. What the decomposition does not supply is stability for directions whose singular values are close, which the resampled body measurements showed directly.

This article closes the Multivariate Statistics unit. The covariance matrices it decomposed are the subject of Covariance Matrices and Quadratic Forms, and Gaussian Mixture Models fits a covariance matrix to each of several groups that are not labeled.

References