FFT (2)

Wikipedia には Hadamard Transform について次のように書かれている。Hadamard transform - Wikipedia

The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multidimensional DFT of size 2 × 2 × ⋯ × 2 × 2.

まあ分かるのだが,FFTと同様に多項式で説明できる。恐らくどこかで既出だと思う。

記述の煩雑さを防ぐために 2×2×2 の Hadamard Transform に関して説明する。一般に関してもほとんど変わらない。数列 a[n] の Hadamard Transform は多項式で説明できる。具体的には 3 変数多項式

$$f(x,y,z)=a[000] + a[001] x + a[010] y + a[011] xy + a[100] z + a[101] xz + a[110] yz + a[111] xyz$$

に対応させる。xor convolution が高速に計算できるというのは,多項式 f, g の積が係数表現より具体値表現の方が高速に計算できることに由来する。実際にどのような具体値で計算するのがいいのかというと,書くのが大変なので 2 変数多項式で書くと,

\begin{align}
f(+1,+1) &= a[00] + a[01] + a[10] + a[11] \\
f(-1,+1) &= a[00] - a[01] + a[10] - a[11] \\
f(+1,-1) &= a[00] + a[01] - a[10] - a[11] \\
f(-1,-1) &= a[00] - a[01] - a[10] + a[11]
\end{align}

が良い。何故かと言うと,$x^2=1$ を満たすような $x$ というのが xor の性質をよく言い表していて,ちなみに Hadamard 行列にもなっていて,ということ。基本的には 2D FFT とかも $x^n=1$ を満たすような $x$ というのが鍵となっている。逆変換も存在しないと辛くて,Hadamard Transform の場合は標数 2 の体(-1=1 となるような体)は辛いし,一般には原始 n 乗根が存在しない体も辛い。

この議論を派生させると,$x^2=x$ となるような $x$ を使って変換するとどうなるのか,というのが出てきて,これが丁度 Zeta Transform に対応している。