Linear-Algebra-Done-Right · Unit 22 · Video 3 · Interactive Practice

Best Low-Rank Approximation: Truncate the SVD at k

IKey Formulas

Formula	Name	What it says
$T_kv = s_1\langle v, e_1\rangle f_1 + \cdots + s_k\langle v, e_k\rangle f_k$	Truncated SVD	$\dim \operatorname{range} T_k = k$
$\\|T - T_k\\| = s_{k+1}$	Error of the truncation	The first discarded singular value, for $1 \le k \lt m$
$\\|T - S\\| \ge s_{k+1}$ if $\dim \operatorname{range} S \le k$	No map does better	Some nonzero $u \in \operatorname{span}(e_1, \dots, e_{k+1})$ has $Su = 0$
$k(M + N + 1)$ numbers instead of $MN$	Storage of $T_k$	For an $M$ -by- $N$ matrix

Key Insight: $\min\{\|T - S\| : \dim \operatorname{range} S \le k\} = s_{k+1}$ , so the error depends only on the first singular value thrown away, not on how many come after it.

IICompressing a Matrix by Truncation

Keeping $k$ terms of the SVD of an 8-by-8 matrix leaves an error of exactly $s_{k+1}$ .

Terms kept k 2

IIINo Rank-One Map Gets Closer Than $s_2$

For $T(x, y) = (3x, 2y)$ , every map $Sv = \langle v, a\rangle b$ leaves $\|T - S\| \ge s_2 = 2$ .

💡 Challenge: find a rank-one $S$ other than $T_1$ that also reaches $\|T - S\| = 2$ .

IVQuiz Questions

Problem 1 · The Error of a Truncation

Given: $T \in \mathcal{L}(V, W)$ with positive singular values $9 \ge 5 \ge 2 \ge \tfrac12$ , and $T_2$ the first two terms of a singular value decomposition of $T$ — find $\|T - T_2\|$ .

✅ Correct!

T - T_2

is the tail

2\langle v, e_3\rangle f_3 + \tfrac12\langle v, e_4\rangle f_4

, whose largest coefficient is

s_3 = 2

❌ Not quite. The discarded singular values act on orthogonal directions, so they do not add: no unit vector gets stretched by

2 + \tfrac12

❌ Not quite.

5 = s_2

is the last singular value kept. The error is the first one discarded.

❌ Not quite.

\sqrt{2^2 + (1/2)^2}

would need one unit vector stretched by both discarded values at once; the norm is the largest single stretch.

Show solution

$(T - T_2)v = 2\langle v, e_3\rangle f_3 + \tfrac12\langle v, e_4\rangle f_4$ . Since $f_3, f_4$ is orthonormal and by Bessel's inequality,

\|(T - T_2)v\|^2 = 4|\langle v, e_3\rangle|^2 + \tfrac14|\langle v, e_4\rangle|^2 \le 4\big(|\langle v, e_3\rangle|^2 + |\langle v, e_4\rangle|^2\big) \le 4\|v\|^2.

And $(T - T_2)e_3 = 2f_3$ has length $2$ . So $\|T - T_2\| = s_3 = 2$ .

Problem 2 · The Best Rank-One Approximation

Given: $T \in \mathcal{L}(\mathbf{R}^3)$ defined by $T(x, y, z) = (x, -6y, 4z)$ — which $S$ with $\dim \operatorname{range} S \le 1$ minimizes $\|T - S\|$ ?

✅ Correct! The largest singular value is

6 = |-6|

, so

T_1 = (0, -6y, 0)

, and

\|T - T_1\| = s_2 = 4

❌ Not quite. The first coordinate is not the most important one: then

T - S = (0, -6y, 4z)

has norm

6

❌ Not quite. Singular values are absolute values:

|-6| = 6 > 4

. Keeping

4z

leaves

T - S = (x, -6y, 0)

with norm

6

❌ Not quite. This

S

has a range of dimension

2

, so it is not allowed.

Show solution

$T^*T(x, y, z) = (x, 36y, 16z)$ , so the singular values are $6, 4, 1$ . A singular value decomposition is $Tv = 6\langle v, e_2\rangle(-e_2) + 4\langle v, e_3\rangle e_3 + 1\langle v, e_1\rangle e_1$ , with $e_1, e_2, e_3$ the standard basis. Truncating after one term gives

T_1(x, y, z) = 6y\,(-e_2) = (0, -6y, 0),

and $(T - T_1)(x, y, z) = (x, 0, 4z)$ has norm $4 = s_2$ . By the best-approximation theorem no $S$ with $\dim \operatorname{range} S \le 1$ comes closer. The other choices leave the stretch $6$ in $T - S$ .

Problem 3 · How Much Storage

Given: a $500$ -by- $300$ matrix stored as its truncation $T_k$ with $k = 10$ (the $s_j$ , the $e_j$ and the $f_j$ for $j \le 10$ ) — how many numbers are stored?

✅ Correct!

10(500 + 300 + 1) = 8010

, about

5.3\%

of the

150\,000

entries.

❌ Not quite.

500 \cdot 300

stores every entry, which is what the truncation avoids.

❌ Not quite. That counts the vectors

e_j

and

f_j

but forgets the

10

singular values themselves.

❌ Not quite. Each term needs a vector in

\mathbf{F}^{300}

and a vector in

\mathbf{F}^{500}

, plus

s_j

Show solution

The matrix is a map from $\mathbf{F}^{300}$ to $\mathbf{F}^{500}$ . Each of the $k = 10$ terms $s_j\langle v, e_j\rangle f_j$ needs the number $s_j$ , the vector $e_j \in \mathbf{F}^{300}$ and the vector $f_j \in \mathbf{F}^{500}$ :

10\,(1 + 300 + 500) = 8010

numbers, instead of $500 \cdot 300 = 150\,000$ . The largest error on a unit vector is $s_{11}$ .

Problem 4 · A Repeated Singular Value

Given: $T \in \mathcal{L}(V, W)$ with positive singular values $7 \ge 3 \ge 3 \ge 1$ — find $\min\{\|T - S\| : S \in \mathcal{L}(V, W),\ \dim \operatorname{range} S \le 2\}$ .

✅ Correct! The minimum is

s_3 = 3

; the repeated value means dropping the third term costs as much as dropping the second would.

❌ Not quite.

1 = s_4

is the error for

k = 3

. With

k = 2

the first discarded value is

s_3 = 3

; repeated values are listed separately.

❌ Not quite.

T

has four positive singular values, so

\dim \operatorname{range} T = 4

, and no map with a range of dimension

2

equals it.

❌ Not quite.

\sqrt{3^2 + 1^2}

adds the discarded stretches in quadrature, but the norm is the largest single one.

Show solution

Here $m = 4$ and $k = 2 \lt m$ , so by the best-approximation theorem the minimum is $s_{k+1} = s_3$ . The list of singular values repeats $3$ , so $s_2 = s_3 = 3$ :

\min\{\|T - S\| : \dim \operatorname{range} S \le 2\} = s_3 = 3,

attained at $S = T_2$ , for which $T - T_2 = 3\langle v, e_3\rangle f_3 + \langle v, e_4\rangle f_4$ .

Solved: 0 / 4

Best Low-Rank Approximation: Truncate the SVD at k

IKey Formulas

IICompressing a Matrix by Truncation

IIINo Rank-One Map Gets Closer Than s2s_2s2​

IVQuiz Questions

IIINo Rank-One Map Gets Closer Than $s_2$