commons-math 解読 (16) : 高速アダマール変換 FastHadamardTransformer

今回は高速アダマール変換を見ていきます。　アダマール変換 (Hadamard Transform) は、昔 CPU パワーが充分でなかったときにフーリエ変換がコストのかかる計算だったので、その代替としてよく使われていたそうですが、最近はあまり使われてないみたいですね*1。

この記事では、変換データ数が少ない場合にどのように変換されているかを簡単に見るだけにします。　高速アダマール変換を表すクラス FastHadamardTransformer は前回みた RealTransformer インターフェースを実装しています。　また、変換データ数（transform() メソッドに渡す double の配列の要素数）は、FastFourierTransformer や FastSineTransformer と同じく、2 の累乗 (2, 4, 8, ・・・)でなければなりません。

N=2

データ数が2の場合は手で計算できるレベルのものです。　変換を表にすると

x	y
x₀	y₀ = x₀ + x₁
x₁	y₁ = x₀ - x₁

この変換は1次変換なので、行列を使って表すことができます（便利かどうかは別にして:-P）：

　　 ${ \displaystyle \begin{align*} \textbf{x} &= \begin{pmatrix} x_0 \\ x_1 \end{pmatrix} & \textbf{y} &= \begin{pmatrix} y_0 \\ y_1 \end{pmatrix} \end{align*} }$

と定義して、変換行列を ${ T }$ とすると

　　 ${ \displaystyle \begin{align*} \textrm{transform() : }\quad \textbf{x} &\mapsto \textbf{y} = T\textbf{x} & T &= \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \end{align*} }$

と表すことができます。　2×2行列なら簡単に逆行列が求まって、

　　 ${ \displaystyle \begin{align*} T^{-1} = \frac{1}{2}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \end{align*} }$

となります。

N=4

次はデータ数が4の場合。　x から y への変換ですが、間に a という変数を挟むとどんな変換が行われているか分かりやすいですね。　N が増えたときにどのように拡張されているかも分かると思います：

x	a	y
x₀	a₀ = x₀ + x₁	y₀ = a₀ + a₁
x₁	a₁ = x₂ + x₃	y₁ = a₂ + a₃
x₂	a₂ = x₀ - x₁	y₂ = a₀ - a₁
x₃	a₃ = x₂ - x₃	y₃ = a₂ - a₃

変換を行列で表すとこうなります：
　　 $T = \begin{pmatrix} 1 & 1 && \\ && 1 & 1 \\ 1 & -1 && \\ && 1 & -1 \end{pmatrix}^2 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}$
ただ、要素を書き下すだけでももう限界。

N=8

データ数が 8 の場合。　書くのは面倒だけど、やってることはそんなに難しくないかと。

x	a	b	y
x₀	a₀ = x₀ + x₁	b₀ = a₀ + a₁	y₀ = b₀ + b₁
x₁	a₁ = x₂ + x₃	b₁ = a₂ + a₃	y₁ = b₂ + b₃
x₂	a₂ = x₄ + x₅	b₂ = a₄ + a₅	y₂ = b₄ + b₅
x₃	a₃ = x₆ + x₇	b₃ = a₆ + a₇	y₃ = b₆ + b₇
x₄	a₄ = x₀ - x₁	b₄ = a₀ - a₁	y₄ = b₀ - b₁
x₅	a₅ = x₂ - x₃	b₅ = a₂ - a₃	y₅ = b₂ - b₃
x₆	a₆ = x₄ - x₅	b₆ = a₄ - a₅	y₆ = b₄ - b₅
x₇	a₇ = x₆ - x₇	b₇ = a₆ - a₇	y₇ = b₆ - b₇