読者です 読者をやめる 読者になる 読者になる

特異値分解

math

今回はこちらのスライドこちらのスライドこちらのスライドを参考(ほぼ和訳)して特異値分解について理解したいと思います。

Introduction
$n$ 次元ベクトルの解を求めたいときに、誤差を含んだデータ $m(m>n)$ 個から解を得たいときのことを考えます。 画像認識(カメラキャリブレーションなど)では、線形方程式に対して解を計算する際にいくつかの方法がありますが、誤差を含むデータから解を得るにはロバスト推定をしたり、今回説明するように二乗誤差を最小化するようなことを考えます。

Motivation
線形方程式 $Ax=b$ に構成されるシステムを考えます。
ここで、 $b$ が $b+ \delta b$ といった具合に誤差が乗っているとき、解 $x$ には $A^{-1} \delta b$ の誤差が乗っかります。
そこで、 $|| \delta b ||$ によってどのような誤差が発生するかを以下の観点考えたい。 ( $ b $ はベクトルなので、 $\delta b$ ももちろんベクトルです。)
1. $b$ がどの方向に行けば誤差が大きくなるのか
2. 条件数 $cond(A)(= ||A|| \cdot ||A^{-1}||)$ が大きいとき、どのようにして正確な解を得ればよいか
上記のような問題について考えるときは特異値分解(Singular Value Decomposition)が有効である。

直行行列(Orthogonal Matrix)
 m \times n行列 U U^{T} U=Iを満たすとき、 $U$ は直行行列である。 つまり、 $U$ の列ベクトルは互いに直行している。

行列で見る特異値分解
$m \times n$ 行列 $A(m>n)$ のとき

  1.  m \times n 直行行列 $U$
     Uの列成分は AA^{T}固有ベクトルである。
     AA^{T} = USV^{T}VSU^{T} = US^{2}U^{T}
  2.  n \times n 対角行列  S
       S=diag (\sigma_1, \sigma_2, \cdots, \sigma_{n})とする。    \sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_nのとき、 \sigma_1, \sigma_2, \cdots, \sigma_nを特異値と呼び、行列 A^{T}A固有値である。
  3. $n \times n$ 直行行列 $V$
     Vの列成分は A^{T}A固有ベクトルである。
     A^{T}A = VSU^{T}USDV^{T} = VS^{2}V^{T}

によって、
 A=USV^{T}
と分解することを $A$ を特異値分解するという。

 A= \sum_{j=0}^{n} \sigma_{j} u_{j} v_{j}^{T}

であるから、

 A v_{j} = \sigma_{j} u_{j}

となる。
この式の意味するところは、「 Vで張られる空間の基底 v_j Uで張られる空間の基底 u_jに射影される」ということである。
また、 \Lambda = S^{2}とすると、

 A A^{T}=U \Lambda U^{T}

であり、

 (A A^{T}) U = U \Lambda

 (A A^{T}) u_{j} = \lambda_{j} u_{j}

つまり、 Uの列成分は AA^{T}固有ベクトルであることが確認できる。
同様に

 A^{T} A=V \Lambda V^{T}

であり、

 (A^{T} A) V = V \Lambda

 (A^{T} A) v_{j} = \lambda_{j} v_{j}

つまり、  Vの列成分は A^{T}A固有ベクトルであることが確認できる。

固有値と特異値
一般に固有値と特異値は同じ値を取らない。
一般に、行列 Aに対して、 A^{H} Aはエルミート行列であり、非負の固有値を持つ。(ただし A^{H} Aのエルミート共役とする。)
特異値は A^{H} A固有値平方根である。

特異値分解による逆行列の計算
 n \times n行列 A A=USV^{T}特異値分解されるとき、正則である A逆行列
 A^{-1} = V (diag (\sigma_1^{-1}, \sigma_2^{-1}, \cdots, \sigma_n^{-1})) U^{T}
となる。
 \sigma_iがゼロに近いとき、丸め誤差が生じる。
ゼロに近い \sigma_iが多いほど、 Aは特異である(?)。  Aが特異であるまたは不良条件(ill-conditioned)であるとき、 A逆行列は、

 A^{-1} = V D^{-1}_{0} U^{T}

 D_{0}^{-1} = \left\{ \begin{array}{ll}
 1 / \sigma_i & (\sigma_i > t) \\
 0 & (otherwise) \end{array} \right.

ただし、 tは小さい閾値

The condition of a matrix
線形方程式 Ax=bにおいて
 bが微小変化したときに、解 xが比較的大きく変動するおき、不良条件(ill-conditioned)という。
最大特異値と最小特異値の比 \sigma_1 / \sigma_nが大きいほど、特異である。

ゼロ空間(null space)
核空間(kernel space)ともいう。
 n \times n行列 Aに対して、 Ax=0を満たすベクトル xの集合をゼロ空間(null space)という。

行列の値域(range)
行列 Aの値域(range)とは Ax=bの解 xが存在するベクトル bの集合のことである。
値域は線形ベクトル空間であり、次元は Aのランクと一致する。
つまり、ゼロでない特異値の数とランクが一致する。 もし Aが特異ならば、 Aのランクは nより小さい。
 n=Rank(A) + Nullity(A)

特異値分解と値域、ゼロ空間
特異値分解は値域とゼロ空間における直行基底を構成する。
 Aの非負の特異値に対応する、 Uの列ベクトルは、 Aの値域の正規直行基底である。
 Aのゼロの特異値に対応する、 Vの列ベクトルは、  Aのゼロ空間の直行基底を形成している。

線形方程式を特異値分解で解く
方程式 Ax=b(b \neq 0)であり、 b Aの値域に含まれるとき、 この連立方程式は解を持つ。
しかし、解が無数に存在することがある。(なぜならば、もし xが解で、 yがゼロ空間上のベクトルであるとき、 x+yも同様に解であるから。)
しかし、なんらかの値が必要になった場合、 ||x||^2が最も小さい解を解とする。
このとき解は
 x = V (diag (\sigma_1^{-1}, \sigma_2^{-1}, \cdots, \sigma_n^{-1})) (U^{T} b) = V S^{-1} U^{T} b
となる。ただし、 \sigma_{j}= 0のとき、 \sigma_j^{-1} = 0とする。

一方、 bが値域に含まれないとき、 Ax=bを満たすベクトル xは存在しなく、解は先ほどと同様に
 x = V (diag (\sigma_1^{-1}, \sigma_2^{-1}, \cdots, \sigma_n^{-1})) (U^{T} b) = V S^{-1} U^{T} b
で与えられる。
この解は ||Ax-b||が最小となるような解となっている。

なぜこれらのように bが値域に含まれても、含まれなくて同じように解が出せるかを証明する。
 bは値域に含まれるとき(つまり式の本数が足りないとき)
 Ax=bを拘束条件として、 ||x||を最小化させる。
ラグランジュの未定乗数法を用いて解く。

 L(x) = 1/2 ||x||^2 - (\lambda, Ax-b)

 \lambda = (\lambda_1, \lambda_2, \cdots, \lambda_m)

よって、

 x - A^{T} \lambda = 0

これによって、 Ax=b xに代入して、

 A A^{T} \lambda = b

これを解いて \lambdaを求めると、(つまり、 A A^{T}逆行列を持つことを前提としている)
次式を得る。

 x = A^T (A A^T)^{-1} b

次にこれが特異値分解による解と等しいことを示す。

 A A^{T} = U \Lambda U^{T}

これより

 A^{T} (A A^{T})^{-1} = V S U^{T} U \Lambda^{-1} U^{T}

 A^{T} (A A^{T})^{-1} = V S^{-1} U^{T}

となる。
次に、 bが値域に含まれないとき(つまり式の本数が多い時)

 1/2 ||Ax-b||^{2}

を最小化する。
これより、

 A^{T} A x - A^{T} b = 0

よって( A^{T} A逆行列を持つことを前提としている)

 x = (A^{T} A)^{-1} A^{T} b

となる。これが、特異値分解による解と等しいことを示す。

 (A^{T} A)^{-1} A^{T} = V \Lambda^{-1} V^{T} V S U^{T}
 A^{T} (A A^{T})^{-1} = V S^{-1} U^{T}

となる。

同次線形方程式を特異値分解で解く
同次線形方程式 Ax=0を考える。 これはゼロ空間上の任意のベクトルに等しい。
つまり、特異値がゼロに対応する Vの列ベクトルが作る空間が解となる。
(別の解釈?)←これが一番しっくりくる
最小ノルムとなる解 x=0は自明解。
そこで、 x=1という拘束条件を加える。
この拘束条件を満たす最適解を探索する問題に帰着。

  min_{||x||=1} ||Ax||^2

これをラグランジュの未定乗数法を使って解く。

 L(x) = x^{T} A^{T} A x  - \lambda (x^{T} x -1)

よって、

 A^{T} A x - \lambda x = 0

したがって、 \lambda A^{T} A固有値であり、そのときの固有ベクトル

 x= e_{\lambda}

とする。
ここで、 \lambda=0のとき L(e_{\lambda})を最小化できるので、 x=e_0が解となる。

(また別の解釈?)

 rank(A)=n-k (m \geq n-k, \sigma_{n-k+1}=\cdots=\sigma_n=0)

のとき、解は

 x=a_1 v_{n-k+1} + a_2 v_{n-k-1} + \cdots + a_k v_n

with

 a^{2}_{1} + a^{2}_{2} + \cdots + a^{2}_{k} = 1