Fast Fourier Transform

Fourier Series

淑芬讲的那个, 任意信号 (波形) 可以转换成正弦/余弦波的加和

Fourier Transform

理解这个的精髓在于看视频

这里有 3B1B, Veritasium, 漫士, 还有鹤翔万里

~~关注 ZJU 学长鹤翔万里谢谢喵~~

3B1B 相对直观一些, 相当于在复平面上绕圈, 当频率与原信号相同时, 复平面上的向量加和后的质心会偏离原点, 以此将这个子波分离

Veritasium 讲了为什么要构造这个 \(e^{i\omega t}\) 的欧拉项, 本质上还是在试探一个与原信号的波频率相同的正弦波, 由正弦的正交性, 只有有相同频率的组成部分, 积分才会是正值

而如果原信号有相位偏移, 即可能是余弦波, 正弦相乘积分等于 \(0\), 那需要用余弦去试探

既有余弦又有正弦, 就不妨使用 \(e^{i\omega t}\) 把两项组合成一项

另一种解释

可以理解为在 Hilbert 空间中的算子, \(L^2(\mathbb R)\to L^2(\mathbb R)\)

在这个空间定义内积:

\[\int f(x)\bar g(x)\]

傅里叶希望解决热传导方程

所以选择微分算子 \(D=-i\frac{\text d}{\text dx}\) 的特征函数(正交基) \(e^{i\omega t}\)

这个算子也是薛定谔方程里用的那个动量算符

选择微分算子, 进行谱分解可以对角化, 从偏微分方程化成若干独立的一阶常微分方程

应用

characteristic function

概率论中的 \(X+Y\) 概率密度需要卷积

卷积相当于平移后做内积

而平移算子的特征函数正好也是 \(e^{i\omega t}\)

更具体地, 微分算子是平移算子的生成元:

\[T_a=E^{-iaD}\]

所以 "时域的卷积积分转换成频域的简单乘法" 的性质不变

有个定理来描述这个 "简单乘法" 的性质: 卷积定理

本质是对平移群的酉表示进行谱分解, 而平移群的生成元是微分算子

quantum mechanics

动量算符
位置波函数 \(\leftrightarrow\) 动量波函数
不确定性原理

有限阿贝尔群上的傅里叶变换

Pontryagin 对偶

DFT and FFT

application

polynomial multiplication

noise reduction

最简单的想法就是把原信号分解成频谱, 把高频部分去掉, 做逆傅里叶变换回去