特異値分解求め方・低ランク近似・擬似逆行列

任意の $m \times n$ 実行列 $A$ は、直交行列 $U$ （ $m$ 次）、 $V$ （ $n$ 次）と、対角に $\sigma_1 \ge \sigma_2 \ge \cdots \ge 0$ を並べた $m \times n$ 行列 $\Sigma$ によって $A = U\Sigma V^{\mathsf T}$ と分解できる。特異値 $\sigma_i$ は $A^{\mathsf T}A$ の固有値の正の平方根で、 $V$ の列は $A^{\mathsf T}A$ の正規直交固有ベクトル、 $U$ の列は $\boldsymbol{u}_i = A\boldsymbol{v}_i/\sigma_i$ で求める。 $0$ でない特異値の個数が $\operatorname{rank} A$ で、大きい方から $k$ 個だけ残すと、階数 $k$ の行列の中で $A$ に最も近いものが得られる。

線形代数の第9単元（全9単元）。先に読む単元：内積と直交対角化、二次形式と正定値行列

院試数学基礎完成シリーズ線形代数編

基礎ノートと類題を答案の形で解いた問題集（2,480円）。収録章と見本ページを商品ページで確認できる。過去問の本文は収録していない。

線形代数編の内容を見る

特異値と特異値分解の定義

定義

特異値

$A$ を $m \times n$ 実行列とする。 $A^{\mathsf T}A$ は $n$ 次の半正定値対称行列なので、固有値はすべて $0$ 以上である。それを $\mu_1 \ge \cdots \ge \mu_n \ge 0$ と並べ、 $\sigma_i = \sqrt{\mu_i}$ を $A$ の特異値という。 $\boldsymbol{v}$ が $A^{\mathsf T}A$ の固有ベクトルなら $\|A\boldsymbol{v}\|^2 = \boldsymbol{v}^{\mathsf T}A^{\mathsf T}A\boldsymbol{v} = \mu\|\boldsymbol{v}\|^2$ で、 $\sigma$ は単位ベクトル $\boldsymbol{v}$ が $A$ で何倍に伸びるかを表す。

定理・法則

特異値分解の存在

条件

$A$ は任意の $m \times n$ 実行列で、 $r = \operatorname{rank} A$ 。正方行列である必要も、対角化可能である必要もない。

主張

$m$ 次直交行列 $U$ 、 $n$ 次直交行列 $V$ があって

A = U\Sigma V^{\mathsf T}, \qquad \Sigma = \begin{pmatrix} \operatorname{diag}(\sigma_1, \dots, \sigma_r) & O \\ O & O \end{pmatrix} \ (m \times n)

と書ける。 $\sigma_1 \ge \cdots \ge \sigma_r > 0$ は $0$ でない特異値で、 $\Sigma$ は $A$ から一通りに決まる。和の形では $A = \sum_{i=1}^{r} \sigma_i \boldsymbol{u}_i\boldsymbol{v}_i^{\mathsf T}$ 。

要点

$U, V$ は一通りではない。特異値が相異なれば、 $\boldsymbol{u}_i, \boldsymbol{v}_i$ の組を同時に $-1$ 倍する自由度を除いて決まる。複素行列では直交行列をユニタリ行列に、転置を共役転置に替えて同じことが成り立つ。

特異値分解の求め方

$A^{\mathsf T}A$ （ $n$ 次）の固有値 $\mu_1 \ge \cdots \ge \mu_n$ を求め、 $\sigma_i = \sqrt{\mu_i}$ とする。
$A^{\mathsf T}A$ の正規直交固有ベクトル $\boldsymbol{v}_1, \dots, \boldsymbol{v}_n$ を、固有値の大きい順に並べて $V$ とする。
$\sigma_i > 0$ の $i$ について $\boldsymbol{u}_i = A\boldsymbol{v}_i/\sigma_i$ とする。これらは自動的に正規直交になる。
$m > r$ なら、 $\boldsymbol{u}_1, \dots, \boldsymbol{u}_r$ に直交する単位ベクトルを補って $U$ を $m$ 次直交行列にする（ $A^{\mathsf T}$ の核、つまり $A^{\mathsf T}\boldsymbol{u} = \boldsymbol{0}$ の解から選ぶ）。

$m < n$ のときは $AA^{\mathsf T}$ （ $m$ 次）から始め、 $U$ を先に決めて $\boldsymbol{v}_i = A^{\mathsf T}\boldsymbol{u}_i/\sigma_i$ としてもよい。 $AA^{\mathsf T}$ と $A^{\mathsf T}A$ の $0$ でない固有値は一致する。

特異値と行列の量の関係

2ノルム（作用素ノルム）: $\|A\|_2 = \max_{\|\boldsymbol{x}\| = 1}\|A\boldsymbol{x}\| = \sigma_1$
フロベニウスノルム: $\|A\|_F^2 = \sum_{i,j} a_{ij}^2 = \operatorname{tr}(A^{\mathsf T}A) = \sigma_1^2 + \cdots + \sigma_r^2$
正方行列の行列式: $|\det A| = \sigma_1\sigma_2\cdots\sigma_n$
条件数: $\kappa(A) = \frac{\sigma_1}{\sigma_n}$
$n$ 次正則行列のとき。大きいほど連立方程式の解が誤差に敏感になる。
擬似逆行列（ムーア・ペンローズ逆）: $A^{+} = V\Sigma^{+}U^{\mathsf T}$
$\Sigma^{+}$ は $\Sigma$ を転置し、 $0$ でない対角成分を逆数にした $n \times m$ 行列。 $A$ の列が一次独立なら $A^{+} = (A^{\mathsf T}A)^{-1}A^{\mathsf T}$ 。

実対称行列では特異値は固有値の絶対値 $|\lambda_i|$ になる。半正定値対称行列では、直交対角化 $A = Q\Lambda Q^{\mathsf T}$ がそのまま特異値分解である。一般の正方行列では、特異値と固有値の絶対値は一致しない。

低ランク近似と最小二乗法

定理・法則

エッカート・ヤングの定理

条件

$A$ は $m \times n$ 実行列で、特異値分解 $A = \sum_{i=1}^{r}\sigma_i\boldsymbol{u}_i\boldsymbol{v}_i^{\mathsf T}$ をもつ。 $k < r$ とし、 $A_k = \sum_{i=1}^{k}\sigma_i\boldsymbol{u}_i\boldsymbol{v}_i^{\mathsf T}$ と置く。

主張

階数が $k$ 以下の行列 $B$ の中で、 $\|A - B\|_2$ と $\|A - B\|_F$ を最小にするのは $B = A_k$ で、

\|A - A_k\|_2 = \sigma_{k+1}, \qquad \|A - A_k\|_F = \sqrt{\sigma_{k+1}^2 + \cdots + \sigma_r^2}

要点

主成分分析は、データ行列（各列から平均を引いたもの）の特異値分解で、大きい特異値に対応する $\boldsymbol{v}_i$ が主成分の方向になる。

定理・法則

最小二乗解と擬似逆行列

条件

$A$ は $m \times n$ 実行列、 $\boldsymbol{b} \in \mathbb{R}^m$ 。

主張

$\|A\boldsymbol{x} - \boldsymbol{b}\|$ を最小にする $\boldsymbol{x}$ のうちノルムが最小のものは $\boldsymbol{x} = A^{+}\boldsymbol{b}$ である。 $A$ の列が一次独立なら、最小二乗解はただ一つで、正規方程式 $A^{\mathsf T}A\boldsymbol{x} = A^{\mathsf T}\boldsymbol{b}$ の解 $(A^{\mathsf T}A)^{-1}A^{\mathsf T}\boldsymbol{b}$ に一致する。

要点

$A\boldsymbol{x}$ は $A$ の列空間を動くので、 $\boldsymbol{b}$ の列空間への正射影に一致する $\boldsymbol{x}$ が最小二乗解になる。

特異値分解の計算例

計算例

2次正方行列の特異値分解

$A = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix}$ の特異値分解を求めよ。

解答

$A^{\mathsf T}A = \begin{pmatrix} 25 & 20 \\ 20 & 25 \end{pmatrix}$ の固有値は $45, 5$ 、固有ベクトルは $\boldsymbol{v}_1 = \frac{1}{\sqrt{2}}(1, 1)^{\mathsf T}$ 、 $\boldsymbol{v}_2 = \frac{1}{\sqrt{2}}(1, -1)^{\mathsf T}$ 。特異値は $\sigma_1 = 3\sqrt{5}$ 、 $\sigma_2 = \sqrt{5}$ 。

\boldsymbol{u}_1 = \frac{A\boldsymbol{v}_1}{\sigma_1} = \frac{1}{3\sqrt{5}}\cdot\frac{1}{\sqrt{2}}\begin{pmatrix} 3 \\ 9 \end{pmatrix} = \frac{1}{\sqrt{10}}\begin{pmatrix} 1 \\ 3 \end{pmatrix}, \qquad \boldsymbol{u}_2 = \frac{A\boldsymbol{v}_2}{\sigma_2} = \frac{1}{\sqrt{10}}\begin{pmatrix} 3 \\ -1 \end{pmatrix}

A = \frac{1}{\sqrt{10}}\begin{pmatrix} 1 & 3 \\ 3 & -1 \end{pmatrix}\begin{pmatrix} 3\sqrt{5} & 0 \\ 0 & \sqrt{5} \end{pmatrix}\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}^{\mathsf T}

検算

$(\boldsymbol{u}_1, \boldsymbol{u}_2) \propto 3 - 3 = 0$ 。 $\sigma_1\sigma_2 = 15 = |\det A|$ 、 $\sigma_1^2 + \sigma_2^2 = 50 = 9 + 16 + 25 = \|A\|_F^2$ 。 $A$ の固有値は $3, 5$ で、特異値とは異なる。

計算例

縦長の行列の特異値分解と擬似逆行列

$A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix}$ の特異値分解と擬似逆行列を求め、 $A\boldsymbol{x} = (1, 2, 3)^{\mathsf T}$ の最小二乗解を求めよ。

解答

$A^{\mathsf T}A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ の固有値は $3, 1$ で、 $\sigma_1 = \sqrt{3}$ 、 $\sigma_2 = 1$ 。 $\boldsymbol{v}_1 = \frac{1}{\sqrt{2}}(1, 1)^{\mathsf T}$ 、 $\boldsymbol{v}_2 = \frac{1}{\sqrt{2}}(1, -1)^{\mathsf T}$ 。

$\boldsymbol{u}_1 = A\boldsymbol{v}_1/\sqrt{3} = \frac{1}{\sqrt{6}}(2, 1, 1)^{\mathsf T}$ 、 $\boldsymbol{u}_2 = A\boldsymbol{v}_2 = \frac{1}{\sqrt{2}}(0, 1, -1)^{\mathsf T}$ 。両方に直交する単位ベクトルとして $\boldsymbol{u}_3 = \frac{1}{\sqrt{3}}(1, -1, -1)^{\mathsf T}$ を補う。 $\Sigma = \begin{pmatrix} \sqrt{3} & 0 \\ 0 & 1 \\ 0 & 0 \end{pmatrix}$ 。

列が一次独立なので

A^{+} = (A^{\mathsf T}A)^{-1}A^{\mathsf T} = \frac{1}{3}\begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} = \frac{1}{3}\begin{pmatrix} 1 & 2 & -1 \\ 1 & -1 & 2 \end{pmatrix}

最小二乗解は $\boldsymbol{x} = A^{+}(1, 2, 3)^{\mathsf T} = \left(\frac{2}{3}, \frac{5}{3}\right)^{\mathsf T}$ 。

検算

残差 $A\boldsymbol{x} - \boldsymbol{b} = (\frac{7}{3}, \frac{2}{3}, \frac{5}{3}) - (1, 2, 3) = (\frac{4}{3}, -\frac{4}{3}, -\frac{4}{3})$ は $\boldsymbol{u}_3$ に平行で、 $A$ の2つの列のどちらとも内積 $0$ になる（正規方程式が成り立つ）。 $V\Sigma^{+}U^{\mathsf T}$ を計算しても同じ $A^{+}$ になる。

計算例

階数1の近似と誤差

$A = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix}$ に2ノルムで最も近い階数1の行列と、その誤差を求めよ。

解答

最初の例の分解から

A_1 = \sigma_1\boldsymbol{u}_1\boldsymbol{v}_1^{\mathsf T} = 3\sqrt{5}\cdot\frac{1}{\sqrt{10}}\begin{pmatrix} 1 \\ 3 \end{pmatrix}\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \end{pmatrix} = \frac{3}{2}\begin{pmatrix} 1 & 1 \\ 3 & 3 \end{pmatrix}

誤差は $\|A - A_1\|_2 = \sigma_2 = \sqrt{5}$ 。

検算

$A - A_1 = \begin{pmatrix} 3/2 & -3/2 \\ -1/2 & 1/2 \end{pmatrix}$ は階数1で、フロベニウスノルムの2乗は $\frac{9}{4} + \frac{9}{4} + \frac{1}{4} + \frac{1}{4} = 5 = \sigma_2^2$ になる。

答案でよくある誤り

1
特異値を $A$ の固有値と同じものとする。特異値は $A^{\mathsf T}A$ の固有値の平方根である。 $\begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix}$ の固有値は $3, 5$ 、特異値は $3\sqrt{5}, \sqrt{5}$ と異なる。一致するのは対称な半正定値行列のときである。
2
$U$ を $AA^{\mathsf T}$ の固有ベクトルから、 $V$ を $A^{\mathsf T}A$ の固有ベクトルから別々に求めて並べる。固有ベクトルの符号が独立に決まるため、 $A = U\Sigma V^{\mathsf T}$ が成り立たないことがある。片方を決めたら $\boldsymbol{u}_i = A\boldsymbol{v}_i/\sigma_i$ でもう片方を作る。
3
縦長の行列で $U$ を $m$ 次直交行列に補わない。完全な特異値分解では $U$ は $m$ 次、 $\Sigma$ は $m \times n$ である。 $r$ 列だけ使う縮約形を答えるなら、そう明記する。
4
特異値の並び順と $U, V$ の列の順をずらす。 $\Sigma$ の対角は大きい順に並べ、 $\boldsymbol{u}_i, \boldsymbol{v}_i$ を同じ番号で対応させる。
5
列が一次独立でない行列に $(A^{\mathsf T}A)^{-1}A^{\mathsf T}$ を使う。そのとき $A^{\mathsf T}A$ は正則でない。擬似逆行列は $V\Sigma^{+}U^{\mathsf T}$ で求める。

特異値分解が出た院試の過去問

院試hubが年度別解説の大問を分類した集計から、この単元の内容を扱う出題を挙げる。問題文は各大学の公式過去問で確かめ、解き方は各年度の解説ページで読める。