特異値分解 | 制御系CAD

特異値分解(Singular-Value Decomposition)

● $A$ をサイズ $m\times n$ の行列( ${\rm rank}\,A=k$ )とします。このとき、サイズ $m\times m$ の直交行列 $U$ とサイズ $n\times n$ の直交行列 $V$ が存在して

$\displaystyle{(1)\quad A=U\Sigma V^T }$

が成り立ちます。ここで、サイズ $m\times n$ の行列 $\Sigma$ は次を満たします。

$\displaystyle{(2.1)\quad \Sigma= \left[\begin{array}{cc} \Sigma_1(k\times k) & 0\,(k\times n-k)\\ 0\,(m-k\times k) & 0\,(m-k\times n-k) \end{array}\right] }$

$\displaystyle{(2.2)\quad \Sigma_1={\rm diag}\{\sigma_1,\cdots,\sigma_k\}\quad(\sigma_1\ge\cdots\ge\sigma_k>0) }$

● $A^TA\ge 0$ だから、仮定 ${\rm rank}\,A=k$ より、 $A^TA$ は $k$ 個の正固有値と $n-k$ 個の零固有値をもち、互いに直交する固有ベクトルをもちます。そこで、 $A^TA$ の固有値の正の平方根を、大きい順に、 $\sigma_1\ge\cdots\ge\sigma_k>\sigma_{k+1}=\cdots=\sigma_{n}=0$ のように表し、対応する固有ベクトル $v_1,\cdots,v_n$ を $v_i^Tv_i=1\ (i=j),\ 0\ (i\ne j)$ を満足するようにとることができます。いま、 $\Sigma_1$ を上のように、また

$\displaystyle{(3)\quad V= [\begin{array}{cc} V_1 & V_2 \end{array}] = [\begin{array}{ccc|ccc} v_1 & \cdots & v_k & v_{k+1}& \cdots & v_n \end{array}] }$

とおくと、 $V$ は直交行列となり、つぎが成り立ちます。

$\displaystyle{(4)\quad \begin{array}{l} A^TAV_1=V_1\Sigma_1^2\\ A^TAV_2=0 \end{array} }$

第2式の左から、 $V_2^T$ をかけて

$\displaystyle{(5)\quad V_2^TA^TAV_2=0\Rightarrow AV_2=0 }$

また、 $U_1=AV_1\Sigma_1^{-1}$ とおくと、第1式から $U_1^TU_1=I_{k}$ を得ます。そこで、 $U_2$ を $U= [\begin{array}{cc} U_1 & U_2 \end{array}]$ が直交行列となるように選ぶと

$\displaystyle{(6)\quad U^TAV= \left[\begin{array}{cc} U_1^TAV_1 & U_1^TAV_2\\ U_2^TAV_1 & U_2^TAV_2 \end{array}\right] = \left[\begin{array}{cc} \Sigma_1 & 0\\ U_2^TU_1\Sigma_1 & 0 \end{array}\right] =\Sigma }$

が成り立ちます。

●行列 $A= \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \end{array}\right]$ の特異値分解は

$\displaystyle{(7)\quad A= \underbrace{ \left[\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right] }_{U} \underbrace{ \left[\begin{array}{ccc} \sqrt{2} & 0 & 0 \\ 0 & 1 & 0 \end{array}\right] }_{\Sigma} \underbrace{ \left[\begin{array}{ccc} 0 & 1 & 0 \\ \frac{1}{\sqrt{2}} & 0 & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & 0 & \frac{1}{\sqrt{2}} \end{array}\right]^T }_{V^T} }$

のように与えられることを確かめます。

● $A^TA$ のサイズは $3\times 3$ ですが、 $AA^T$ のサイズは $2\times 2$ であるので、 $AA^T$ を計算すると $\left[\begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array}\right]$ となります（サイズ $m\times n$ の行列 $A$ の特異値を手計算で求めるには、 $A^TA$ と $AA^T$ のが同じ非零固有値をもつことから、サイズの小さいほうの固有値計算を行えばよい）。これから、 $AA^T$ の固有値は $1,2$ で、その正の平方根 $1,\sqrt{2}$ が特異値で、上の $\Sigma_1$ の対角成分の特異値は大きい順に並べる約束ですから

$\displaystyle{(8)\quad \underbrace{ \left[\begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array}\right] }_{AA^T} \underbrace{ \left[\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right] }_{U} = \underbrace{ \left[\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right] }_{U} \underbrace{ \left[\begin{array}{cc} 2 & 0 \\ 0 & 1 \end{array}\right] }_{\Sigma_1^2} }$

のように、 $U$ と $\Sigma_1$ が決まります。つぎに、 $V$ については、視察によって

$\displaystyle{(9)\quad \underbrace{ \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 1 \end{array}\right] }_{A^TA} \underbrace{ \left[\begin{array}{ccc} 0 & 1 & 0 \\ x & 0 & -y \\ y & 0 & x \end{array}\right] }_{V} = \underbrace{ \left[\begin{array}{ccc} 0 & 1 & 0 \\ x & 0 & -y \\ y & 0 & x \end{array}\right] }_{V} \underbrace{ \left[\begin{array}{ccc} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{array}\right] }_{{\rm diag}\{\Sigma_1^2,0\}} }$

とします。ここで、 $\left[\begin{array}{ccc}x \\y \end{array}\right]$ と $\left[\begin{array}{ccc}-y \\x \end{array}\right]$ が直交しており、 $x^2+y^2=1$ の制約があります。上式から $x=y$ が出て、 $x=y=\frac{1}{\sqrt{2}}$ と定まります。

行列のノルム

● $x\in{\rm\bf R}^n$ から $y\in{\rm\bf R}^m$ への写像 $y=Ax$ の「伝達特性」をどう測るかを考えます。これはスカラの場合は正比例の関係 $y=ax$ ですから、比例定数 $a$ に相当する量を求める話になります。

サイズ $m\times n$ の行列 $A$ の次の特異値分解を考えます。

$\displaystyle{(1)\quad \begin{array}{l} A= \underbrace{ \left[\begin{array}{cc} U_1 & U_2 \end{array}\right] }_{U(m\times m)} \underbrace{ \left[\begin{array}{cc} {\rm diag}\{\sigma_1,\cdots,\sigma_k\} & 0_{k\times (n-k)} \\ 0_{(m-k)\times k} & 0_{(m-k)\times (n-k)} \end{array}\right] }_{\Sigma= \left[\begin{array}{cc} \Sigma_1 & 0 \\ 0 & 0 \end{array}\right] \quad(\sigma_1\ge\cdots\ge\sigma_k) } \underbrace{ \left[\begin{array}{cc} V_1^T \\ V_2^T \end{array}\right] }_{V(n\times n)^T}\\ =U_1(m\times k)\Sigma_1(k\times k)V_1(n\times k)^T \end{array} }$

ここで、 $k={\rm rank}A$ で、 $U$ と $V$ は直交行列です。

$\displaystyle{(2)\quad UU^T=U^TU=I_m,\quad VV^T=V^TV=I_n }$

したがって、次のような３つの線形写像に分解されます。

● $n$ 次元ベクトル $x\in{\rm\bf R}^n$ のノルムとして、次の３通りが知られています。

$\displaystyle{(3)\quad \left\{\begin{array}{lll} ||x||_1=|x_1|+\cdots+|x_n|&\\ ||x||_2=\sqrt{x_1^2+\cdots+x_n^2}&\Rightarrow&||x||_2^2=x^Tx\\ ||x||_\infty=\max\{|x_1|,\cdots,|x_n|\}& \end{array}\right. }$

以下では、ベクトルのノルムとして、２番目の２ノルムを考えます。

このとき、次が成り立ちます。

$\displaystyle{(4)\quad ||x'||_2^2=||Vx||_2^2=x^TV^TVx=x^Tx=||x||_2^2\ \Rightarrow\ \frac{||x'||_2}{||x||_2}=1 }$

$\displaystyle{(5)\quad \begin{array}{l} ||y'||_2^2=||\Sigma x'||_2^2=\sigma_1^2x_1'\,^2+\cdots+\sigma_k^2x_k'\,^2+0x_{n+1}'\,^2+\cdots+0x_n'\,^2\\ \le \sigma_1^2(x_1'\,^2+\cdots+x_n'\,^2)=\sigma_1^2x'\,^Tx'=\sigma_1^2||x'||_2^2 \ \Rightarrow\ \frac{||y'||_2}{||x'||_2}\le\sigma_1 \end{array} }$

$\displaystyle{(6)\quad ||y||_2^2=||Uy'||_2^2=y'\,^TU^TUy'=y'\,^Ty'=||y'||_2^2\ \Rightarrow\ \frac{||y||_2}{||y'||_2}=1 }$

すなわち

$\displaystyle{(7)\quad \frac{||x'||_2}{||x||_2}\times\frac{||y'||_2}{||x'||_2}\times\frac{||y||_2}{||y'||_2}\le\sigma_1 \ \Rightarrow\ \frac{||y||_2}{||x||_2}=\frac{||Ax||_2}{||x||_2}\le\sigma_1 }$

したがって、線形写像 $y=Ax$ の伝達特性は、行列 $A$ の２ノルム

$\displaystyle{(8)\quad ||A||_2=\max_{x\ne 0}\frac{||Ax||_2}{||x||_2}=\sigma_1(A) }$

すなわち行列 $A$ の最大特異値 $\sigma_1(A)$ （行列 $A^TA$ または $AA^T$ の最大固有値の正の平方根）によって表されます。

●行列のノルムについて次式が成り立ちます。

$\displaystyle{(9)\quad \begin{array}{l} ||A+B||\le ||A||+||B||\\ ||AB||\le ||A|| ||B|| \end{array}　 }$

(8)より

$\displaystyle{(10)\quad \frac{||Ax||}{||x||} \le ||A||\ \Rightarrow\ ||Ax|| \le ||A||||x|| }$

に注意して

$\displaystyle{(11)\quad \begin{array}{l} ||(A+B)x||=||Ax||+||Bx||\ \le (||A||+||B||)||x||\\ \Rightarrow\ ||(A+B)|| \le ||A||+||B||\\ ||ABx||\le ||A||||Bx||\ \le ||A||||B||||x||\ \Rightarrow\ ||AB|| \le ||A||||B|| \end{array} }$

●一方、ベクトルの２ノルムについて次式が成り立ちます。

$\displaystyle{(12)\quad \begin{array}{l} ||a+b||\le ||a||+||b||\\ |a^Tb|\le ||a|| ||b|| \end{array}　 }$

これらは(9)の特別な場合と考えられますが、ここでは直接導出してみます。

いま、 $x$ に関する２次方程式

$(13)\quad \begin{array}{l} \displaystyle{\sum_{i=1}^n(a_ix-b_i)^2=\sum_{i=1}^n(a_i^2x^2-2a_ib_ix+b_i^2)}\\ \displaystyle{=(\sum_{i=1}^na_i^2)x^2-2(\sum_{i=1}^na_ib_i)x+(\sum_{i=1}^nb_i^2)=0} \end{array}$

を考えると、この実数解は１個または０個となることから、この判別式は零または負でなければならないので

$\displaystyle{(14)\quad D=\underbrace{(\sum_{i=1}^na_ib_i)^2}_{(a^Tb)^2}-\underbrace{(\sum_{i=1}^na_i^2)}_{a^Ta}\underbrace{(\sum_{i=1}^nb_i^2)}_{b^Tb}\le 0 }$

より

$\displaystyle{(15)\quad (a^Tb)^2 \le a^Ta b^Tb \Leftrightarrow |a^Tb|\le||a||||b|| }$

すなわち(12)の第２式が得られます。また、第１式は、次式から得られます。

$\displaystyle{(16)\quad \begin{array}{l} (\sqrt{a^Ta}+\sqrt{b^Tb})^2-(a+b)^T(a+b)\\ =a^Ta+2\sqrt{a^Ta}\sqrt{b^Tb}+b^Tb-(a^Ta+2a^Tb+b^Tb)\\ =2(\sqrt{a^Ta}\sqrt{b^Tb}-a^Tb) \ge 2(|a^Tb|-a^Tb) >0 \end{array}　 }$

●ちなみに、行列のフロベニウスノルムは

$\displaystyle{(17)\quad ||A||_F^2={\rm tr}A^TA=\sum_{i=1}^m\sum_{j=1}^n a_{ij}^2 }$

で定義されます。これは

$\displaystyle{(18)\quad ||A||_F^2={\rm tr}V\Sigma U^TU\Sigma V^T=\sum_{i=1}^{\min\{n,m\}}\sigma_{i}^2 }$

と表せるので、次式が成り立ちます。

$\displaystyle{(19)\quad \underbrace{\sigma_1^2}_{||A||^2} \le \underbrace{\sum_{i=1}^{\min\{n,m\}}\sigma_{i}^2}_{||A||_F^2} \le \min\{n,m\}\underbrace{\sigma_1^2}_{||A||^2}\ \Rightarrow\ ||A|| \le ||A||_F \le \sqrt{\min\{n,m\}}||A|| }$

行列積のフロベニウスノルムについても

$\displaystyle{(20)\quad \begin{array}{l} \displaystyle{||AB||_F^2=\sum_{j=1}^{n}\sum_{i=1}^{m}(\sum_{k=1}^{\ell}a_{ik}b_{kj})^2} \displaystyle{\le \sum_{j=1}^{n}\sum_{i=1}^{m} (\sum_{k=1}^{\ell}a^2_{ik}\sum_{k=1}^{\ell}b_{kj}^2)}\\ \displaystyle{=(\sum_{i=1}^{m}\sum_{k=1}^{\ell}a^2_{ik}) (\sum_{k=1}^{\ell}\sum_{j=1}^{n}b_{kj}^2)} \displaystyle{=||A||_F^2||B||_F^2} \end{array}　 }$

が成り立ちます。

連立１次方程式

次の線形方程式（連立１次方程式）を考えます。

$\displaystyle{(1)\quad Ax=b\quad(A\in{\bf R}^{n\times m}, x\in\bf R}^m, b\in\bf R}^n) }$

ここで、 $A$ はフルランク（ ${\rm rank}A=\min\{n,m\}$ ）とします。

$1^\circ$ $n\le m$ の場合（未知数の数が方程式の数より大きい場合）、(1)はunder-determined（劣決定）と呼ばれ、 $A$ の特異値分解を代入して次のように書けます。

$\displaystyle{(2)\quad \begin{array}{l} \underbrace{U\left[\begin{array}{cc} \Sigma_1 & 0_{n\times m-n} \end{array}\right] \left[\begin{array}{c} V_1^H\\ V_2^H \end{array}\right]}_{A}x =U\Sigma_1V_1^Hx=b\\ \Sigma_1={\rm diag}\{\sigma_1,\cdots,\sigma_n\} \end{array} }$

(2)の解候補として

$\displaystyle{(3)\quad x=V_1\Sigma_1^{-1} U^Hb+V_2c\quad(c\in{\bf R}^{n\times m-n}) }$

を考えます。 $V_1^HV_2=0_{n\times m-n}$ より第１項と第２項は直交することから

$\displaystyle{(4)\quad ||x||^2=||V_1\Sigma_1^{-1} U^Hb||^2+||V_2c||^2 }$

(3)において $c=0$ として得られる $x=V_1\Sigma_1^\dagger U^Hb$ は、 $||x||$ を最小化する最小ノルム解と呼ばれます。

$2^\circ$ $n\ge m$ の場合（未知数の数が方程式の数より小さい場合）、(1)はover-determined（過決定）と呼ばれ、 $A$ の特異値分解を代入して次のように書けます。

$\displaystyle{(5)\quad \begin{array}{l} \underbrace{\left[\begin{array}{cc} U_1 & U_2 \end{array}\right] \left[\begin{array}{cc} \Sigma_1 \\ 0_{n-m\times m} \end{array}\right]V^H}_{A}x =U_1\Sigma_1V^Hx=b\\ \Sigma_1={\rm diag}\{\sigma_1,\cdots,\sigma_m\} \end{array} }$

(5)の解候補として

$\displaystyle{(6)\quad x=V\Sigma_1^{-1} U_1^Hb }$

を考えます。 $b=(b-Ax)+Ax$ において、

$\displaystyle{(7)\quad \begin{array}{l} b=(b-Ax)+Ax\\ =(I-U_1\Sigma_1V^HV\Sigma_1^{-1} U_1^H)b+U_1\Sigma_1V^HV\Sigma_1^{-1} U_1^Hb\\ =U_2 U_2^Hb+U_1 U_1^Hb \end{array} }$

ここで、 $U_2^HU_1=0_{m\times n-m}$ より第１項と第２項は直交することから

$\displaystyle{(8)\quad ||b||^2=||b-Ax||^2+||Ax||^2 }$

(6)は $||b-Ax||^2$ を最小化する最小２乗解と呼ばれます。