离散 Fourier 变换

阐述

设单位根 $\omega=e^{-2\pi i/N}$ ，则离散 Fourier 变换是对长度为 $N$ 的向量 $x$ 的变换，满足

y_k=\frac1{\sqrt N}\sum_{j=0}^{N-1}\omega^{jk}x_j

这可以视为一个矩阵向量乘法，矩阵为

F=\frac{1}{\sqrt{N}}\left[\begin{array}{cccccc}1 & 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^{2} & \omega^{3} & \cdots & \omega^{N-1} \\ 1 & \omega^{2} & \omega^{4} & \omega^{6} & \cdots & \omega^{2(N-1)} \\ 1 & \omega^{3} & \omega^{6} & \omega^{9} & \cdots & \omega^{3(N-1)} \\ \vdots & \vdots & \vdots & \vdots & & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \omega^{3(N-1)} & \cdots & \omega^{(N-1)(N-1)}\end{array}\right]

该变换为酉变换 $FF^\dagger=1$ 。

上述变换可以在 $O(N\log N)$ 的时间而非 $O(N^2)$ 的时间内完成。核心在于注意到上式是递归的：定义 $k=k_1+N_2k_2$ 、 $n=n_1+N_1n_2$ ，则有

y_{k_1+N_2k_2}=\frac1{\sqrt N}\sum_{n_1=0}^{N_1}\omega_{N_1}^{n_1k_2}\omega^{k_1n_1}\sum_{n_2=0}^{N_2}\omega_{N_2}^{n_1k_2}x_{n_1+N_1n_2}

例如，对于 Radix-2 的快速 Fourier 变换，计算方法为：

\hat f_n=F_nf_n=\begin{pmatrix}I_{n/2}&I_{n/2}\\I_{n/2}&-I_{n/2}\end{pmatrix}\begin{pmatrix}F_{n/2}f_e\\DF_{n/2}f_o\end{pmatrix}

其中 $D=\operatorname{diag}\{\omega^0,\cdots,\omega^{n/2-1}\}$ .

第一类余弦变换：要求函数能偶拓展到 $[0,2\pi]$ 区间内

\hat f_j=\frac2n\sum_{k=0}^{n-1}f_k\cos\frac{\pi jk}{n-1}=\Re\left(\frac2n\sum_{k=0}^{n-1}f_ke^{-2\pi ijk/2(n-1)}\right)

第二类正弦变换：要求函数能奇拓展到 $[0,2\pi]$ 区间内

\hat f_j=\frac2n\sum_{k=0}^{n-1}f_k\sin\frac{\pi (j+1)(k+1)}{n+1}=\Im\left(\frac2n\sum_{k=0}^{n-1}f_ke^{2\pi i(j+1)(k+1)/2(n-1)}\right)