Go to the future

はろー．

$a_p$ を定数として最高次数が $P$ な $x$ の多項式で表される関数

$f(x)=\sum_{p=1}^{P} a_p x^p$

の直交基底について，卒業研究で必要になってGoogle先生で調べたので残しておきます．ただし $x$ が一様分布に従う場合はググればいろいろ出てくるのに対して， $x$ が任意の分布に従う場合にどう計算すればいいかがあまり出てこなかったので，本記事では $x$ が任意の分布に従う場合について書きます．

問題を一般化すると，基底関数を要素として持つベクトル $\mathbf{\Phi}=\left[\phi_1(x), \phi_2(x),\dots \right]$ が与えられた場合に，任意の分布に従う $x$ について，異なるどの2つの基底も直交している直交基底ベクトルを導出する方法です．ただし，関数 $\phi_i(x)$ は $\mathbb{C} \to \mathbb{C}$ な関数であり，関数 $f$ と関数 $g$ が直交しているとは $E[f(x)g^{*}(x)]=0$ を満たすことを示すとします．つまり， $[-1,1]$ で一様乱数で分布する $x$ に対して $f(x)$ と $g(x)$ が直交しているか確認するためには以下を満たすかどうか確認すればよいです．

$\displaystyle \int_{-1}^{1} f(x) g^{*}(x) dx=0$

グラムシュミットの直交化法

説明するまでもなく，直交化といえばコレですよね．

$\displaystyle v_k(x) = \phi_k(x) - \sum_{i=0}^{k-1} E[\phi_k(x) u_i^{*}(x)]u_i(x)$

$\displaystyle u_k = \frac{v_k(x)}{\sqrt{E\left[|v_k(x)|^2\right]}}$

以上で， $u_0(x)$ から順番に $x$ に対して正規直交系な基底関数 $u_k(x)$ を得ることができます．

行列の対角化を使う方法

行列 $\Sigma$ を次のように定義します．

$\displaystyle \Sigma = E\left[\Phi \Phi^{H}\right]=\left\{E\left[\phi_i(x) \phi_j^{*}(x) \right]\right\}$

この行列 $\Sigma$ はエルミート行列であるので実数の固有値を持ち，ユニタリ行列 $U$ を用いて対角化可能です．

$\displaystyle \Sigma=UDU^{H}$

で，以下の様に変形していきます．

$\displaystyle D=U^{H} \Sigma U$

$\displaystyle D^{-\frac{1}{2}}$ を， $D$ は対角行列なので $D$ の対角要素の平方根を取った行列として，

$\displaystyle I=D^{-\frac{1}{2}}U^{H}\Sigma U D^{-\frac{1}{2}}$

$\Sigma$ を元に戻すと

$\displaystyle I=D^{-\frac{1}{2}}U^{H} \left(E\left[\Phi \Phi^{H}\right]\right) U D^{-\frac{1}{2}}$

$\displaystyle I=E\left[D^{-\frac{1}{2}}U^{H}\Phi \Phi^{H} U D^{-\frac{1}{2}} \right]$

また， $D$ は実対角行列であるので $\displaystyle \Psi = D^{-\frac{1}{2}}U^{H}\Phi$ とすると，

$\displaystyle I=E\left[\Psi \Psi^{H} \right]$

となります．したがって， $\Psi$ は正規直交基底となる関数を要素として持つベクトルとなります．

計算量について

求めたい直交基底の個数を $P$ とします．また両手法ともに任意の分布に従う複素数 $x$ を事前に $N$ 個を生成しておくとします． $\phi_i(x)$ の計算量を $\mathcal{O}(1)$ とします．基底関数の線形結合で表される関数の加減算は，その関数を各基底関数に対する係数のベクトルで表している場合， $\mathcal{O}(P)$ かかりますなぜなら，基底関数を $x$ と $x^2$ とした場合は $f(x)=ax+bx^2$ を $[a,b]$ と表すので，基底関数が $P$ 個あった場合は加減算に $\mathcal{O}(P)$ 必要となります．

さて，グラムシュミットの直交化法では $\mathcal{O}(P^3N)$ のオーダーとなりますが，行列の対角化を使う方法は $\mathcal{O}(P^3+NP)$ らしいです． $x$ は分布とか生成方法がわかっていれば事前計算できるので， $\Psi$ も事前計算できます．

とはいえ，僕が研究で使う場合は $P=10$ 程度に対して $N=10^6$ とかなので，グラムシュミットの直交化法ではちょっと重いかなって感じですね．