nopu@wiki
nopu@wiki

特異値分解と一般化逆行列

次の一般化された固有値問題を解いていることになる。
\mathcal{V} \cong \mathbb{R}^n
\mathcal{U} \cong \mathbb{R}^m
A : \mathcal{V} \to \mathcal{U} \mbox{ linear}
として，
A \mathbf{v}_i = \sigma_i \mathbf{u}_i
ただし
\mathbf{v}_i \cdot \mathbf{v}_j = \mathbf{u}_i \cdot \mathbf{u}_j = \delta_{ij}
このとき，U := [ \mathbf{u}_1 \, \cdots \, \mathbf{u}_n ], V := [ \mathbf{v}_1 \, \cdots \, \mathbf{v}_m ], \Sigma := \mathrm{diag}(\sigma_1, \cdots, \sigma_r)
として，
A = U \Sigma V^*

実際，\mathbf{v}_i に作用させてみると，
A \mathbf{v}_i = U \Sigma \begin{bmatrix} \mathbf{v}_1^\mathrm{T} \\ \vdots \\ \mathbf{v}_n^\mathrm{T}\end{bmatrix} \mathbf{v}_i = U \Sigma \begin{bmatrix} 0 \\ \vdots \\ 1 \\ \vdots \\ 0\end{bmatrix} = U \begin{bmatrix} 0 \\ \vdots \\ \sigma_i \\ \vdots \\ 0\end{bmatrix} = \sigma_i \mathbf{u}_i

ここで，
V^* = V^{-1} は，\mathcal{V}の元をVを基底とした場合の成分ベクトルに対応付ける線形作用素である。
V^* \mathbf{v} = V^* \sum_{i=1}^n x_i \mathbf{v}_i = \sum_{i=1}^n x_i V^* \mathbf{v}_i = \begin{bmatrix} x_1 \\ \vdots \\ x_n\end{bmatrix}
したがって特に，
Vは，成分ベクトルから\mathcal{V}のベクトルを復元する作用素である。
（要するに線形同型V : \mathcal{V} \cong \mathbb{R}^n）

したがって，A = U \Sigma V^*とは，
\mathcal{V}の元を成分ベクトルに写し，
各成分をスカラー倍して，
\mathcal{U}の元として埋め込む作用素に他ならない。

目標
1. 一般の（正則あるいは正方ですらない）行列 A の標準形を作りたい。
2. 直交行列ないしユニタリ行列（つまり正規直交性を保つ座標変換）

アイデア
任意の行列Aに対し，A^* A の形は常に半正定エルミート行列
従って必ずユニタリ行列によって対角化することができて，しかもその固有値は正。

特異値分解 singular value decomposition
A : m×n行列
r = rank A
このとき，特異値と呼ばれるAに固有のr個の数字の組{σi}と，
m,n次ユニタリ行列 U,V があって，以下のように分解できる。
A = U \Sigma V^* \quad \Sigma := \mbox{diag } [\sigma_1, \cdots, \sigma_r, 0, \cdots, 0]
この分解をAの特異値分解という。
この分解による標準形に相当する m×n行列 Σ には特に名前はない。
具体的な理論計算にあたっては，特異値を大きい順に並べて，次のような外積表示も有用である。
A = \sum_{i=1}^r \sigma_i \mathbf{u} \mathbf{v}^* = \sum_{i=1}^r \sigma_i \mathbf{v} \otimes \mathbf{u}
ただし u_i, v_i はそれぞれU,Vの列ベクトルとする。

U,Vとして非正方行列を使う表示
U := [ u_1, \cdots, u_r ] \in \mathbb{R}^{m \times r} \mbox{ s.t. } U^* U = I
V := [ v_1, \cdots, v_r ] \in \mathbb{R}^{n \times r} \mbox{ s.t. } V^* V = I
\Sigma := \mbox{diag }[ \sigma_1, \cdots, \sigma_r ]
こうしておいて，次のように書いていることもある。
A = U \Sigma V^*

幾何学的な意味
xに作用させてみると，
A\mathbf{x} = \sum_{i=1}^r \sigma_i (\mathbf{v}_i^* \mathbf{x}) \mathbf{u}_i
つまり，xを正規直交基底Vで分解し，成分表示したものを，σでスケーリングして，Uに割り当てた（回転）という意味であることが分かる。
xのV-座標を単にx_iと書くことにすれば、
A \mathbf{x} = \sum_{i=1}^r \sigma_i x_i \mathbf{u}_i
となる。
和は元々Uの全ての基底ベクトル(m-dim)に対してとるが、固有値を昇順に並べているので、
ランクrより先の特異値は0となって、形式的に消えてしまったということである。
つまりランクrよりでかい添字のU,Vの列ベクトルは直交さえしていれば具体的にはどうでもいいことが分かる。
従ってAx自体はR^mの元をR^rの元と同一視していることに注意。
A \mathbf{x} \in \mathbb{R}^r \subset \mathbb{R}^m 

図式で理解
A \in \mathbb{R}^{m \times n} : \mathbb{R}^n \to \mathbb{R}^m 線形写像と同一視する。
各U,Vは次のような意味を持つ。
V : (\mathrm{Ker}A)^\bot \cong \mathbb{R}^r \to \mathbb{R}^n  回転
U : \mathrm{Im} A \cong \mathbb{R}^r \to \mathbb{R}^m 回転
\Sigma : \mathbb{R}^r \to \mathbb{R}^r スケーリング
従って，特異値分解はこれらの合成写像である。
A : \mathbb{R}^n \xrightarrow{V^*} \mathbb{R}^r \xrightarrow{\Sigma} \mathbb{R}^r \xrightarrow{U} \mathbb{R}^n 

作り方
1. A^* A を対角化する。 → n×nユニタリ行列Vがとれる。
   V^* A^* A V = \Lambda := \mbox{ diag }[\lambda_1, \cdots, \lambda_n]
   ただし r<i に対して固有値は0になり，それ以外は正値である。
   ユニタリ行列は存在すれば良いのであって，具体的な成分を求める必要はない。必要なのは固有値。
2. \sigma_i := \sqrt{\lambda_i} によって特異値が決まる。
   特異値を対角に並べた m×n行列 Σ が求めるもの。
   適当なm×mユニタリ行列Uが存在して，
   A = U \Sigma V^*
  とできる。

特異ベクトルもほしい
U,V の各列ベクトルはそれぞれ A A^*とA^* Aの単位固有ベクトルである。

例
\mathbf{a} \in \mathbb{R}^n \cong \mathrm{Mat}(n, 1, \mathbb{R})
\mathbf{a}^\mathrm{T} \mathbf{a} = a^2 より、特異値はaのノルムa := \| \mathbf{a} \|であることが分かる。
このとき、V := [ \ 1 \ ] \in \mathrm{Mat}(1,1,\mathbb{R}) として、
\mathbf{a}^\mathrm{T} \mathbf{a} = V [ \ a \ ] V^*
さらに、適当に U \in O(n, \mathbb{R}) をとって、
 \mathbf{a} = U \begin{bmatrix} a \\ 0 \\ \vdots \\ 0 \end{bmatrix} V^* とできる。
実際、以下のようにとることができる。
Uの成分で実際に生き残るのは Uの一列目だけだが、これはaの方向ベクトルになっていなければならない。
U = \begin{bmatrix} \frac{\mathbf{a}}{a} * \end{bmatrix}
残りの成分は、Uが直交行列になるようにとらなければならない。
aの直交補空間\mathbf{a}^\bot := \left( \mathrm{Span}\{ \mathbf{a} \} \right)^\botの正規直交基底S = \{ \mathbf{u}_1 \cdots \mathbf{u}_{n-1} \}をとって、
U = \begin{bmatrix} \frac{\mathbf{a}}{a} & \mathbf{u}_1 & \cdots & \mathbf{u}_{n-1}\end{bmatrix} とすれば、これは所望の行列である。

Rem. rankについて
以下が成り立つ。
\mbox{rank } A = \mbox{rank } A A^* = \mbox{rank } A^* A = \mbox{rank } \Sigma
正方でないので見かけの大きさはコロコロ変わるが，rank の方は不変であることに注目。

変換不変性
特異値は、
1. 相似変換 P^{-1}AP で不変
2. 同値変換 UAV で不変
3. 転置 A^\mathrm{T} で不変

Moore-Penrose型一般化逆行列 

一般化逆行列は，方程式の数に過不足がある連立方程式系において無理やり解を１つ決める変換である。
従って最小ノルム・最小誤差・反射などいくつかのアプローチがあるが，これらは一意でない。
一方，最小ノルム・最小誤差・反射のすべてを満たす一般化逆行列は Moore-Penrose型と呼ばれ，これはほぼ一意に定まる。

Def. Moore-Penrose型一般化逆行列
以下のすべてを満たす A^\dag のこと。
1. (AA^\dag)^\mathrm{T} = A A^\dag
2. (A^\dag A)^\mathrm{T} = A^\dag A
3.  A A^\dag A = A 
4.  A^\dag A A^\dag = A^\dag

作り方
Aの特異値分解 A = U \Sigma V^* に対して，次のような行列を用意する。
\Sigma^\dag := \mbox{ diag }[\frac{1}{\sigma_1}, \cdots, \frac{1}{\sigma_r}, 0, \cdots, 0]
ただし，Σとは逆に n×m行列にする。
これを用いて，Aの一般化逆行列は以下で与えられる。
A^\dag := V \Sigma^\dag U^* = \sum_{i=1}^r \frac{1}{\sigma_i} \mathbf{v} \mathbf{u}^*
このとき以下が成り立つ。
A^\dag A = V \Sigma^\dag U^* U \Sigma V^* = I_n
A A^\dag = U \Sigma V^* V \Sigma^\dag U^* = I_m

行列の近似 

フロベニウスノルム，最大特異値ノルムいずれの意味でも，
行列の特異値を小さい方から削ってr個だけ残したものは，
ランクrの行列による最適な近似である。
「特異値分解と一般化逆行列」をウィキ内検索
最終更新：2011年11月10日 18:47
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。