特異値分解とは｜正方でない行列にも使える分解と、その意味

どんな行列も、回転と伸縮と回転の 3 段階に分けられる。

$$A=U\Sigma V^{\top }$$

$U$ と $V$ は直交行列で、$\Sigma$ は対角に非負の数が並ぶ行列である。正方でなくても、階数が足りなくても、この形にできる。対角化が使えない行列にも通じる分解になっている。

特異値分解の形

$\Sigma$ の対角に並ぶ数を特異値といい、大きい順に ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge 0$ と並べる。負の値は現れない。

$U$ の列を左特異ベクトル、$V$ の列を右特異ベクトルという。どちらも正規直交で、$V^{\top }$ が先に働き、$U$ が最後に働く。

対角化 $A=P\Lambda P^{-1}$ とは形が違う。両側で別々の直交行列を使うので、$P$ と $P^{-1}$ のように対で打ち消し合う関係にはない。

行列の大きさの対応

$A$ が $m\times n$ の行列なら、$U$ は $m$ 次、$V$ は $n$ 次の正方行列である。$\Sigma$ は $A$ と同じ $m\times n$ で、対角の外はすべて 0 になる。

特異値の個数は $m$ と $n$ の小さいほうまでである。縦長なら列の数だけ、横長なら行の数だけ並ぶ。

行の数と列の数が違っても分解できる点が、対角化との大きな違いである。対角化は正方行列にしか定義できない。

特異値は転置との積から出る

$A=U\Sigma V^{\top }$ を使って $A^{\top }A$ を作ると、$U$ が中央で打ち消し合う。

$$A^{\top }A=V{\Sigma }^{\top }\Sigma V^{\top }$$

右辺は対称行列の対角化の形である。したがって $A^{\top }A$ の固有値が ${\sigma }_i^2$ で、固有ベクトルが右特異ベクトルになる。

$A^{\top }A$ は半正定値なので固有値は 0 以上であり、平方根が取れる。特異値が非負なのは、この作り方のためである。

例：2 次の行列で特異値を求める

$$A=\left(\begin{array}{cc}2& 2\\ -1& 1\end{array}\right)$$

$A^{\top }A$ を計算すると $(5,3;3,5)$ になる。固有値は $5+3=8$ と $5-3=2$ である。

平方根を取って、特異値は $2\sqrt{2}$ と $\sqrt{2}$ になる。積は 4 で、$A$ の行列式の絶対値と一致する。

固有値そのものを求めると $A$ は複素固有値を持つが、特異値はいつでも実数である。

特異ベクトルの対応

右特異ベクトル $v_i$ に $A$ を掛けると、左特異ベクトルの ${\sigma }_i$ 倍になる。

$$A{v}_i={\sigma }_i{u}_i$$

つまり $v_i$ から $u_i$ へ、伸縮の倍率だけを伴って移る。転置のほうも同じ関係で、$A^{\top }{u}_i={\sigma }_i{v}_i$ が成り立つ。

$A^{\top }A$ の固有ベクトルとして $v_i$ を求めてから、この式で $u_i$ を作るのが手順である。

例：v から u を作る

先ほどの行列で試す。$A^{\top }A$ の固有ベクトルは $(1,1)/\sqrt{2}$ と $(1,-1)/\sqrt{2}$ である。

$v_1=(1,1)/\sqrt{2}$ に $A$ を掛けると $(4,0)/\sqrt{2}$、つまり $(2\sqrt{2},0)$ になる。長さが ${\sigma }_1$ なので、$u_1=(1,0)$ である。

同じように $A{v}_2=(0,-\sqrt{2})$ となり、$u_2=(0,-1)$ が得られる。分解は次の形にまとまる。

$$U=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right),V=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$$

単位円は楕円に写る

分解の 3 段階を図形で追うと、意味がはっきりする。$V^{\top }$ が座標軸を回し、$\Sigma$ が軸方向に伸ばし、$U$ がもう一度回す。

<svg viewBox="0 0 460 180" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<circle cx="70" cy="95" r="38" fill="#1b81e0" fill-opacity="0.08" stroke="#1b81e0" stroke-width="1.5"></circle>
	<text x="70" y="30" font-size="11" fill="#1f1f1f" text-anchor="middle">単位円</text>
	<line x1="122" y1="95" x2="152" y2="95" stroke="#9a9a9a" stroke-width="1"></line>
	<polygon points="157,95 148,91 148,99" fill="#9a9a9a"></polygon>
	<text x="139" y="86" font-size="10" fill="#9a9a9a" text-anchor="middle">Σ</text>
	<ellipse cx="230" cy="95" rx="62" ry="26" fill="#1b81e0" fill-opacity="0.08" stroke="#1b81e0" stroke-width="1.5"></ellipse>
	<text x="230" y="30" font-size="11" fill="#1f1f1f" text-anchor="middle">軸方向に伸縮</text>
	<line x1="302" y1="95" x2="332" y2="95" stroke="#9a9a9a" stroke-width="1"></line>
	<polygon points="337,95 328,91 328,99" fill="#9a9a9a"></polygon>
	<text x="319" y="86" font-size="10" fill="#9a9a9a" text-anchor="middle">U</text>
	<ellipse cx="395" cy="95" rx="62" ry="26" fill="#1b81e0" fill-opacity="0.08" stroke="#1b81e0" stroke-width="1.5" transform="rotate(-35 395 95)"></ellipse>
	<text x="395" y="30" font-size="11" fill="#1f1f1f" text-anchor="middle">回して置き直す</text>
	<text x="230" y="166" font-size="11" fill="#9a9a9a" text-anchor="middle">半軸の長さがそのまま特異値になる</text>
</svg>

できあがる楕円の半軸の長さが、特異値そのものである。いちばん伸びる向きが ${\sigma }_1$、いちばん縮む向きが最小の特異値にあたる。

行列を掛ける操作が、向きの取り替えと軸方向の伸縮に分かれている。ゆがみに見えるものが、この 3 つの組み合わせで説明できる。

例：楕円の半軸を読む

例の行列で単位円を送ると、半軸が $2\sqrt{2}$ と $\sqrt{2}$ の楕円になる。長いほうの向きが $u_1=(1,0)$、短いほうが $u_2=(0,-1)$ である。

面積の比も計算できる。もとの円の面積に ${\sigma }_1{\sigma }_2=4$ を掛けたものが、楕円の面積になる。

この 4 は行列式の絶対値と同じである。行列式が面積の拡大率を表すことと、特異値の積が一致する。

階数は零でない特異値の個数

特異値のうち 0 でないものの個数が、そのまま階数になる。$\Sigma$ の対角に残る成分の数を数えればよい。

伸縮の倍率が 0 の向きは、写した先でつぶれてしまう向きである。つぶれずに残る向きの本数が階数だと読める。

数値計算では、小さすぎる特異値を 0 と見なして階数を判定する。丸め誤差で完全な 0 にならないためで、どこで切るかは扱う問題による。

例：階数が落ちる行列を分解する

$$A=\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right)$$

第 2 行は第 1 行の 2 倍なので、階数は 1 である。$A^{\top }A$ は $(5,10;10,20)$ で、固有値は 25 と 0 になる。

特異値は 5 と 0 で、0 でないものは 1 つだけである。個数が階数と一致している。

$v_1=(1,2)/\sqrt{5}$ を取ると $A{v}_1$ の長さが 5 になり、$u_1$ も同じ向きになる。分解は 1 項だけで書ける。

縮小版と階数 1 の和

零の特異値に対応する列は、掛けても何も生まない。そこを削った形を縮小版という。

さらに項ごとに分けると、階数 1 の行列の和になる。

$$A={\sigma }_1{u}_1{v}_1^{\top }+{\sigma }_2{u}_2{v}_2^{\top }+\cdots +{\sigma }_r{u}_r{v}_r^{\top }$$

$r$ は階数である。それぞれの項は「$v_i$ の向きを見て $u_i$ の向きへ出す」という単純な行列で、重みが特異値になっている。

<svg viewBox="0 0 460 170" width="100%" style="max-width:460px;display:block;margin:0 auto">
	<text x="230" y="22" font-size="11" fill="#9a9a9a" text-anchor="middle">縦長の行列を分解したときの大きさ</text>
	<rect x="40" y="45" width="40" height="90" fill="#1b81e0" fill-opacity="0.10" stroke="#1b81e0" stroke-width="1"></rect>
	<text x="60" y="94" font-size="11" fill="#1b81e0" text-anchor="middle">A</text>
	<text x="60" y="152" font-size="10" fill="#9a9a9a" text-anchor="middle">m × n</text>
	<text x="96" y="94" font-size="12" fill="#9a9a9a">=</text>
	<rect x="120" y="45" width="90" height="90" fill="#1b81e0" fill-opacity="0.10" stroke="#1b81e0" stroke-width="1"></rect>
	<text x="165" y="94" font-size="11" fill="#1b81e0" text-anchor="middle">U</text>
	<text x="165" y="152" font-size="10" fill="#9a9a9a" text-anchor="middle">m × m</text>
	<rect x="222" y="45" width="40" height="90" fill="#1b81e0" fill-opacity="0.10" stroke="#1b81e0" stroke-width="1"></rect>
	<line x1="222" y1="45" x2="262" y2="85" stroke="#1b81e0" stroke-width="1"></line>
	<text x="242" y="110" font-size="11" fill="#1b81e0" text-anchor="middle">Σ</text>
	<text x="242" y="152" font-size="10" fill="#9a9a9a" text-anchor="middle">m × n</text>
	<rect x="274" y="45" width="40" height="40" fill="#1b81e0" fill-opacity="0.10" stroke="#1b81e0" stroke-width="1"></rect>
	<text x="294" y="70" font-size="11" fill="#1b81e0" text-anchor="middle">V</text>
	<text x="294" y="102" font-size="10" fill="#9a9a9a" text-anchor="middle">n × n</text>
	<text x="360" y="70" font-size="10" fill="#9a9a9a">対角の下は 0 なので</text>
	<text x="360" y="88" font-size="10" fill="#9a9a9a">U の右側は使われない</text>
</svg>

例：階数 1 の和に開く

例の行列を 2 つの項に分ける。${\sigma }_1{u}_1{v}_1^{\top }$ を計算すると、第 1 行だけが残る行列になる。

$$2\sqrt{2}\left(\begin{array}{c}1\\ 0\end{array}\right)\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\end{array}\right)=\left(\begin{array}{cc}2& 2\\ 0& 0\end{array}\right)$$

第 2 項も同じように計算すると $(0,0;-1,1)$ になる。2 つを足すと、もとの $A$ に戻る。

正方でない行列でも取れる

行と列の数が違っても、手順は変わらない。$A^{\top }A$ は $n$ 次の対称行列なので、右特異ベクトルはそこから求まる。

左特異ベクトルは $A{v}_i$ を正規化して得る。特異値が 0 の向きでは $A{v}_i$ が零ベクトルになるので、そこは別に補う。

対角化ができない場面でも使えることが、この分解の強みである。固有値が定義できない縦長の行列にも、特異値なら定義できる。

例：縦長の行列を分解する

$$A=\left(\begin{array}{cc}1& 0\\ 0& 1\\ 1& 0\end{array}\right)$$

$A^{\top }A$ は 2 次の行列で、計算すると $(2,0;0,1)$ になる。固有値は 2 と 1 である。

特異値は $\sqrt{2}$ と 1 で、どちらも 0 でないので階数は 2 である。3 行あっても、独立な向きは 2 つしかない。

第 1 列と第 3 列が同じ向きなので、その分が $\sqrt{2}$ という長さに表れている。

対称行列では固有値の絶対値になる

対称行列なら、特異値は固有値の絶対値に一致する。スペクトル分解で $A=Q\Lambda Q^{\top }$ と書けるので、負の固有値の符号を $U$ 側へ移せばよい。

正定値行列に限れば、特異値と固有値はそのまま同じものになる。符号を移す必要がないからである。

一般の行列では、特異値と固有値の間にこうした簡単な関係はない。特異値のほうが計算に強く、数値的にも安定している。

例：固有値が負の行列で確かめる

$$A=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$$

対称行列で、固有値は 3 と $-1$ である。特異値はその絶対値を取って 3 と 1 になる。

$A^{\top }A$ を計算しても確かめられる。$(5,4;4,5)$ の固有値は 9 と 1 で、平方根が 3 と 1 である。

符号の違いは $U$ に吸収される。特異値の側には現れない。

低ランク近似が最良になる

大きい特異値の項から順に $k$ 個だけ残すと、階数 $k$ の行列ができる。この行列が、階数 $k$ の中でもっともよい近似になる。

エッカート・ヤングの定理と呼ばれ、作用素ノルムでもフロベニウスノルムでも最良である。誤差の大きさまで分かる。

$$\Vert A-A_k{\Vert }_2={\sigma }_{k+1},\Vert A-A_k{\Vert }_F=\sqrt{{\sigma }_{k+1}^2+\cdots +{\sigma }_r^2}$$

落とした特異値がそのまま誤差になる。どこで切るかを、特異値の大きさを見て決められる。

例：項を落として誤差を測る

例の行列で第 2 項を落とすと、階数 1 の行列 $(2,2;0,0)$ が残る。もとの行列との差は $(0,0;-1,1)$ である。

この差の作用素ノルムは $\sqrt{2}$ で、落とした特異値 ${\sigma }_2$ と一致する。定理の主張どおりになっている。

${\sigma }_1$ が ${\sigma }_2$ の 2 倍あるので、1 項だけでもおおよその形は残る。特異値の差が大きいほど、少ない項でよく近似できる。

ノルムと条件数へのつながり

作用素ノルムは最大の特異値に等しい。行列がベクトルをいちばん引き伸ばす倍率が、そのまま ${\sigma }_1$ だからである。

フロベニウスノルムは、特異値の 2 乗和の平方根になる。成分の 2 乗和として計算しても同じ値になる。

条件数は最大と最小の特異値の比である。この値が大きいほど、連立方程式の解が誤差に敏感になる。くわしくは行列のノルムの記事で扱う。

応用

画像の圧縮では、画素の並びを行列と見て特異値分解する。大きい特異値の項だけを残せば、少ないデータで元の画像に近いものが作れる。

主成分分析でも同じ考え方を使う。データを並べた行列を分解し、大きい特異値の向きを主成分として取り出す。

検索や推薦の分野でも、大きな疎行列を低い階数で近似する手法として使われる。

他の話題とのつながり

疑似逆行列は、この分解から作れる。$\Sigma$ の零でない対角成分を逆数に取り替えるだけで、最小二乗解を与える行列が得られる。

対称行列に限れば、スペクトル分解と同じ内容になる。両側の直交行列が一致する場合が、そちらにあたる。

$QR$ 分解や $LU$ 分解と比べると、特異値分解は計算量が大きい。そのぶん階数や近似の情報まで取り出せる。

よくある誤り

参考文献