特異値分解

この記事では線形代数の基本定理とも言われるほど応用上非常に重要な特異値分解について解説します。今はやりのデータサイエンスでもかなり使われています。

対称行列のスペクトル分解
特異値分解
行列の作用素ノルム
行列の低ランク近似
参考文献

対称行列のスペクトル分解

特異値分解は対称行列のスペクトル分解に密接に関係しているので、まずは対称行列のスペクトル分解について説明します。

実数を成分に持つ正方行列 $A=(a_{ij})\in {\bf R}^{n\times n}$ が対称行列だとしましょう。すなわち、 $a_{ij}=a_{ji}$ です。このとき、\begin{align} Av_i = \lambda_i v_i \end{align} となる $\lambda_i\in {\bf R}$ と $0 \neq v_i\in {\bf R}^n$ が存在します。ただし、 $i=1, 2,\ldots, n$ です。よく知られているように、このような $\lambda_i$ を $A$ の固有値、 $v_i$ を $A$ の固有値 $\lambda_i$ に対応する固有ベクトルと呼びます。行列 $A$ が対称なので、固有ベクトルの集合 $\{ v_1,v_2,\ldots, v_n\}$ を ${\bf R}^n$ の正規直交基底とすることができます。いま、\begin{align} V &:= \begin{pmatrix} v_1 & v_2 & \cdots & v_n \end{pmatrix},\quad D:= {\rm diag} (\lambda_1,\lambda_2,\ldots, \lambda_n) \end{align} とすると、\begin{align} A = VDV^T\end{align} となります。右辺の $VDV^T$ を対称行列 $A$ のスペクトル分解と言います。より詳しくは、以下の記事を参照してください。

次に、 $A\in {\bf R}^{m\times n}$ で $m\neq n$ でも良い場合を考えてみましょう。正方でない、つまり $m\neq n$ の場合は、 $A$ の固有値や固有ベクトルを考えることができないので $A$ をスペクトル分解することができません。しかし、 $A^TA$ は ${\bf R}^{n\times n}$ に入っているので正方であり、しかも対称行列です。よって、 $A^TA$ のスペクトル分解を考えることができます。

対称行列 $A^TA$ のスペクトル分解を\begin{align} A^TA = VDV^T\end{align}としましょう。ただし、 $D$ は対角行列で対角成分に $A^TA$ の固有値 $\lambda_i$ が並び、 $V\in {\bf R}^{n\times n}$ の各列ベクトルは $A^TA$ の固有ベクトル $v_i$ からなる ${\bf R}^n$ の正規直交基底 $\{v_1, v_2,\ldots, v_n\}$ で構成されているとします。ただし、 $\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n$ とします。このとき、\begin{align} \langle Av_i, Av_j\rangle = \lambda_j \langle v_i, v_j \rangle = \begin{cases} \lambda_i\quad (i=j)\\ 0\quad\,\,\,\,\,\, (i\neq j) \end{cases} \end{align} となります。ただし、 $\langle \cdot, \cdot \rangle$ はユークリッド内積です。したがって、 $\{Av_1, Av_2,\ldots, Av_n\}$ は直交しており、ゼロでないベクトルは ${\rm Im}\,A\subset {\bf R}^m$ の基底を構成します。また、 $i=j$ とすると\begin{align} ||Av_i||^2 = \lambda_i \end{align} となるので $\lambda_i\geq 0$ が分かります。よって、 ${\rm rank}\,A=k$ だとすると、\begin{align} \lambda_i = 0\quad (k<i\leq n)\end{align} となります。したがって、\begin{align} u_i:= \frac{Av_i}{||Av_i||} = \frac{1}{\sqrt{\lambda_i}} Av_i\quad (1\leq i\leq k) \end{align} は ${\rm Im}\,A\subset {\bf R}^m$ の正規直交基底を構成します。もし、 $k＜m$ の場合は、この正規直交基底を ${\bf R}^m$ の正規直交基底へ延長することもできます。実際に、この正規直交基底をなすベクトル $u_1,u_2,\ldots,u_k$ に一次独立な $m-k$ 個のベクトルをもってきて次の記事で解説したグラム・シュミットの直交化法を利用することで ${\bf R}^m$ の正規直交基底 $\{u_1,u_2,\ldots,u_m\}$ を作ることができます。

以上より、\begin{align} Av_i &= \sigma_i u_i\quad (1\leq i\leq k)\\ Av_i &=0\quad\,\,\,\,\,\, (k<i\leq n) \end{align} となります。ただし、 $\sigma_i:= \sqrt{\lambda_i}$ です。このことより、 $\Sigma:= {\rm diag}(\sigma_1,\sigma_2,\ldots, \sigma_k,0,\ldots, 0)\in {\bf R}^{m\times n}$ を用いると（作り方から $\sigma_1\geq \sigma_2\geq \cdots \geq \sigma_k＞0$ であることに注意)、行列 $A$ は\begin{align} A=U\Sigma V^T \end{align} と分解できることが分かります。ただし、\begin{align} U:=\begin{pmatrix} u_1 & u_2 & \cdots & u_m \end{pmatrix}\end{align} で $\{u_1,u_2,\ldots, u_m\}$ は ${\bf R}^m$ の正規直交基底です。この $U\Sigma V^T$ を $A$ の特異値分解、 $\sigma_1, \sigma_2,\ldots, \sigma_k$ を $A$ の特異値、 $U$ の各列を左特異ベクトル、 $V$ の各列を右特異ベクトルと言います。特異値分解は、以下のように任意の行列による写像が回転や拡大の写像に分解できることを意味しています。

f:id:ogyahogya:20190819152422p:plain

また、特異値分解は\begin{align} A= \sum_{i=1}^k \sigma_i u_i v_i^T \end{align} というように、 ${\rm rank}\, A=k$ 個分だけランク1の行列を加算することを意味します。この表現を用いると、任意の $x=x_1v_1+x_2v_2+\cdots +x_nv_n\in {\bf R}^n$ に対して\begin{align} Ax = \sigma_1x_1u_1+\sigma_2x_2u_2+\cdots +\sigma_k x_k u_k \end{align}が成り立つことが分かります。特に、 $x_1=x_2=\cdots =x_n=1$ なら\begin{align} Ax = \sigma_1u_1+\sigma_2u_2+\cdots +\sigma_k u_k \end{align}となります。このことを $k=2$ の $A\in {\bf R}^{2\times 2}$ に対して可視化したのが上の図です。

行列の作用素ノルム

任意の $A\in {\bf R}^{m\times n}$ に対して\begin{align} ||A||:= \max_{x\in {\bf R}^n\backslash\{0\}} \frac{||Ax||}{||x||} = \max_{||x||=1} ||Ax|| \end{align}とすると $\|\cdot \|$ はノルムとなります。このノルムを作用素ノルムと言います。以下のように、行列 $A$ の作用素ノルムは最大特異値になります。

f:id:ogyahogya:20191229184335p:plain

f:id:ogyahogya:20191229184349p:plain

例えば、 $U^TU=I$ となる任意の $U\in {\bf R}^{s\times m}$ の作用素ノルムは $1$ になります。なぜなら、任意の $x\in {\bf R}^m$ に対して\begin{align} ||Ux||^2=x^TU^TUx=||x||^2 \end{align} が成り立つからです。また、サイズの異なる行列 $A\in {\bf R}^{m\times n},\, B\in {\bf R}^{n\times p}$ に対して\begin{align} ||AB||\leq ||A||\cdot ||B|| \end{align}が成り立ちます。なぜなら、任意の $x\in {\bf R}^n$ に対して\begin{align} ||ABx||\leq ||A||\cdot ||Bx||\leq ||A||\cdot ||B||\cdot ||x|| \end{align} が成り立つからです。さらに、以下が成り立ちます。

f:id:ogyahogya:20191229191417p:plain

証明は以下の通りです。

f:id:ogyahogya:20191229191436p:plain

行列の低ランク近似

与えられた行列 $A\in {\bf R}^{m\times n}$ の最適な近似が特異値分解を利用することで以下のように得られます。この結果はエッカート・ヤング(Eckart-Young)の定理と言われています。

f:id:ogyahogya:20200114120225p:plain

証明は以下の通りです。

f:id:ogyahogya:20191229192723p:plain

f:id:ogyahogya:20191229192733p:plain

f:id:ogyahogya:20191229192747p:plain

この定理は以下を意味します。

f:id:ogyahogya:20191230121939p:plain

この定理は行列 $A\in {\bf R}^{m\times n}$ のランクを $k$ だとしたときに、ランク $k-1$ 以下で $A$ に最も近い行列が $A$ 自身を特異値分解することで得られることを示しており、このことから特異値分解が応用上非常に重要だということになります。例えばデータサイエンスの文脈では、 $A$ はデータを格納した行列ということが多いですが、この $A$ のサイズが非常に大きい（ $m, n$ が非常に大きい）と情報処理が大変になります。このようなときに、 $A$ を特異値分解して、 $A$ に最も近い低ランクな行列を構成する特異値と特異ベクトルを抽出しておけば、データ処理が非常に簡単になります。