卷积与卷积定理 | 赛博物理终端

> DEFINITIONS RECAP

连续卷积：$(f*g)(t)=\int_{-\infty}^{\infty} f(\tau)g(t-\tau)\,d\tau$
离散卷积：$(f*g)[n]=\sum_k f[k]g[n-k]$
卷积定理：$\mathcal{F}\{f*g\}=F(\omega)\cdot G(\omega)$
对偶：$\mathcal{F}\{f\cdot g\}=\tfrac{1}{2\pi}F(\omega)*G(\omega)$

> KEY PROPERTIES

交换律f ∗ g = g ∗ f

结合律(f ∗ g) ∗ h = f ∗ (g ∗ h)

分配律f ∗ (g+h) = f∗g + f∗h

微分(f ∗ g)' = f' ∗ g = f ∗ g'

单位元f ∗ δ = f

Parseval∫|f|² dt = (1/2π)∫|F|² dω

> COMPLEXITY TABLE

直接卷积（定义）O(N·M)

FFT 卷积O(N log N)

N=1024 时节省~100×

N=1M 时节省~50000×

> CLOSING

傅里叶变换教我们：复杂的信号，不过是简单正弦的叠加。
卷积定理则告诉我们：复杂的相互作用，不过是频率分量的独立相乘。
当我们换一副眼镜看世界，缠绵的卷积便化作了轻盈的乘法。