离散 Fourier 级数

连续的Fourier 级数将 \(L_2([0,2 \pi])\) 空间中函数 \(f\) 与 \(l_2\) 空间中的 Fourier 系数 \(c_k\) 关联起来: \[ f(x) = \sum_{k \in \mathbb{Z}} c_k e^{i kx}, \quad c_k = \frac{1}{2 \pi} \int_{0}^{2 \pi} f(x) e^{-i kx} \mathrm{d} x \]

对于离散情景, 如果已知函数 \(f\) 在 \([0, 2\pi]\) 上 \(n\) 个点处的取值 \(f_0, f_1, \dots,f_{n-1}\), 那么, 是否存在一个映射关系 \(F: \mathbb{R}^n \mapsto \mathbb{R}^n\), 得到对应的 Fourier 级数系数 \(c_0, c_1, \dots,c_{n-1}\) 呢? 这就是离散的 Fourier 变换.

例: 离散的 Fourier 变换

已知函数 \(f\) 在点 \(0, \pi/2, \pi, 3\pi/2\) 上取值分别为 \(1,2,3,4\), 如果使用 Fourier 级数的前 4 项和作为函数 \(f\) 的近似: \[ \tilde f(x) \triangleq c_0 + c_1 e^{ix} + c_2 e^{i2x} + c_3 e^{i3x} \] 并令函数 \(\tilde f\) 在对应点处与函数 \(f\) 取值相同, 那么就得到关于系数 \(c_k, k=1,2,3,4\) 的四个方程: \[ \begin{aligned} c_0+c_1+c_2+c_3=2 \\ c_0+i c_1-c_2-i c_3=4 \\ c_0-c_1+c_2-c_3=6 \\ c_0-i c_1-c_2+i c_3=8 \end{aligned} \] 求解上述方程, 得到 \[ c_0 = 5, \quad c_1 = -1+i, \quad c_2 = -1, \quad c_3 = -1-i \] 注意到 \(c_0 = \mathrm{avg}~ f_i = \left( \sum_{i=0}^{3} f_i \right) / 4\), 这恰好与连续 Fourier 级数计算常数项系数的公式 \[ c_0 = \frac{1}{L} \int_{0}^{L} f(x) ~\mathrm{d}x \] 相仿!

因为 Fourier 变换是线性的, 对于 \(\mathbb{R}^n \mapsto \mathbb{R}^n\) 上的线性映射, 总可以找到一个 \(n \times n\) 的矩阵来表示. 我们约定在区间 \([0,2\pi]\) 上均匀分布的点集 \(x_k = 2\pi k/n\) 处采集函数 \(f\) 的数值 \(f_0, f_1, \dots, f_{n-1}\). 为方便表示之后得到的矩阵 \(F\), 定义如下复数 \(w\): \[ w \triangleq e^{i 2 \pi/n} \] 注意到 \(w^n = 1\), 是 \(1\) 的一个 \(n\) 次根. 近似函数取为 Fourier 级数的前 \(n\) 项和 \[ \tilde f(x) = \sum_{k=0}^{n-1} c_k e^{i k x}, \] 令 \(\tilde f(x_k) = f_k,~ k=0,1,\dots,n-1\), 就得到关于系数 \(c_k\) 的 \(n\) 个方程: \[ \begin{aligned} c_0 + c_1 + \cdots + c_k + \cdots + c_{n-1} = f_0, \\ c_0 + c_1 w + \cdots + c_k w^k + \cdots + c_{n-1} w^{n-1} = f_0, \\ c_0 + c_1 w^2 + \cdots + c_k w^{2k} + \cdots + c_{n-1} w^{2(n-1)} = f_0, \\ \cdots \end{aligned} \] 定义离散 Fourier 变换矩阵 \(F\) \[ F_{jk} \triangleq w^{jk},\quad j,k=0,1,2,\ldots,n-1 \] (注意矩阵的下标是从 0 开始索引的), 这样就可以得到方程 \[ F_{jk} c_k = f_j,\quad j=0,1,2,\ldots,n-1 \]

Fourier 变换矩阵最重要的性质是, 如果我们记 \(\overline{w} \triangleq e^{-i 2\pi/n}\), 以及 \(\overline F_{jk} \triangleq \overline w^{jk}\), 那么矩阵 \(F\) 的逆可以通过矩阵 \(\overline F\) 表示为 \[ (F)^{-1} = \frac{1}{n} \overline F, \quad \text{或者} \quad F \overline F = \overline F F = nI \tag{1} \] 证明过程也很整洁, 矩阵的乘法通过分量可以表示为等比数列之和: \[ \begin{aligned} (F \overline F)_{jl} &= F_{jk} \overline F_{kl} = e^{i 2\pi jk/n} e^{-i 2\pi kl/n} = \sum_{k=0}^{n-1} \left( e^{i 2\pi (j-l)/n} \right)^k \\ &= \begin{cases} \dfrac{1 - r^n}{1 - r},\quad j \neq l \\ n,\quad j=l \end{cases} \end{aligned} \] 式中, \(r \triangleq e^{i 2\pi (j-l)/n}\), 而当 \(j \neq l\) 时, \(r^n\) 恒等于 0: \[ r^n = e^{i 2\pi (j-l)} \equiv 1,\quad j \neq l \] 由此得到式 (1) 中的结论.

根据式 (1) 中的结论, 物理空间中的数据点 \(\{f_k\}\) 与相空间中的数据点 \(\{c_k\}\) 之间的关联为 \[ F_{jk} c_k = f_j, \quad \frac{1}{n} \overline F_{jk} f_k = c_j \]

或者写成 \[ f_j = c_k w^{jk}, \quad c_j = \frac{1}{n} f_k w^{-jk} \]