本記事ではレイリー商について解説します。
はじめに
古典的なレイリー商は、対称行列の固有値を求めるアルゴリズムや、ゲーム理論のミニマックス原理を示すために使われます。
線型空間と内積さえ与えられていればレイリー商は一般的に定義できるので、色々な場面で登場します。
有名な例だと、ラプラシアン $\Delta$ の固有値問題の性質を調べるときに本質的な役割を果たします。
気になる方は、ラプラシアン 固有値問題 レイリー商などで検索してみてください。
今回は深いところには踏み込まず、古典的ないわゆる行列に付随するレイリー商についてのみ取り扱います。
レイリー商の定義
$n$ を2以上の自然数とし、$n \times n$ の 対称行列 $A$ と 0ではない $n$ 次元ベクトル $x \in \mathbb{R}^n$ に対して、レイリー商 $\mathcal{R}(A)$ を以下のように定めます。
$$
\mathcal{R}(A)=\frac{x^TAx}{x^Tx}
$$
レイリー商の意味
レイリー商の分子はいわゆる2次形式といわれるもので、$n$ 次元の2次の項からなる多項式を行列の形で表現したものです。2次形式については後から解説します。たとえば、$x_1^2 + 2x_1x_2 +x_2^2$、$3x_1^2+2x_1x_3+x_2x_3+x_3^2$ などは2次形式で表現することができます。
レイリー商の分母は ベクトル $x$ の長さなので、レイリー商は2次の多項式を $x$ について正規化したものと考えると良いでしょう。
2次形式
2次の項からなる多項式は対称行列を用いて行列の形、すなわち2次形式として表現できることを見てみましょう。先ほどの例をそのまま使います。
$x_1^2 + 2x_1x_2 +x_2^2$ の場合
A =\left(
\begin{matrix}
1 & 1 \\
1 & 1
\end{matrix}
\right)
$3x_1^2+2x_1x_3+x_2x_3+x_3^2$ の場合
A =\left(
\begin{matrix}
3 & 0 & 1 \\
0 & 0 & \frac{1}{2} \\
1 & \frac{1}{2} & 1
\end{matrix}
\right)
とすると、それぞれ $x^TAx$ を計算すると求める多項式となることが確認できます。
これは、天下り的に出てきたわけではなく、対角成分が２乗となっている項、非対角成分が $x_1x_3$ などのふたつの組となっている項の係数を表しています。
ここで、非対角成分が半分づつに分配されて対称行列となるように工夫している点に注意します。（たとえば、$2x_1x_2$ が $x_1x_2 + x_2x_1$ の和になっていると解釈する）
レイリー商の性質
レイリー商の定義がわかったところで、性質についてみてみましょう。
この記事のはじめに、レイリー商は固有値を求めるアルゴリズムに使われると書きましたが、固有値に大きく関係しています。
すなわち、レイリー商の最大値は行列 $A$ の最大固有値になり、レイリー商の最小値は最小固有値になります。
さらに、他の固有値についての情報も得られて、次のようにまとめることができます。
$A$ を対称行列とし、$x$ を0ではないn次元ベクトルとする。$A$ の固有値を重複もこめて $\lambda_1\leq\lambda_2 \leq \cdots\leq\lambda_n$ とする。また、対応する固有ベクトルを $\phi_1,\cdots,\phi_n$ とする。このとき、固有値 $\lambda_i(i=1,2,\cdots,n)$ は以下で求められる。
\lambda_i = \min_{x \perp\phi_1,\cdots\phi_n}\frac{x^TAx}{x^Tx}
そして、それを最小化する $x$ については,
\phi_i =arg\min_{x \perp\phi_1,\cdots\phi_n}\frac{x^TAx}{x^Tx}
となる。
称行列の固有値は全て実数なこと、異なる固有値に対応する固有ベクトルは互いに直交することに注意しておきます。
では、これを説明してみましょう。
簡単な解説
任意のベクトル $x$ に対してある実数 $c_1,\cdots c_n$ がとれて、$x$ を以下のように表せます（固有ベクトル $\phi_1,\cdots,\phi_n$は $\mathbb{R}^n$ の基底であるため)
x=\sum_ic_i\phi_i
これをレイリー商に代入すると、
\frac{x^TAx}{x^Tx}=\frac{\sum_ic_i\phi_i^TA\sum_jc_j\phi_j}{\sum_{i,j}c_ic_j\phi^T_i\phi_j}=\frac{\sum_{i,j}c_ic_j\lambda_j\phi_i^T\phi_j}{\sum_{i,j}c_ic_j\phi^T_i\phi_j}=\frac{\sum_i c_i^2\lambda_i}{\sum_i c_i^2}\\
=\frac{\lambda_1c_1^2+\cdots+\lambda_nc_n^2}{c_1^2+\cdots c_n^2} \geq \lambda_1\frac{c_1^2+\cdots+c_n^2}{c_1^2+\cdots+c_n^2}=\lambda_1
より、レイリー商の最小値が $A$ の最小固有値になることがわかります。
また、明らかに $x=\phi_1$ としてレイリー商に代入するとその値は $\lambda_1$ になり、最小値を達成するベクトルは $\lambda_1$ に対応する固有ベクトルであることがわかります。
最大値についても全く同様にもとめることができます。
途中の $\lambda_2,\cdots,\lambda_{n-1}$ についてですが、固有ベクトルの直交性をもちいて求めることができます。
すなわち、$\lambda_i$ を求めるには $x$ が $\phi_1,\cdots,\phi_{i-1}$ のベクトルと直交した平面（言い換えると、$\phi_i,\cdots,\phi_n$ が張る空間）で考えることによって全く同様にもとめることができます。
具体的には、先ほどの計算の分母分子にある $\phi_1 \cdots,\phi_{i-1}$ までの項が0になります。
##おまけ
微分のテクニック
ベクトルの微分と2次形式の微分についてまとめておきます。
他でも結構出てくるらしいので、ぜひ参考にしてください。
$x^Tx$ の $x_i$ についての微分
\frac{\partial}{\partial x_i} x^Tx=\frac{\partial}{\partial x_i} \sum_j x_j^2=\sum_j 2x_j\delta_{ij}=2x_i
ここで、 $\delta_{ij}$ はクロネッカーのデルタで $i=j$ のとき１でそれ以外は0となるものです。
$x^TAx$ の $x_i$ についての微分
\frac{\partial}{\partial x_i} x^TAx=\frac{\partial}{\partial x_i} \sum_{j,k} A_{jk}x_jx_k=\sum_{j,k} A_{jk}(\delta_{ij}x_k + x_j\delta_{ik}) \\
=\sum_{k} A_{ik}x_k + \sum_{j}A_{ji}x_j=\sum_{k} A_{ik}x_k + \sum_{j}A_{ij}x_j \\
=\sum_{k} A_{ik}x_k + \sum_{k}A_{ik}x_k=2\sum_{k} A_{ik}x_k=2(Ax)_i
ここで、行列の対称性 $A_{ij}=A_{ji}$ などを使っています。
他からの視点
先ほどはレイリー商の性質を固有ベクトルで展開して、ゴリゴリ計算して求めてみましたが、せっかくなので違った形で考えてみようと思います。
$x$ をレイリー商を最小化するベクトルとします。最小値を取る点での勾配は0になる必要があるので、先ほどのテクニックを使い計算してみると
\frac{\partial}{\partial x_i}\frac{x^TAx}{x^Tx}=\frac{(x^Tx)(2Ax)_i - (x^TAx)(2x_i)}{(x^Tx)^2} =0
とおくと、
(x^Tx)(2Ax)_i - (x^TAx)(2x_i)=0
すなわち、
(Ax)_i=\frac{x^TAx}{x^Tx}x_i
が得られます。$i$ は任意なので、
Ax = \frac{x^TAx}{x^Tx} x
となることがわかります。すなわち、レイリー商が最小値をとる $x$ は固有ベクトルでその固有値はレイリー商 $\frac{x^TAx}{x^Tx}$ になることがわかりました。
まとめ
レイリー商を固有値を用いて特徴づけることができました。今回はのべられませんでしたが、次はレイリー商を使って、min-max定理についての記事を書くつもりです。