时域卷积定理&频域卷积定理

前言

之前的文章介绍了卷积积分的计算，作为图神经网络的前置知识点，理解卷积定理有助于理解谱图卷积。

卷积定理是傅立叶变换满足的一个重要性质。维基百科中卷积定理的定义如下：

卷积定理指出，两个函数（或信号）的卷积的傅里叶变换是它们傅里叶变换的逐点乘积。

更一般地说，一个域（例如，时域）中的卷积等于另一个域（例如，频域）中的逐点乘法。具体分为时域卷积定理和频域卷积定理，时域卷积定理即时域内的卷积对应频域内的乘积；频域卷积定理即频域内的卷积对应时域内的乘积，两者具有对偶关系。

连续变量的函数

卷积定理

设两个函数 $g(t)$ 和 $h(t)$ 的傅里叶变换为 $G$ 和 $H$，

G ( f ) ≜ F { g } ( f ) = ∫ − ∞ ∞ g ( t ) e − i 2 π f t   d t , f ∈ R H ( f ) ≜ F { h } ( f ) = ∫ − ∞ ∞ h ( t ) e − i 2 π f t   d t , f ∈ R

G(f)H(f)​≜F{g}(f)=∫−∞∞​g(t)e−i2πftdt,f∈R≜F{h}(f)=∫−∞∞​h(t)e−i2πftdt,f∈R​其中， $\triangleq$表示定义为，$\mathcal{F}$是傅里叶变换算子。通常， F { g } ( f ) \mathcal{F}\{g\}(f) F{g}(f) 也可以表示为 F { g ( t ) } \mathcal{F}\{g(t)\} F{g(t)}、 $\mathcal{F}[g(t)]$。$g$ 和 $h$ 的卷积定义为：
r ( t ) = { g ∗ h } ( t ) ≜ ∫ − ∞ ∞ g ( τ ) h ( t − τ )   d τ = ∫ − ∞ ∞ g ( t − τ ) h ( τ )   d τ . r(t) = \{g*h\}(t) \triangleq \int_{-\infty}^{\infty} g(\tau) h(t-\tau)\, d\tau = \int_{-\infty}^{\infty} g(t-\tau) h(\tau)\, d\tau. r(t)={g∗h}(t)≜∫−∞∞​g(τ)h(t−τ)dτ=∫−∞∞​g(t−τ)h(τ)dτ.这里，$\ast$ 表示卷积。两个函数其他形式的卷积有$g(t)\ast h(t)$，博文卷积积分的计算有助于理解卷积。

卷积定理表述为：
R ( f ) ≜ F { r } ( f ) = G ( f ) H ( f ) . f ∈ R ( 1 ) R(f) \triangleq \mathcal{F}\{r\}(f) = G(f) H(f). \quad f \in \mathbb{R}\quad\quad(1) R(f)≜F{r}(f)=G(f)H(f).f∈R(1)其中$R(f)$也可以写成如下形式：$R(f)\triangleq \mathcal{F}[r(t)]\triangleq \mathcal{F}[h(t)\ast g(t)]$。

证明

根据傅里叶变换及卷积积分有：
F [ g ( t ) ∗ h ( t ) ] = ∫ − ∞ + ∞ g ( t ) ∗ h ( t ) e − i ω t d t = ∫ − ∞ + ∞ ∫ − ∞ + ∞ g ( τ ) ∗ h ( t − τ ) d τ e − i ω t d t ( 卷积展开 ) = ∫ − ∞ + ∞ ∫ − ∞ + ∞ h ( t − τ ) e − i ω t d t   g ( τ ) d τ ( 1 )

F[g(t)∗h(t)]​=∫−∞+∞​g(t)∗h(t)e−iωtdt=∫−∞+∞​∫−∞+∞​g(τ)∗h(t−τ)dτe−iωtdt(卷积展开)=∫−∞+∞​∫−∞+∞​h(t−τ)e−iωtdtg(τ)dτ(1)​令$x=t-\tau$，则$t=x+\tau$，$dt=dx$，所以：
( 1 ) = ∫ − ∞ + ∞ ∫ − ∞ + ∞ h ( x ) e − i ω ( x + τ ) d x   g ( τ ) d τ = ∫ − ∞ + ∞ ∫ − ∞ + ∞ h ( x ) e − i ω x e − i ω τ d x   g ( τ ) d τ = ∫ − ∞ + ∞ h ( x ) e − i ω x ∫ − ∞ + ∞ e − i ω τ d x   g ( τ ) d τ ( x 是在 τ 的积分中是常量 , 可以移出来 ) = g ( ω ) ⋅ h ( ω )

(1)=∫−\infin+\infin∫−\infin+\infinh(x)e−iω(x+τ)dxg(τ)dτ=∫−\infin+\infin∫−\infin+\infinh(x)e−iωxe−iωτdxg(τ)dτ=∫−\infin+\infinh(x)e−iωx∫−\infin+\infine−iωτdxg(τ)dτ(x是在τ的积分中是常量,可以移出来)=g(ω)⋅h(ω)" role="presentation">(1)=∫+\infin−\infin∫+\infin−\infinh(x)e−iω(x+τ)dxg(τ)dτ=∫+\infin−\infin∫+\infin−\infinh(x)e−iωxe−iωτdxg(τ)dτ=∫+\infin−\infinh(x)e−iωx∫+\infin−\infine−iωτdxg(τ)dτ(x是在τ的积分中是常量,可以移出来)=g(ω)⋅h(ω)$$\begin{array}{rl}(1)& ={\int }_{-\text{infin}}^{+\text{infin}}{\int }_{-\text{infin}}^{+\text{infin}}h(x)e^{-i\omega (x+\tau )}dxg(\tau )d\tau \\ & ={\int }_{-\text{infin}}^{+\text{infin}}{\int }_{-\text{infin}}^{+\text{infin}}h(x)e^{-i\omega x}{e}^{-i\omega \tau }dxg(\tau )d\tau \\ & ={\int }_{-\text{infin}}^{+\text{infin}}h(x)e^{-i\omega x}{\int }_{-\text{infin}}^{+\text{infin}}{e}^{-i\omega \tau }dxg(\tau )d\tau (x是在\tau 的积分中是常量,可以移出来)\\ & =g(\omega )\cdot h(\omega )\end{array}$$

(1)​=∫−∞+∞​∫−∞+∞​h(x)e−iω(x+τ)dxg(τ)dτ=∫−∞+∞​∫−∞+∞​h(x)e−iωxe−iωτdxg(τ)dτ=∫−∞+∞​h(x)e−iωx∫−∞+∞​e−iωτdxg(τ)dτ(x是在τ的积分中是常量,可以移出来)=g(ω)⋅h(ω)​其中$\omega =2\pi f$。
证毕。$■$

小结

上述为时域卷积定理的公式及证明，频域卷积定义与之类似。所以连续变量函数的卷积定理为：

时域卷积定理为：$\mathcal{F}[g(t)\ast h(t)]=G(\omega )\cdot H(\omega )$

频域卷积定理为：$\mathcal{F}[g(t)\cdot h(t)]=\frac{1}{2\pi }G(\omega )\ast H(\omega )$

离散变量序列

卷积定理

对于离散变量序列，有着与连续变量函数类似的定理，这里 $\mathcal{F}$ 表示离散傅里叶变换算子，设两个序列 $g[n]$ 和 $h[n]$ 的傅里叶变换为 $G$ 和 $H$：
G ( f ) ≜ F { g } ( f ) = ∑ n = − ∞ ∞ g [ n ] ⋅ e − i 2 π f n    , f ∈ R H ( f ) ≜ F { h } ( f ) = ∑ n = − ∞ ∞ h [ n ] ⋅ e − i 2 π f n    . f ∈ R

G(f)H(f)​≜F{g}(f)=n=−∞∑∞​g[n]⋅e−i2πfn,f∈R≜F{h}(f)=n=−∞∑∞​h[n]⋅e−i2πfn.f∈R​

序列 $g$ 和 $h$ 的离散卷积的定义为：

$$r[n]\triangleq (g\ast h)[n]=\sum _{m=-\infty }^{\infty }g[m]\cdot h[n-m]=\sum _{m=-\infty }^{\infty }g[n-m]\cdot h[m].$$ $(g\ast h)[n]$也可以表示为 $g[n]\ast h[n]$。

离散序列的卷积定理为：

R ( f ) = F { g ∗ h } ( f ) =   G ( f ) H ( f ) R(f) = \mathcal{F}\{g * h\}(f) =\ G(f) H(f) R(f)=F{g∗h}(f)= G(f)H(f) \quad 或
R ( ω ) = F { g ∗ h } ( ω ) =   G ( ω ) H ( ω ) R(\omega) = \mathcal{F}\{g * h\}(\omega) =\ G(\omega) H(\omega) R(ω)=F{g∗h}(ω)= G(ω)H(ω)

证明

本证明来自劉奕文教授的Lecture《The Discrete-Time Fourier Transform and
Convolution Theorems: A Brief Tutorial》(pdf)

Y ( ω ) = ∑ n = − ∞ ∞ y [ n ] e − j ω n = ∑ n = − ∞ ∞ ( ∑ m = − ∞ ∞ g [ m ] ⋅ h [ n − m ] ) e − j ω n = ∑ m = − ∞ ∞ g [ m ] ( ∑ m = − ∞ ∞ h [ n − m ] e − j ω n ) = ∑ m = − ∞ ∞ g [ m ] ( ∑ m = − ∞ ∞ h [ n − m ] e − j ω ( n − m )   e − j ω ( m ) ) = ∑ m = − ∞ ∞ g [ m ] e − j ω ( m ) ( ∑ m = − ∞ ∞ h [ n − m ] e − j ω ( n − m ) ) = ∑ m = − ∞ ∞ g [ m ] e − j ω ( m ) H ( ω ) = G ( ω ) H ( ω )

Y(ω)​=n=−∞∑∞​y[n]e−jωn=n=−∞∑∞​(m=−∞∑∞​g[m]⋅h[n−m])e−jωn=m=−∞∑∞​g[m](m=−∞∑∞​h[n−m]e−jωn)=m=−∞∑∞​g[m](m=−∞∑∞​h[n−m]e−jω(n−m)e−jω(m))=m=−∞∑∞​g[m]e−jω(m)(m=−∞∑∞​h[n−m]e−jω(n−m))=m=−∞∑∞​g[m]e−jω(m)H(ω)=G(ω)H(ω)​$■$

小结

上述为时域卷积定理的公式及证明，频域卷积定义与之类似。所以离散变量序列的卷积定理为：

时域卷积定理为：$\mathcal{F}[g\ast h]=G(\omega )\cdot H(\omega )$

频域卷积定理为：$\mathcal{F}[g\cdot h]=\frac{1}{2\pi }G(\omega )\ast H(\omega )$