エッカート・ヤング・ミルスキーの定理

達成可能性。 $U, V$ が正規直交な列を持つため、$\|A - A_k\|_2 = \|U(\Sigma - \Sigma_k)V^\top\|_2 = \|\Sigma - \Sigma_k\|_2$ であり、ここで $\Sigma_k$ は上位 $k$ 個の特異値を残し残りをゼロにしたものである。$\Sigma - \Sigma_k$ は成分 $0, \dots, 0, \sigma_{k+1}, \dots, \sigma_r$ を持つ対角行列であるため、その作用素ノルムは最大成分 $\sigma_{k+1}$ である。

最適性。 $\operatorname{rank}(B) \le k$ を満たす任意の行列 $B$ をとる；その零空間（核）の次元は少なくとも $n - k$ である。$S = \operatorname{span}(v_1, \dots, v_{k+1})$ を $(k+1)$ 次元部分空間とする。$\dim(\ker B) + \dim(S) \ge (n-k) + (k+1) = n+1 > n$ であるため、この2つの部分空間は原点以外でも交わらねばならない: $Bz = 0$ を満たす単位ベクトル $z \in S$ が存在する。

$z = \sum_{i=1}^{k+1} c_i v_i$（$\sum_{i=1}^{k+1} c_i^2 = 1$、$z$ が単位ノルムを持ち $v_i$ が正規直交であるため）と書く。$Bz = 0$ であるから、$u_i$ の正規直交性を用いて $\|(A-B)z\| = \|Az\| = \left\|\sum_{i=1}^{k+1} c_i \sigma_i u_i\right\| = \sqrt{\sum_{i=1}^{k+1} c_i^2 \sigma_i^2}$ となる。

$i \le k+1$ に対して $\sigma_i \ge \sigma_{k+1}$ であるため、$\sum_{i=1}^{k+1} c_i^2 \sigma_i^2 \ge \sigma_{k+1}^2 \sum_{i=1}^{k+1} c_i^2 = \sigma_{k+1}^2$。よって、ランク $\le k$ の任意の行列 $B$ に対して $\|A-B\|_2 \ge \|(A-B)z\| \ge \sigma_{k+1}$ となり、達成可能性と合わせて定理が証明される。