§D3.18特異値分解と低ランク近似

証明. 1について。$(A^\top A)^\top = A^\top A$より対称である。$A^\top A\vec x = \lambda \vec x$、$\vec x \ne \vec 0$とすると$\lambda \|\vec x\|^2 = \vec x^\top A^\top A \vec x = (A\vec x)^\top (A\vec x) = \|A\vec x\|^2 \ge 0$であるから$\lambda \ge 0$である。

2について。$A\vec x = \vec 0$ならば$A^\top A\vec x = \vec 0$である。逆に$A^\top A \vec x = \vec 0$ならば$\|A\vec x\|^2 = \vec x^\top A^\top A\vec x = 0$であるから、内積の正定値性より$A\vec x = \vec 0$である。よって核が一致し、§D3.10 系 4.1を両者に適用して階数も一致する。▨

証明.$A^\top A$は実対称であるから、§D3.15 定理 3.1により、直交行列で対角化される。すなわち$\mathbb{R}^n$の正規直交基底$\vec v_1, \dots, \vec v_n$と実数$\lambda_1 \ge \dots \ge \lambda_n$が存在して$A^\top A \vec v_j = \lambda_j \vec v_j$が成り立つ。補題 1.1より$\lambda_j \ge 0$である。

$0$でない$\lambda_j$の個数が$r$であることを示す。$\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$とおくと$A^\top A = V\Lambda V^{\top}$である。正則行列を掛けても像の次元は変わらない（正則行列$P$による写像は全単射であるから$\dim P(\operatorname{Im} M) = \dim \operatorname{Im} M$であり、また$\operatorname{Im}(MP) = \operatorname{Im} M$である）から$\operatorname{rank}(A^\top A) = \operatorname{rank}\Lambda$であり、対角行列の階数は$0$でない対角成分の個数である。補題 1.1の2より、この個数は$r$に等しい。$\lambda_j$は大きい順に並んでいるので$\lambda_1 \ge \dots \ge \lambda_r > 0$、$\lambda_j = 0$（$j > r$）である。

$i \le r$に対し$\sigma_i = \sqrt{\lambda_i} > 0$、$\vec u_i = \dfrac{1}{\sigma_i}A\vec v_i$と定める。$r < i \le p$に対しては$\sigma_i = \sqrt{\lambda_i} = 0$と定める（$p \le n$であることに注意する）。$i, j \le r$について

であり、右辺は$i = j$のとき$1$、$i \ne j$のとき$0$である。よって$\vec u_1, \dots, \vec u_r$は$\mathbb{R}^m$の正規直交系である。§D3.11 補題 1.2によりこれを$\mathbb{R}^m$の基底へ延長し、付け加えたベクトルに§D3.14 定理 2.1を適用すると、はじめの$r$本はすでに正規直交であるから変わらず、$\mathbb{R}^m$の正規直交基底$\vec u_1, \dots, \vec u_m$が得られる。

$j > r$については$\|A\vec v_j\|^2 = \vec v_j^{\top}A^\top A\vec v_j = \lambda_j = 0$より$A\vec v_j = \vec 0$である。そこで$B = \sum_{i=1}^{r}\sigma_i \vec u_i\vec v_i^{\top}$とおくと、$j \le r$のとき$B\vec v_j = \sigma_j \vec u_j = A\vec v_j$、$j > r$のとき$B\vec v_j = \vec 0 = A\vec v_j$である。$\vec v_1, \dots, \vec v_n$は基底であるから$A = B$である。

行列の形については、$\Sigma = \sum_{i=1}^{p}\sigma_i \vec\varepsilon_i \vec\delta_i^{\top}$（$\vec\varepsilon_i$は$\mathbb{R}^m$の、$\vec\delta_i$は$\mathbb{R}^n$の標準基底）と書けるので

となる。$U$と$V$は列が正規直交基底であるから、§D3.15 命題 1.2より直交行列である。▨

証明.$A = U\Sigma V^{\top}$より$A^\top A = V\Sigma^\top\Sigma V^{\top}$である。$\Sigma^\top \Sigma$は対角成分が$\sigma_1^2, \dots, \sigma_p^2, 0, \dots, 0$である$n$次対角行列であるから、$A^\top A$の固有値はこれらである。固有値は$A^\top A$が定める線形写像から定まり、$A^\top A$は$A$から定まるので、$\sigma_1 \ge \dots \ge \sigma_p \ge 0$は$A$から一意に定まる。▨

証明.$\mathbb{R}^m$の標準基底を$\vec\varepsilon_1, \dots, \vec\varepsilon_m$とする。§D3.14 命題 3.1より、任意の$\vec x \in \mathbb{R}^m$について$\vec x = \sum_i \langle \vec x, \vec\varepsilon_i\rangle \vec\varepsilon_i$であり、両辺と$\vec x$の内積を取ると$\|\vec x\|^2 = \sum_i \langle \vec x, \vec\varepsilon_i\rangle^2$である。また$\langle A\vec w, \vec y\rangle = (A\vec w)^\top \vec y = \vec w^\top (A^\top \vec y) = \langle \vec w, A^\top \vec y\rangle$である。よって

となる。最後の等号では、$\vec w_1, \dots, \vec w_n$が$\mathbb{R}^n$の正規直交基底であることから上と同じ等式を$A^\top\vec\varepsilon_i$に適用した。右辺は$\vec w_j$の取り方を含まない。$\vec w_j$として標準基底を取れば左辺は$\sum_{i,j}a_{ij}^2 = \|A\|_F^2$である。▨

証明.$c_j = \sum_{i=1}^{k}\langle \vec g_j, \vec w_i\rangle^2$とおく。§D3.14 命題 3.1より$\vec w_i = \sum_j \langle \vec w_i, \vec g_j\rangle \vec g_j$であるから$\vec w_i^{\top}M\vec w_i = \sum_j \mu_j \langle \vec w_i, \vec g_j\rangle^2$であり、$i$について加えると

となる。§D3.14 命題 3.2のベッセルの不等式より$c_j \le \|\vec g_j\|^2 = 1$であり、明らかに$c_j \ge 0$である。また$\sum_j c_j = \sum_i \sum_j \langle \vec w_i, \vec g_j\rangle^2 = \sum_i \|\vec w_i\|^2 = k$である。

$k = m$ならば$c_j = 1$がすべての$j$について成り立ち、等号である。$k < m$とする。$s = \sum_{j \le k}(1 - c_j)$とおくと$\sum_j c_j = k$より$s = \sum_{j>k}c_j$である。$j \le k$について$\mu_j \ge \mu_{k+1}$かつ$1 - c_j \ge 0$であるから$\sum_{j\le k}\mu_j(1-c_j) \ge \mu_{k+1}s$であり、$j > k$について$\mu_j \le \mu_{k+1}$かつ$c_j \ge 0$であるから$\sum_{j>k}\mu_j c_j \le \mu_{k+1}s$である。よって

となる。$\vec w_i = \vec g_i$のときは$c_j$が$j \le k$で$1$、$j > k$で$0$となり、等号が成り立つ。▨

証明.$k \ge p$の場合、$\min(k,r) = r$より$A_k = A$であり、右辺の和は空であるから主張は明らかである。以下$k < p \le m$とする。

まず$\|A - A_k\|_F^2$を求める。$j \le k$のとき$(A - A_k)\vec v_j = \sigma_j\vec u_j - \sigma_j\vec u_j = \vec 0$、$k < j \le r$のとき$(A-A_k)\vec v_j = \sigma_j \vec u_j$、$j > r$のとき$(A-A_k)\vec v_j = \vec 0$である。補題 3.2を正規直交基底$\vec v_1, \dots, \vec v_n$について用いると$\|A - A_k\|_F^2 = \sum_{k < i \le r}\sigma_i^2$であり、$r < i \le p$では$\sigma_i = 0$であるから、これは$\sum_{k<i\le p}\sigma_i^2$に等しい。同じ補題を$A$について用いると$\|A\|_F^2 = \sum_{i \le p}\sigma_i^2$である。また$A_k$の像は$\operatorname{span}\{\vec u_1, \dots, \vec u_k\}$に含まれるので$\operatorname{rank}A_k \le k$である。

次に、$\operatorname{rank}B \le k$を満たす$B$を取る。$W = \operatorname{Im}B$の次元は$k$以下であるから、$W$の正規直交基底を取り、必要ならば§D3.11 補題 1.2と§D3.14 定理 2.1によって$\mathbb{R}^m$の中で正規直交系$\vec w_1, \dots, \vec w_k$へ延長する。$W \subseteq \operatorname{span}\{\vec w_1,\dots,\vec w_k\} =: W'$である。$P = \sum_{i=1}^{k}\vec w_i\vec w_i^{\top}$とおくと、$P\vec x = \sum_i \langle \vec x, \vec w_i\rangle \vec w_i$であるから、§D3.14 命題 3.2より$P\vec x$は$W'$の中で$\vec x$に最も近い点である。$A$と$B$の第$j$列を$\vec a_j$、$\vec b_j$と書くと$\vec b_j \in W \subseteq W'$であるから

である。さらに$\vec a_j - P\vec a_j$は$W'$に直交し$P\vec a_j \in W'$であるから、ピタゴラスの定理により$\|\vec a_j - P\vec a_j\|^2 = \|\vec a_j\|^2 - \|P\vec a_j\|^2$であり

となる。ここで

である。$AA^{\top} = U\Sigma\Sigma^{\top}U^{\top}$であり、$\Sigma\Sigma^{\top}$は対角成分が$\sigma_1^2, \dots, \sigma_p^2, 0, \dots, 0$である$m$次対角行列であるから、$AA^{\top}$の固有値を大きい順に並べたものは$\sigma_1^2 \ge \dots \ge \sigma_p^2 \ge 0 \ge \dots$であり、対応する正規直交な固有ベクトルとして$\vec u_1, \dots, \vec u_m$を取ることができる。補題 3.3より$\sum_i \vec w_i^{\top}AA^{\top}\vec w_i \le \sum_{i \le k}\sigma_i^2$である。したがって

となる。▨

証明.§D3.17 定理 2.2より、$\vec x$が最小二乗解であることと$A^\top A\vec x = A^\top \vec b$が成り立つことは同値である。$\vec x = \sum_j c_j \vec v_j$と書くと、$A^\top A\vec v_j = \lambda_j \vec v_j = \sigma_j^2 \vec v_j$（$j \le p$）、$A^\top A \vec v_j = \vec 0$（$j > p$）であるから$A^\top A\vec x = \sum_{j\le r}\sigma_j^2 c_j \vec v_j$である。一方$A^\top = \sum_{i\le r}\sigma_i \vec v_i\vec u_i^{\top}$であるから$A^\top \vec b = \sum_{i\le r}\sigma_i \langle \vec b, \vec u_i\rangle \vec v_i$である。$\vec v_1, \dots, \vec v_n$は基底であるから、両者が等しいことは、$j \le r$について$\sigma_j^2 c_j = \sigma_j\langle \vec b, \vec u_j\rangle$が成り立つことと同値であり、$\sigma_j > 0$より$c_j = \langle \vec b, \vec u_j\rangle / \sigma_j$と同値である。$j > r$の成分には条件が付かない。これが主張の表示である。

$r = n$のときは自由な成分がないので解はただ一つである。ノルムについては、$\|\vec x\|^2 = \sum_j c_j^2$であり、$j > r$の成分を$0$に取ったものが最小であるから、$\vec x^{+}$がノルム最小の最小二乗解である。▨