特異値分解

A Blog Entry on Bayesian Computation by an Applied Mathematician

$$

$$

1 特異値分解

命題（特異値分解）¹

任意の行列 $A\in M_{n,p}(\mathbb{R}),r:=\mathrm{rank}(A)$ について，直交行列 $U\in O_n(\mathbb{R}),V\in O_p(\mathbb{R})$ と非負実数 ${\sigma }_1\ge \cdots \ge {\sigma }_r>0$ が存在して，次が成り立つ： $$A=U\mathrm{\Sigma }{V}^{\mathrm{\top }},\mathrm{\Sigma }:=\left[\begin{array}{cc}D& O_{r,p-r}\\ O_{n-r,r}& O_{n-r,p-r}\end{array}\right],D:=\mathrm{diag}({\sigma }_1,\cdots ,{\sigma }_r).$$ $D$ を 特異値行列，の対角要素を 特異値 と呼ぶ．²

(Sylvester, 1889) は特異値を正準乗数 (canonical multipliers) と呼んでいた．Sylvester は特異値分解を独立に再発見した一人で，歴史上最初の特異値分解は (Beltrami, 1873) が与えたものだとされている．より詳しい歴史については (Stewart, 1993) 参照．

証明

1. まず $v_1,\cdots ,v_r\in {\mathbb{R}}^n$ を，$A^{\mathrm{\top }}A$ の固有ベクトルからなる正規直交系として取る． このとき $v_1,\cdots ,v_r$ は $\mathrm{Im}(A^{\mathrm{\top }})$ の像の基底である． $v_1,\cdots ,v_r$ が $A^{\mathrm{\top }}A$ の固有ベクトルであることが必要であることは， $$A^{\mathrm{\top }}A=(U\mathrm{\Sigma }{V}^{\mathrm{\top }}{)}^{\mathrm{\top }}(U\mathrm{\Sigma }{V}^{\mathrm{\top }})=V{\mathrm{\Sigma }}^{\mathrm{\top }}{U}^{\mathrm{\top }}U\mathrm{\Sigma }{V}^{\mathrm{\top }}=V({\mathrm{\Sigma }}^{\mathrm{\top }}\mathrm{\Sigma })V$$ となることからわかり，${\sigma }_1^2,\cdots ,{\sigma }_r^2$ が $A^{\mathrm{\top }}A$ の固有値である． （従って $A{A}^{\mathrm{\top }}$ の固有値でもある）．

2. 続いて，条件 $A{v}_i={\sigma }_i{u}_i(i\in [r])$ によって，$u_1,\cdots ,u_r$ を定める．するとこれらは直交し， $\mathrm{Im}(A)$ の基底をなす．さらに，$A{A}^{\mathrm{\top }}$ の固有ベクトルでもある．

   このことは次のように示せる：

   $$\begin{array}{rl}{u}_i^{\mathrm{\top }}{u}_j& ={\left(\frac{A{v}_i}{{\sigma }_i}\right)}^{\mathrm{\top }}\left(\frac{A{v}_j}{{\sigma }_j}\right)=\frac{v_i^{\mathrm{\top }}{A}^{\mathrm{\top }}A{v}_j}{{\sigma }_i{\sigma }_j}=\frac{{\sigma }_j^2}{{\sigma }_i{\sigma }_j}{v}_i^{\mathrm{\top }}{v}_j=0,i\ne j.\end{array}$$

   $⟨u_1,\cdots ,u_r⟩\subset \mathrm{Im}(A)$ であることと，正規直交することから線型独立でもあり，これらが $\mathrm{Im}(A)$ の基底であることがわかる． さらに，任意の $i\in [r]$ について， $$A{A}^{\mathrm{\top }}{u}_i=\frac{A{A}^{\mathrm{\top }}A{u}_i}{{\sigma }_i}={\sigma }_{i}A{v}_i={\sigma }_i^2{u}_i,i\in [r].$$ なお，$A{v}_i={\sigma }_i{u}_i$ が必要であることは，$v_1,\cdots ,v_r$ の正規直交性から， $$A{v}_i=(u_1{\sigma }_1{v}_1^{\mathrm{\top }}+\cdots +u_r{\sigma }_r{v}_r^{\mathrm{\top }})v_i=u_i{\sigma }_i$$ からわかる．

3. $v_1,\cdots ,v_r$ の正規直交な延長であって，$v_{r+1},\cdots ,v_n$ が $\mathrm{Ker}(A)$ の基底になるもの，$u_1,\cdots ,u_r$ の正規直交な延長であって，$u_{r+1},\cdots ,u_m$ が $\mathrm{Ker}(A^{\mathrm{\top }})$ の基底になるものが取れる． これは，核と余像，像と余核が直交するためである． これについて，$A=U\mathrm{\Sigma }{V}^{\mathrm{\top }}$ が成り立つ．

系

以上の証明から，次のこともわかる：

1. $A$ の特異値は，$A^{\mathrm{\top }}A$ の固有値の正の平方根に等しい．
2. $V$ の列ベクトルは $A^{\mathrm{\top }}A$ の固有ベクトルであり，$U$ の列ベクトルは $A{A}^{\mathrm{\top }}$ の固有ベクトルになる．

2 低階数近似

$(n,p)$-行列の全体 $M_{n,p}(\mathbb{C})$ は Hilbert-Schmidt 内積 $$(B|A{)}_{\mathrm{HS}}:=\mathrm{Tr}(A^{\ast }B)=\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{b}_{ij}$$ に関して Hilbert 空間をなす．$M_{n,p}(\mathbb{R})$ はこの閉部分空間をなす．

命題 (Eckart and Young, 1936)

$A\in M_{n,p}(\mathbb{R})$ を行列，$0\le r\le n\vee p$ を自然数とする．ランク $r$ の行列 $\tilde{A}\in M_{n,p}(\mathbb{R})$ のうち，$A$ に最も近いものは $$\tilde{A}:=U{\mathrm{\Sigma }}_{1:r}{V}^{\mathrm{\top }}=\underset{\mathrm{rank}(\tilde{A})=r}{\mathrm{argmin}}\parallel A-\tilde{A}{\parallel }_{\mathrm{HS}}$$ が与える．ただし，${\mathrm{\Sigma }}_{1:r}=\mathrm{diag}({\sigma }_1,\cdots ,{\sigma }_r,0,\cdots ,0)$ とした．

またこのときの残差は，残った特異値のうち最大のもの $$\parallel A-\tilde{A}{\parallel }_{\mathrm{HS}}={\sigma }_{r+1}$$ が与える．³

3 一般化逆行列

命題 (Moore, 1920)-(Penrose, 1955)⁴

$A\in M_{mn}(\mathbb{R})$ について，次の３条件を満たす行列 $A^{+}\in M_{nm}(\mathbb{R})$ は一意的に定まる：

1. 反射型一般可逆行列：$A{A}^{+}A=A,A^{+}A{A}^{+}=A^{+}$
2. 最小ノルム型：$A^{+}A$ は自己共役である：$(A^{+}A{)}^{\mathrm{\top }}=A^{+}A$
3. 最小誤差型：$A{A}^{+}$ も自己共役である：$(A{A}^{+}{)}^{\mathrm{\top }}=A{A}^{+}$

これを Moore-Penrose の一般化逆行列 という．

任意の行列 $A\in M_{n,p}(\mathbb{R})$ の一般化逆行列は，直交行列 $V,U$ で座標変換を施したところで逆行列を取り，これを再び $V,U$ で変換し直したものに等しい：

命題（一般化逆の特徴付け）⁵

$A\in M_{n,p}(\mathbb{R})$ の一般化逆行列は次のように表せる： $$A^{+}=V{\mathrm{\Sigma }}^{-1}{U}^{\mathrm{\top }},{\mathrm{\Sigma }}^{-1}=\left[\begin{array}{cc}{D}^{-1}& O_{r,p-r}\\ O_{n-r,r}& O_{n-r,p-r}\end{array}\right].$$

関連ページ

References

Beltrami, E. (1873). Sulle funzioni bilineari. Giornale Di Matematiche Ad Uso Degli Studenti Delle Universita, 11, 98–106.

Eckart, C., and Young, G. (1936). The approximation of one matrix by another of lower rank. Psychometrika, 1(3), 211–218.

Moore, E. H. (1920). On the reciprocal of the general algebraic matrix. Bulletin of the American Mathematical Society, 26(9), 394–395.

Penrose, R. (1955). A generalized inverse for matrices. Mathematical Proceedings of the Cambridge Philosophical Society, 51(3), 406–413.

Stewart, G. W. (1993). On the early history of the singular value decomposition. SIAM Review, 35(4), 551–566.

Strang, G. (2016). Introduction to linear algebra. Wellesley-Cambridge Press.

Sylvester, J. J. (1889). On the reduction of a bilinear quantic of the $n$-th order to the form of a sum of $n$ products by a double orthogonal substitution. The Messenger of Mathematics, 18, 42–46.

柳井晴夫，竹内啓. (1983). 射影行列・一般逆行列・特異値分解,Vol. 10. 2018年に新装版が出版されている; 東京大学出版会.

Footnotes

1. (Eckart and Young, 1936, p. 213 Theorem 1), (Strang, 2016, p. 372) など．

2. (Eckart and Young, 1936, p. 214) によると，以前はにより正準乗数 (canonical multipliers) と呼ばれていた．

3. $r\ge \mathrm{rank}(A)$ であるとき，${\sigma }_{r+1}=0$ とする．(Strang, 2016, p. 394) も参照．

4. (柳井晴夫，竹内啓, 1983) も参照．

5. (柳井晴夫，竹内啓, 1983, p. 定理5.6), (Strang, 2016, p. 395) も参照．