Skip to main content

The best rank-k approximation

Cut the singular value decomposition after k layers and you have the closest matrix of rank k. Derive the error, in the Frobenius and the spectral norm, from the singular values you dropped, and test the Eckart-Young theorem against random rivals.
M03.6.1L2 Intermediate25 min
In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: M03.5 Singular value decomposition

What you will be able to do
  • Form the truncation A_k of a matrix from the first k layers of its singular value decomposition.
  • Derive that the squared Frobenius error of A_k is the sum of the squared singular values that were dropped, and that its spectral error is the first dropped singular value.
  • State the Eckart-Young theorem and explain why zeroing small entries or truncating an eigendecomposition does worse.
  • Build A_k in NumPy and check that random matrices of the same rank are never closer.

The question

A matrix with a million entries costs a million numbers to store. Recommender systems, compressed neural networks and the fine-tuning method LoRA all replace such a matrix by one of low rank, which costs far fewer. Of all the matrices of rank \(k\), which one is closest to the original, and how close can it possibly get?

Intuition

The last module wrote every matrix as a stack of rank-one layers, one per singular value (M03.5.4):

\[ \begin{aligned} \mat{A} &= \cparam{\sigma_1}\,\vect{u}_1\vect{v}_1\T + \cparam{\sigma_2}\,\vect{u}_2\vect{v}_2\T \\ &\quad + \cdots + \cparam{\sigma_r}\,\vect{u}_r\vect{v}_r\T . \end{aligned} \]

The layers come in order of size, \(\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0\). The obvious way to save space is to keep the big layers and throw away the small ones. The truncation \(\cmodel{\mat{A}_k}\) is the sum of the first \(k\) layers. Each layer is a column times a row, so it has rank one, and \(\mat{A}_k\) has rank \(k\).

Picture what that does for the running SVD matrix \(\mat{A} = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}\). It turns the unit circle into an ellipse with semi-axes \(\sigma_1 = 3\sqrt5\) and \(\sigma_2 = \sqrt5\). Keeping one layer squashes the ellipse flat onto its long axis.

Two tall panels. Left, titled The matrix A: a small blue unit circle at the origin and around it a long vermillion ellipse tilted up to the right. Two orange arrows from the origin mark its semi-axes: a long one labelled sigma 1 u 1, with sigma 1 equal to 3 root 5, about 6.71, and a short one pointing up to the left labelled sigma 2 u 2, root 5, about 2.24. Right, titled Its best rank-one copy A 1: the same ellipse dashed in grey, a thick vermillion segment along its long axis labelled A 1 keeps sigma 1 u 1, and two purple arrows along the short axis labelled dropped: sigma 2 equals root 5. A sentence underneath reads: the error A minus A 1 is the dropped axis: no rank-one matrix comes closer.
M03.6.1-F1

Keeping one layer of \(\mat{A}\) keeps the long axis of its ellipse and squashes the short one to nothing. What is lost is exactly the short axis, of length \(\sigma_2\).

Two claims hide in this picture. The size of the error is set by the dropped singular value alone. And nothing of rank one does better. This lesson proves the first and states the second, the Eckart-Young theorem, with its proof in a collapsed block.

Build it up

Step 1. Two ways to measure an error. To say how close \(\mat{A}_k\) is, we need the size of the error matrix \(\mat{A} - \mat{A}_k\). Two sizes are in common use, and M03.5.4 met both.

  • The Frobenius norm treats a matrix as a long list of entries: \(\norm{\mat{M}}_F\) is the square root of the sum of the squares of all the entries.
  • The spectral norm \(\norm{\mat{M}}_2\) is the largest stretch, the biggest value of \(\norm{\mat{M}\vect{x}}\) over unit vectors \(\vect{x}\).

M03.8.1 studies norms of matrices in full. Here we need only these two.

Step 2. Layer by layer. Adding layers one at a time rebuilds the matrix in order of importance. The figure shows it on a \(48 \times 48\) greyscale picture, a matrix of brightness values that the next lesson compresses.

Six square greyscale pictures in two rows. Top row: layer 1, with sigma 1 equal to 32.55, a pattern of soft horizontal and vertical stripes; plus layer 2, sigma 2 equal to 5.16, and plus layer 3, sigma 3 equal to 3.51, both stripy patterns on a mid-grey background with dark and light blocks where a house will be. Bottom row: equals A 1, equals A 2, equals A 3, the running sums, in which a blurred house with a dark roof and a door gradually appears. A note reads: in a layer every row is a multiple of one row; mid-grey is zero.
M03.6.1-F2

Layers of a picture and their running sums. Each layer is a plaid of stripes, because every row of a rank-one matrix is a multiple of one row. Their sums \(\mat{A}_1, \mat{A}_2, \mat{A}_3\) sharpen step by step.

Step 3. The error is the layers you left out. Subtract the truncation from the full sum and what remains is the tail:

\[ \begin{aligned} \closs{\mat{A} - \mat{A}_k} &= \sigma_{k+1}\,\vect{u}_{k+1}\vect{v}_{k+1}\T \\ &\quad + \cdots + \sigma_r\,\vect{u}_r\vect{v}_r\T . \end{aligned} \]

The next section measures this tail in both norms.

The formal statement

Result 1: the layers are perpendicular. Treat matrices of one shape as long vectors and define their dot product entry by entry, \(\langle \mat{X}, \mat{Y} \rangle = \sum_{a,b} x_{ab}\,y_{ab}\), so that \(\norm{\mat{X}}_F^2 = \langle \mat{X}, \mat{X} \rangle\). Entry \((a, b)\) of the layer \(\vect{u}_i\vect{v}_i\T\) is \((u_i)_a\,(v_i)_b\). So

\[ \begin{aligned} &\langle \vect{u}_i\vect{v}_i\T, \vect{u}_j\vect{v}_j\T \rangle \\ &\quad= \sum_a \sum_b (u_i)_a (v_i)_b\,(u_j)_a (v_j)_b \\ &\quad= \Big(\sum_a (u_i)_a (u_j)_a\Big) \\ &\qquad \times \Big(\sum_b (v_i)_b (v_j)_b\Big) \\ &\quad= (\vect{u}_i \cdot \vect{u}_j)\,(\vect{v}_i \cdot \vect{v}_j) . \end{aligned} \]

The \(\vect{u}\)’s are orthonormal and so are the \(\vect{v}\)’s. The product is 1 when \(i = j\) and 0 otherwise: the layers are orthonormal, like the axes of a coordinate system.

Result 2: the Frobenius error. Expand the squared norm of the tail as a double sum of dot products. By Result 1 only the terms with \(i = j\) survive:

\[ \begin{aligned} &\norm{\mat{A} - \mat{A}_k}_F^2 \\ &\quad= \sum_{i > k} \sum_{j > k} \sigma_i \sigma_j \langle \vect{u}_i\vect{v}_i\T, \vect{u}_j\vect{v}_j\T \rangle \\ &\quad= \closs{\sigma_{k+1}^2 + \cdots + \sigma_r^2} . \end{aligned} \]

With \(k = 0\) the same line gives \(\norm{\mat{A}}_F^2 = {\sigma_1^2 + \cdots + \sigma_r^2}\): the sum of the squares of the entries equals the sum of the squared singular values. We call that sum the energy of the matrix. The share of the energy that \(\mat{A}_k\) keeps is \({\sigma_1^2 + \cdots + \sigma_k^2}\) divided by the whole sum.

Result 3: the spectral error. Take a unit vector \(\vect{x}\). Each layer acts by \({(\vect{u}_i\vect{v}_i\T)\,\vect{x}} = {(\vect{v}_i \cdot \vect{x})\,\vect{u}_i}\), so

\[ (\mat{A} - \mat{A}_k)\,\vect{x} = \sum_{i > k} \sigma_i\,(\vect{v}_i \cdot \vect{x})\,\vect{u}_i . \]

The \(\vect{u}_i\) are orthonormal, so the squared length is the sum of the squared coefficients. Every \(\sigma_i\) in the tail is at most \(\sigma_{k+1}\), and the squared coordinates of \(\vect{x}\) along orthonormal directions add up to at most \(\norm{\vect{x}}^2 = 1\):

\[ \begin{aligned} \norm{(\mat{A} - \mat{A}_k)\,\vect{x}}^2 &= \sum_{i > k} \sigma_i^2\,(\vect{v}_i \cdot \vect{x})^2 \\ &\le \sigma_{k+1}^2 \sum_{i > k} (\vect{v}_i \cdot \vect{x})^2 \\ &\le \sigma_{k+1}^2 . \end{aligned} \]

For \(\vect{x} = \vect{v}_{k+1}\) both inequalities are equalities. So \(\norm{\mat{A} - \mat{A}_k}_2 = \closs{\sigma_{k+1}}\), the largest singular value left out. (When \(k = r\) nothing is left out and the error is zero.)

A bar chart of five squared singular values, 25, 16, 9, 4 and 1. The first two bars are orange and labelled kept: A 2. The last three are purple and labelled dropped. A pointer to the bar 9 reads: the squared spectral norm of A minus A 2 equals sigma 3 squared. An arrow leads to a single stacked purple bar of height 14 made of the three dropped bars, labelled: the squared Frobenius norm of A minus A 2 equals 9 plus 4 plus 1.
M03.6.1-F3

A matrix with singular values 5, 4, 3, 2, 1, cut after two layers. The squared spectral error is the tallest dropped bar, \(\sigma_3^2 = 9\). The squared Frobenius error is all the dropped bars stacked, \(9 + 4 + 1 = 14\).

NoteThe Eckart-Young theorem

Let \(\mat{A}\) have singular values \(\sigma_1 \ge \sigma_2 \ge \cdots\) and let \(\mat{A}_k\) be its truncation after \(k\) layers. For every matrix \(\mat{X}\) of the same shape with rank at most \(k\),

\[ \begin{aligned} \norm{\mat{A} - \mat{X}}_2 &\ge \norm{\mat{A} - \mat{A}_k}_2 = \sigma_{k+1}, \\ \norm{\mat{A} - \mat{X}}_F &\ge \norm{\mat{A} - \mat{A}_k}_F . \end{aligned} \]

In words: the truncated SVD is the best approximation of rank \(k\), whichever of the two norms you measure with. It need not be the only best one. If \({\sigma_k = \sigma_{k+1} > 0}\), swapping the layer of \(\sigma_k\) for that of \(\sigma_{k+1}\) does equally well; and in the spectral norm other matrices can match \(\mat{A}_k\) even when all the singular values differ.

Go deeper: the spectral-norm proof, by counting dimensions

Let \(\mat{X}\) have rank at most \(k\). The \(k + 1\) vectors \(\mat{X}\vect{v}_1, \dots, \mat{X}\vect{v}_{k+1}\) lie in the column space of \(\mat{X}\), which has dimension at most \(k\), so they are dependent: there are numbers \(c_1, \dots, c_{k+1}\), not all zero, with \({c_1\mat{X}\vect{v}_1 + \cdots + c_{k+1}\mat{X}\vect{v}_{k+1}} = \vect{0}\). Put \(\vect{w} = {c_1\vect{v}_1 + \cdots + c_{k+1}\vect{v}_{k+1}}\). It is not zero, because the \(\vect{v}_i\) are independent, and \(\mat{X}\vect{w} = \vect{0}\). Then

\[ \begin{aligned} \norm{(\mat{A} - \mat{X})\,\vect{w}}^2 &= \norm{\mat{A}\vect{w}}^2 \\ &= \Big\| \sum_{i \le k+1} c_i\,\sigma_i\,\vect{u}_i \Big\|^2 \\ &= \sum_{i \le k+1} c_i^2\,\sigma_i^2 \\ &\ge \sigma_{k+1}^2 \sum_{i \le k+1} c_i^2 \\ &= \sigma_{k+1}^2\,\norm{\vect{w}}^2 . \end{aligned} \]

So \(\mat{A} - \mat{X}\) stretches \(\vect{w}\) by at least \(\sigma_{k+1}\), and \(\norm{\mat{A} - \mat{X}}_2 \ge \sigma_{k+1}\). This is the proof of result 7.92 in Axler.

The Frobenius case follows from the spectral one. Put \(\mat{Y} = \mat{A} - \mat{X}\) and let \(\mat{Y}_{i-1}\) be its own truncation after \({i - 1}\) layers. A sum of matrices of rank at most \(k\) and \({i - 1}\) has rank at most \({k + i - 1}\), so the spectral case, used with \({k + i - 1}\) in place of \(k\), gives

\[ \norm{\mat{A} - (\mat{X} + \mat{Y}_{i-1})}_2 \ge \sigma_{k+i}(\mat{A}) . \]

The matrix inside the norm is \({\mat{Y} - \mat{Y}_{i-1}}\), and by Result 3 its spectral norm is \(\sigma_i(\mat{Y})\). So \({\sigma_i(\mat{A} - \mat{X})} \ge {\sigma_{k+i}(\mat{A})}\) for every \(i\). Squaring and adding over \(i\), with Result 2 for \(\mat{Y}\), gives \(\norm{\mat{A} - \mat{X}}_F^2 \ge {\sigma_{k+1}^2 + \sigma_{k+2}^2 + \cdots}\).

Worked example

The running rectangular matrix. \(\mat{B} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}\) has \(\sigma_1 = \sqrt3\) with \(\vect{u}_1 = {(2, 1, 1)/\sqrt6}\), \(\vect{v}_1 = {(1, 1)/\sqrt2}\), and \(\sigma_2 = 1\) with \(\vect{u}_2 = {(0, 1, -1)/\sqrt2}\), \(\vect{v}_2 = {(1, -1)/\sqrt2}\) (M03.5.3). The first layer is

\[ \begin{aligned} \mat{B}_1 &= \frac{\sqrt3}{\sqrt6\,\sqrt2} \begin{bmatrix} 2 \\ 1 \\ 1 \end{bmatrix}\begin{bmatrix} 1 & 1 \end{bmatrix} \\ &= \frac12 \begin{bmatrix} 2 & 2 \\ 1 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 0.5 & 0.5 \\ 0.5 & 0.5 \end{bmatrix} , \end{aligned} \]

because \({\sqrt6\,\sqrt2} = \sqrt{12} = 2\sqrt3\). Subtracting it from \(\mat{B}\) leaves the second layer.

A matrix equation. In blue, B with rows (1, 1), (1, 0), (0, 1). Equals, in vermillion, root 3 u 1 v 1 transpose, which is B 1, with rows (1, 1), (0.5, 0.5), (0.5, 0.5), labelled kept: rank one. Plus, in purple, 1 times u 2 v 2 transpose, which is B minus B 1, with rows (0, 0), (0.5, minus 0.5), (minus 0.5, 0.5), labelled dropped: the error. A box underneath reads: the squared Frobenius norm of B minus B 1 is 0.25 plus 0.25 plus 0.25 plus 0.25, which is 1, which is sigma 2 squared; and the spectral norm of B minus B 1 is sigma 2, which is 1.
M03.6.1-F4

\(\mat{B}\) split into its two layers. The dropped layer is the error, and both of its norms are \(\sigma_2 = 1\).

The error \(\mat{B} - \mat{B}_1\) has four entries of size \(0.5\), so its squared Frobenius norm is \({4 \times 0.25} = 1 = \sigma_2^2\), as Result 2 says. The error matrix has rank one, so its only singular value, \(1\), is its spectral norm, as Result 3 says. \(\mat{B}_1\) keeps \(3/(3 + 1) = 75\%\) of the energy.

A rank-2 matrix plus a small change. Rows 1 and 2 of \(\mat{R} = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\) are equal, so \(\mat{R}\) has rank 2. Suppose it is measured with small errors:

\[ \mat{M} = \begin{bmatrix} 1.05 & 0.95 & 0 \\ 0.95 & 1.05 & 0 \\ 0 & 0 & 1 \end{bmatrix} . \]

Now \(\det\mat{M} = {1.05^2 - 0.95^2} = 0.2\), so \(\mat{M}\) has full rank. It is symmetric, and one multiplication each checks three perpendicular eigenvectors: \({\mat{M}(1, 1, 0)} = (2, 2, 0)\), \({\mat{M}(0, 0, 1)} = (0, 0, 1)\) and \({\mat{M}(1, -1, 0)} = (0.1, -0.1, 0)\). The eigenvalues \(2\), \(1\) and \(0.1\) are positive, so they are also the singular values (M03.5.4). Dropping the last layer removes \({0.1 \cdot \tfrac12 (1, -1, 0)(1, -1, 0)\T}\), which is exactly the change, so \(\mat{M}_2 = \mat{R}\). Truncation has filtered the noise out, and \(\norm{\mat{M} - \mat{M}_2}_F = \norm{\mat{M} - \mat{M}_2}_2 = 0.1\).

Code

From scratch: the truncation as a sum of outer products, and the two error formulas.

import numpy as np

def truncate(A, k):
    """A_k: the sum of the first k layers sigma_i u_i v_i^T."""
    U, s, Vt = np.linalg.svd(np.asarray(A, dtype=float), full_matrices=False)
    return sum(s[i] * np.outer(U[:, i], Vt[i]) for i in range(k))

B = np.array([[1.0, 1.0], [1.0, 0.0], [0.0, 1.0]])
M = np.array([[1.05, 0.95, 0.0], [0.95, 1.05, 0.0], [0.0, 0.0, 1.0]])
print("B_1 =\n", truncate(B, 1).round(10))
print("singular values of M:", np.linalg.svd(M, compute_uv=False).round(10))
print("M_2 =\n", truncate(M, 2).round(10))

rng = np.random.default_rng(0)
A = rng.normal(size=(6, 5))
s = np.linalg.svd(A, compute_uv=False)
for k in range(1, 5):
    E = A - truncate(A, k)
    print(k, "Frobenius:", np.isclose(np.linalg.norm(E, "fro") ** 2, np.sum(s[k:] ** 2)),
          " spectral:", np.isclose(np.linalg.norm(E, 2), s[k]))
B_1 =
 [[1.  1. ]
 [0.5 0.5]
 [0.5 0.5]]
singular values of M: [2.  1.  0.1]
M_2 =
 [[1. 1. 0.]
 [1. 1. 0.]
 [0. 0. 1.]]
1 Frobenius: True  spectral: True
2 Frobenius: True  spectral: True
3 Frobenius: True  spectral: True
4 Frobenius: True  spectral: True

Now the theorem against rivals. A random matrix of rank \(k\) is a product of a \(6 \times k\) and a \(k \times 5\) matrix. We also try small nudges of \(\mat{A}_k\) itself, which stay at rank \(k\).

k = 2
U, s, Vt = np.linalg.svd(A, full_matrices=False)
best_F, best_2 = np.linalg.norm(A - truncate(A, k), "fro"), s[k]

worst_gap_F, worst_gap_2 = np.inf, np.inf
for trial in range(20000):
    if trial % 2 == 0:                       # a random rank-2 matrix
        X = rng.normal(size=(6, k)) @ rng.normal(size=(k, 5))
    else:                                    # a small nudge of the two factors of A_2
        left = U[:, :k] * s[:k] + 0.05 * rng.normal(size=(6, k))
        X = left @ (Vt[:k] + 0.05 * rng.normal(size=(k, 5)))
    worst_gap_F = min(worst_gap_F, np.linalg.norm(A - X, "fro") - best_F)
    worst_gap_2 = min(worst_gap_2, np.linalg.norm(A - X, 2) - best_2)
print("best errors:", round(best_F, 4), round(best_2, 4))
print("every rival farther away, in both norms:", worst_gap_F > 0 and worst_gap_2 > 0)
best errors: 2.11 1.9014
every rival farther away, in both norms: True

Twenty thousand rivals, and every one of them is farther from \(\mat{A}\) in both norms. A test of this kind cannot prove the theorem, but a single counterexample would have disproved it.

Explore

The module’s interactive, the rank slider, is in the next lesson. It rebuilds the \(48 \times 48\) picture of the second figure from its first \(k\) layers, for every \(k\) from 1 to 48, and prints the energy kept, which by Result 2 is the share of the sum of the \(\sigma_i^2\).

Pitfalls

Two tall panels, each with the dashed ellipse of A for comparison. Left, marked with a cross and titled Zero the smallest entry: a thick vermillion vertical segment, the image of the circle under X with rows (0, 0) and (4, 5), of half-length root 41, and two purple arrows along the horizontal axis labelled A minus X. Text: error, squared Frobenius norm 9; worst stretch 3. Right, marked with a tick and titled Drop the smallest layer: a thick vermillion segment along the long axis of the ellipse, of half-length 3 root 5, and two short purple arrows along the short axis labelled A minus A 1. Text: error, squared Frobenius norm 5; worst stretch root 5.
M03.6.1-F5

Wrong beside right. Both guesses have rank one. Zeroing the entry 3 of \(\mat{A}\) leaves an error of size 9 in squared Frobenius norm; dropping the small layer leaves only \(\sigma_2^2 = 5\).

“To simplify a matrix, set its smallest entries to zero.”

Small entries are not small layers. For \(\mat{A} = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix}\), zeroing the 3 gives a rank-one matrix \(\mat{X}\) whose error has squared Frobenius norm 9 and spectral norm 3. The truncation \(\mat{A}_1\) gives 5 and \(\sqrt5 \approx 2.24\). Size lives in the singular values, which mix all the entries.

“The error of \(\mat{A}_k\) is \(\sigma_{k+1}\), whatever norm I use.”

Only in the spectral norm. In the Frobenius norm every dropped layer counts. With singular values 5, 4, 3, 2, 1 and \(k = 2\), the spectral error is 3 but the Frobenius error is \(\sqrt{9 + 4 + 1} = \sqrt{14} \approx 3.74\).

“Keeping the largest eigenvalue term does the same job.”

For a symmetric matrix with non-negative eigenvalues it does, because there the two decompositions agree. For the running \(\mat{A} = \begin{bmatrix} 4 & 1 \\ 2 & 3 \end{bmatrix}\) the eigenvalue-5 term of \(\mat{P}\mat{D}\mat{P}^{-1}\) is \(\tfrac53\begin{bmatrix} 2 & 1 \\ 2 & 1 \end{bmatrix}\), and its error has squared Frobenius norm \(40/9 \approx 4.44\). The best rank-one copy does better: \(\sigma_2^2 = 15 - 5\sqrt5 \approx 3.82\). Eigenvectors that are not perpendicular do not give perpendicular layers, and Result 2 needs perpendicular layers.

Check yourself

Recall

1. What is the truncation \(\mat{A}_k\), and what is its rank?

Show answer

The sum of the first \(k\) layers \({\sigma_i\,\vect{u}_i\vect{v}_i\T}\) of the SVD. It has rank \(k\) (when \(k \le r\)).

2. What is \(\norm{\mat{A} - \mat{A}_k}_F^2\)?

Show answer

The sum of the squared singular values that were dropped, \({\sigma_{k+1}^2 + \cdots + \sigma_r^2}\).

3. What is \(\norm{\mat{A} - \mat{A}_k}_2\), and which unit vector is stretched that much?

Show answer

\(\sigma_{k+1}\), the largest dropped singular value. The error stretches \(\vect{v}_{k+1}\) by exactly that much.

4. Why are the layers \({\vect{u}_i\vect{v}_i\T}\) perpendicular to one another?

Show answer

Their entrywise dot product is \({(\vect{u}_i \cdot \vect{u}_j)(\vect{v}_i \cdot \vect{v}_j)}\), which is 0 for \(i \ne j\) and 1 for \(i = j\), because the \(\vect{u}\)’s and the \(\vect{v}\)’s are orthonormal.

5. What does the Eckart-Young theorem say?

Show answer

No matrix of rank at most \(k\) is closer to \(\mat{A}\) than \(\mat{A}_k\), in the spectral norm or in the Frobenius norm.

Exercises

1. ★ A matrix has singular values 10, 6, 3 and 1. Find the Frobenius and the spectral error of \(\mat{A}_2\), and the share of the energy it keeps.

Show solution

The dropped values are 3 and 1. The Frobenius error is \(\sqrt{9 + 1} = \sqrt{10} \approx 3.16\) and the spectral error is \(\sigma_3 = 3\). The energy is \(100 + 36 + 9 + 1 = 146\), of which \(\mat{A}_2\) keeps \(136\), a share of \(136/146 \approx 93.2\%\).

2. ★★ The running symmetric matrix \(\mat{S} = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}\) has eigenvalues 3 and 1 with eigenvectors \({(1, 1)/\sqrt2}\) and \({(1, -1)/\sqrt2}\). Find its best rank-one approximation and both errors.

Show solution

The eigenvalues are positive, so they are the singular values and \(\vect{u}_i = \vect{v}_i\). Then

\[ \mat{S}_1 = 3 \cdot \frac12 \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 1.5 & 1.5 \\ 1.5 & 1.5 \end{bmatrix} . \]

The error \(\mat{S} - \mat{S}_1\) has entries \(0.5\) on the diagonal and \(-0.5\) off it. Its squared Frobenius norm is \({4 \times 0.25} = 1 = \sigma_2^2\), and its spectral norm is \(\sigma_2 = 1\).

3. ★★★ Show that \(\norm{\mat{Y}}_2 \le \norm{\mat{Y}}_F\) for every matrix \(\mat{Y}\). Deduce, using only the spectral half of the Eckart-Young theorem, that every matrix \(\mat{X}\) of rank at most \(k\) has \(\norm{\mat{A} - \mat{X}}_F \ge \sigma_{k+1}\).

Show solution

By Result 3 with \(k = 0\), \(\norm{\mat{Y}}_2 = {\sigma_1(\mat{Y})}\), and by Result 2 with \(k = 0\), \(\norm{\mat{Y}}_F^2\) is the sum of all the squared singular values of \(\mat{Y}\), which is at least \(\sigma_1(\mat{Y})^2\). Taking square roots, \(\norm{\mat{Y}}_2 \le \norm{\mat{Y}}_F\).

Now put \(\mat{Y} = \mat{A} - \mat{X}\). The spectral half of the theorem gives \(\norm{\mat{A} - \mat{X}}_2 \ge \sigma_{k+1}\), so \(\norm{\mat{A} - \mat{X}}_F \ge \norm{\mat{A} - \mat{X}}_2 \ge \sigma_{k+1}\). This is weaker than the full Frobenius statement, whose bound is \(\sqrt{\sigma_{k+1}^2 + \sigma_{k+2}^2 + \cdots}\), but it needs no new tool.

Summary card

Keep the biggest layers: nothing of the same rank comes closer.

The anchor figure again: the matrix with rows (3, 0) and (4, 5) turns the unit circle into a long ellipse, and its best rank-one copy squashes the ellipse onto its long axis, dropping the short axis of length root 5.
M03.6.1-F1

Keep the long axis, drop the short.

  • Truncation. \(\mat{A}_k = {\sigma_1\vect{u}_1\vect{v}_1\T + \cdots + \sigma_k\vect{u}_k\vect{v}_k\T}\).
  • Frobenius error. \(\norm{\mat{A} - \mat{A}_k}_F^2 = {\sigma_{k+1}^2 + \cdots + \sigma_r^2}\).
  • Spectral error. \(\norm{\mat{A} - \mat{A}_k}_2 = \sigma_{k+1}\).
  • Eckart-Young. No matrix of rank at most \(k\) does better in either norm.

Sources and next steps

Sources. Each was opened and checked against this lesson on 15 November 2026.

  • Sheldon Axler, Linear Algebra Done Right, 4th edition (open access), Section 7F. Result 7.88 shows that the norm of a linear map is its largest singular value, and result 7.92, “best approximation by linear map whose range has dimension at most k”, proves that chopping the SVD after \(k\) terms leaves an error of exactly \(s_{k+1}\) and that no map of lower rank does better. The proof in the “deeper” block follows it.
  • Marc Deisenroth, Aldo Faisal and Cheng Soon Ong, Mathematics for Machine Learning, Section 4.6. Theorem 4.25 (the Eckart-Young theorem) gives the truncation as the best rank-\(k\) approximation in the spectral norm, equation (4.94), with error \(\sigma_{k+1}\), equation (4.95), and sketches the same dimension argument.
  • David Austin, Understanding Linear Algebra, Using singular value decompositions, subsection “Rank k approximations”: the matrices \(A_k\) built from the first \(k\) singular values approximate \(A\) with increasing accuracy and are, in a sense, the closest of rank \(k\).
  • NumPy, numpy.linalg.svd: with full_matrices=False the shapes are \((m, K)\) and \((K, n)\) for \(K = \min(m, n)\), the singular values are sorted in descending order, and the rows of Vh are the eigenvectors of \(\mat{A}\T\mat{A}\), that is the right singular vectors.

Next. M03.6.2 Image compression by rank puts the truncation to work on a photograph.

This lesson unlocks

M03.6.2 Image compression by rank

Your progress is saved in this browser only. No account, no tracking.
Back to top