高等代数选讲笔记（4）——傅里叶变换

高等代数选讲笔记（4）——傅里叶变换

第四讲：傅里叶变换

傅里叶变换

信号传输

常见的如正弦波，余弦波。

如 $\cos (2 \pi t) = \Re e^{2\pi \mathrm{i} t}$。

其乘上复数 $c = r e^{-\mathrm{i} \theta}$ 得：

$$\Re \left (r e^{2\pi \mathrm{i} \left (t – \frac{\theta}{2 \pi} \right )} \right )$$
其图像，$r$ 对应振幅，$\frac{\theta}{2 \pi}$ 对应相位偏移。

信号的集合

$$c_1 e^{2 \pi \mathrm{i} t} + c_2 e^{4 \pi \mathrm{i} t} + \cdots +c_n e^{2n \pi \mathrm{i} t} + \cdots$$

输入一个信号，可以逼近：

$$c_0 + c_1 e^{2 \pi \mathrm{i} t} + \cdots + c_n e^{2 n \pi \mathrm{i} t}$$

傅里叶变换

将物理空间中的信号波 $f : [0, 1] \to \mathbb{C}, f = c_0 + c_1 e^{2 \pi \mathrm{i} t} + \cdots$ 映射到了频率空间 $\widehat{f} : \mathbb{Z} \to \mathbb{C}, \widehat{f} = (\cdots, c_{-1}, c_0, c_1, \cdots)$。

特殊情况：$f = e^{2 k \pi \mathrm{i} t}$：

$$\widehat{f}(n) = \delta_k(n) = \begin{cases} 1 & n = k \\ 0 & n \not = k \end{cases}$$

离散傅里叶变换

单位根

记 $\omega_n = \omega = e^{\frac{2 \pi \mathrm{i}}{n}}$，称为 $n$ 次单位根。

离散傅里叶变换

考虑前 $m$ 个余弦函数：

$$\begin{bmatrix} f(0) \\ f(\frac{1}{n}) \\ \vdots \\ f(\frac{n – 1}{n}) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{m – 1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(m – 1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n – 1} & \omega^{2(n – 1)} & \cdots & \omega^{(m – 1)(n – 1)} \end{bmatrix} \begin{bmatrix} c_0 \\ c_1 \\ \vdots \\ c_{m – 1} \end{bmatrix} \\ y = A_{m, n} C$$
取 $m = n$，$F_n = A_{m, n}$ 称为离散傅里叶矩阵，则 $y = F_n C$。

注意 $F_n$ 是可逆的（$\frac{1}{\sqrt{n}} F_n$ 是酉矩阵）。

如果要计算 $y = F_n C$ 需要用到 $n^2$ 次乘法，如何减少运算量？

快速傅里叶变换

基本想法

找到 $F_n$ 与 $F_m$ 的关系，当 $n = 2m$ 时。

快速傅里叶变换

一般来说，我们有：

$$F_n = \begin{bmatrix} I_{\frac{n}{2}} & D_{\frac{n}{2}} \\ I_{\frac{n}{2}} & -D_{\frac{n}{2}} \end{bmatrix} \begin{bmatrix} F_{\frac{n}{2}} & 0 \\ 0 & F_{\frac{n}{2}} \end{bmatrix} P \\ D_{n} = \begin{bmatrix} 1 & 0& \cdots & 0 \\ 0 & \omega & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \omega^{n – 1} \end{bmatrix}$$
其中 $P$ 为一个置换阵。

需要迭代 $l = \log_2 n$ 次。

总共约需要乘法次数：$\frac{n}{2} \cdot l = \frac{n}{2} \log_2 n << n^2$。

蝴蝶图表

略。

bit-reverse order

把 $0 \sim 2^n – 1$ 写成二进制，然后前后顺序颠倒，再写回十进制，即可得到蝴蝶图表的左侧下标。

 笔记 高代选