一、信号处理:时域与频域
时域(Time Domain)是我们生活中常见的信号表示方式,以横轴为时间,纵轴为信号该时刻的强度(幅度),就可以得到一张时域图。打个比方,通过每时每刻的震动强度可以得到音频的时域图,或者画一张每小时的车流量,或者每日的降水量的图,也是时域图。
频域(Frequency Domain)则是一种数学上描述信号的方式。在频域中,唯一存在的波形是正弦波(Sine Wave,此处指代余弦和正弦这样的简谐波总称),通过不断叠加不同周期的正弦波,我们认为我们可以拟合所有的时域信号。画成图的话,频域是横轴为频率,纵轴为幅度的一个图形。
那么我们为什么需要频域呢?一方面,将复杂信号拆分为不同频率的正弦波,可以更简洁地对其进行表示。另一方面,通过频率分离,我们可以做到一些滤波操作。例如,一段音频里既有男生在说话,也有女生在说话,我们想把男女生的声音分开,而女生的声音频率要比男生的高,于是就可以根据频率来划分。保留男生的低频声音的滤波叫做低通滤波,而保留女生的高频声音的滤波叫做高通滤波。
二、傅里叶变换
2.1 傅里叶变换的本质
傅里叶变换的总公式如下:
F
(
ω
)
=
∫
−
∞
+
∞
f
(
t
)
e
−
i
ω
t
d
t
F(\omega) =\int_{-\infty}^{+\infty} f(t)e^{-i\omega t}dt
F(ω)=∫−∞+∞f(t)e−iωtdt
其中
ω
\omega
ω表示频率,而
t
t
t表示时间,这个操作就是把信号从时域转到频域上。
这个可怕的式子到底是什么意思呢?在这里非常推荐3Blue1Brown的图解。
让我们回到高中学过,或者高中的你正在学的复数概念。复数是二维的数,在横轴的实数轴上,又添加了一条纵轴的虚数轴。而单位虚数
i
=
−
1
i=\sqrt{-1}
i=−1。
著名欧拉公式就是
e
i
x
=
cos
x
+
i
sin
x
e^{ix}=\cos x + i \sin x
eix=cosx+isinx,这个公式有一个重要的几何意义,那就是
e
i
x
e^{ix}
eix代表着在复平面上,从(1,0)出发,沿着圆心为原点,半径为1的单位圆逆时针走
x
x
x个单位的圆周,所落到的点代表的复数。
由此可知:
- h ( t ) = e i t h(t)=e^{it} h(t)=eit 代表一个每秒走1个单位的圆周的,在圆周上逆时针运动的点的轨迹函数。
- h ( t ) = e − i t h(t)=e^{-it} h(t)=e−it是顺时针运动的轨迹函数。
- h ( t ) = e − i ω t h(t)=e^{-i\omega t} h(t)=e−iωt是每 1 ω \frac{1}{\omega} ω1秒走1单位圆周(或者说每秒走 ω \omega ω单位圆周),在圆周上逆时针运动的点的轨迹函数。
-
h
(
t
)
=
f
(
t
)
e
−
i
ω
t
h(t)=f(t)e^{-i\omega t}
h(t)=f(t)e−iωt,则相当于我们将时域图上,横轴为时间,纵轴为幅度的
f
(
t
)
f(t)
f(t),画到了圆上。时间从轴变成了角度,幅度从轴变成了幅长(到原点的距离)。圆上的一圈,我们能画原时域图
1
ω
\frac{1}{\omega}
ω1秒的内容。
对于一个正弦波,大部分情况下只要你无限地画下去,它在圆周上都会分布得比较均匀,除了……当 1 ω \frac{1}{\omega} ω1秒恰好是原正弦波的一个周期时。此时,时域图上波峰的位置会在圆的一侧,而波谷的位置会在另一侧,就像这样:
那么这时,我们将这个图形上所有的点都加起来,也就是,找它们二维上的几何平均点(质心),就可以近似得到原函数在 ω \omega ω这个频率下的正弦波有多大的强度。而这种正弦波在原函数中持续时间越长(画了越多圈上图的图案),得到的 F ( ω ) = ∫ − ∞ + ∞ f ( t ) e − i ω t d t F(\omega) =\int_{-\infty}^{+\infty} f(t)e^{-i\omega t}dt F(ω)=∫−∞+∞f(t)e−iωtdt也会越大。由此,我们就得到了原时域信号在不同频率下的强度。
同样,也存在频域到时域上的傅里叶逆变换:
f ( t ) = 1 2 π ∫ − ∞ ∞ F ( ω ) e i ω t d ω f(t) = \frac{1}{2\pi} \int_{-\infty}^{\infty} F(\omega) e^{i\omega t} d\omega f(t)=2π1∫−∞∞F(ω)eiωtdω
2.2 从线性代数角度看离散傅里叶变换
能够被存储下来的信号,往往没有真正的连续形式,故实际中用得更多的,是离散傅里叶变换。既然离散了,我们显然也没办法把所有频率都做一遍了,此时可以近似地用
2
k
π
n
(
k
∈
{
0
,
.
.
.
,
n
−
1
}
\frac{2k\pi}{n}(k \in \{0,...,n-1\}
n2kπ(k∈{0,...,n−1}这一套频率来近似地拟合,下面我们记记
W
n
=
e
2
π
n
i
W_n=e^{\frac{2\pi}{n}i}
Wn=en2πi。
假设我们在时域上有一组采样点
f
(
t
0
)
,
.
.
.
,
f
(
t
n
−
1
)
f(t_0),...,f(t_{n-1})
f(t0),...,f(tn−1),离散傅里叶变换的公式为:
F
(
W
n
k
)
=
∑
j
=
0
n
−
1
f
(
t
j
)
W
n
−
k
j
F(W_n^k)=\sum_{j=0}^{n-1} f(t_j) W_n^{-kj}
F(Wnk)=j=0∑n−1f(tj)Wn−kj
相应地,逆傅里叶变换的公式为:
f
(
t
j
)
=
1
n
∑
k
=
0
n
−
1
F
(
W
n
k
)
W
n
k
j
f(t_j) = \frac{1}{n}\sum_{k=0}^{n-1} F(W_n^k)W_n^{kj}
f(tj)=n1k=0∑n−1F(Wnk)Wnkj
如果把傅里叶变换写成矩阵形式,就是这样:
(
F
(
0
)
⋮
F
(
n
−
1
)
)
=
(
W
n
−
0
⋯
W
n
−
(
n
−
1
)
⋮
⋱
⋮
W
n
−
(
n
−
1
)
⋯
W
n
−
(
n
−
1
)
2
)
(
f
(
t
0
)
⋮
f
(
t
n
−
1
)
)
\begin{pmatrix} F(0) \\ \vdots \\ F(n-1) \end{pmatrix}= \begin{pmatrix} W_n^{-0} & \cdots & W_n^{-(n-1)} \\ \vdots & \ddots & \vdots \\ W_n^{-(n-1)} & \cdots & W_n^{-(n-1)^2} \end{pmatrix} \begin{pmatrix} f(t_0) \\ \vdots \\ f(t_{n-1}) \end{pmatrix}
F(0)⋮F(n−1)
=
Wn−0⋮Wn−(n−1)⋯⋱⋯Wn−(n−1)⋮Wn−(n−1)2
f(t0)⋮f(tn−1)
中间那个巨大的矩阵,我们记作
U
U
U,于是上式可以简写为
F
=
U
f
F=Uf
F=Uf。
同样,我们可以把逆傅里叶变换写成
f
=
1
n
V
F
f=\frac{1}{n}VF
f=n1VF,其中
V
i
j
=
W
n
i
j
V_{ij}=W_n^{ij}
Vij=Wnij
考虑
(
V
U
)
i
j
=
∑
k
=
0
n
−
1
W
n
i
k
W
n
−
k
j
=
∑
k
=
0
n
−
1
W
n
k
(
i
−
j
)
(VU)_{ij}=\sum_{k=0}^{n-1} W_n^{ik}W_n^{-kj}=\sum_{k=0}^{n-1}W_n^{k(i-j)}
(VU)ij=∑k=0n−1WnikWn−kj=∑k=0n−1Wnk(i−j)
当
i
=
j
i=j
i=j时,显然和为
(
V
U
)
i
i
=
n
(VU)_{ii}=n
(VU)ii=n。而
i
≠
j
i \not= j
i=j时,根据等比数列求和可得
(
V
U
)
i
j
=
W
n
n
(
i
−
j
)
−
1
W
n
(
i
−
j
)
−
1
(VU)_{ij}=\frac{W^{n(i-j)}_n-1}{W^{(i-j)}_n-1}
(VU)ij=Wn(i−j)−1Wnn(i−j)−1,由
W
n
n
=
1
W^n_n=1
Wnn=1可知此时
(
V
U
)
i
j
=
0
(VU)_{ij}=0
(VU)ij=0。
三、拉普拉斯算子
拉普拉斯算子(Laplace Operator)写作一个正着的三角,表示梯度的散度,简单来说,对于
n
n
n维函数(注意这里是
n
n
n维而不是
n
n
n个采样点)
f
(
x
1
,
.
.
.
,
x
n
)
f(x_1,...,x_n)
f(x1,...,xn)有:
Δ
f
=
∇
⋅
∇
f
=
(
∂
∂
x
1
…
∂
∂
x
n
)
(
∂
∂
x
1
⋮
∂
∂
x
n
)
f
=
∑
i
=
1
n
∂
2
f
∂
x
i
2
\Delta f = \nabla \cdot \nabla f = \begin{pmatrix} \frac{\partial}{\partial x_1} & \dots & \frac{\partial}{\partial x_n}\end{pmatrix}\begin{pmatrix} \frac{\partial}{\partial x_1} \\ \vdots \\ \frac{\partial}{\partial x_n}\end{pmatrix}f=\sum_{i=1}^n \frac{\partial^2 f}{\partial x_i^2}
Δf=∇⋅∇f=(∂x1∂…∂xn∂)
∂x1∂⋮∂xn∂
f=i=1∑n∂xi2∂2f
那么拉普拉斯算子和频率有什么关系呢?写成连续形式或许不够直观,我们可以考虑一个二维离散的场景,即,对一张灰度图使用拉普拉斯算子。函数
f
(
x
,
y
)
f(x,y)
f(x,y)表示的是灰度图上
(
x
,
y
)
(x,y)
(x,y)点的灰度。在此情景下,我们近似地将导数
∂
f
∂
x
=
lim
h
→
0
(
f
(
x
+
h
)
−
f
(
x
)
)
\frac{\partial f}{\partial x}=\lim_{h \to 0} (f(x+h)-f(x))
∂x∂f=limh→0(f(x+h)−f(x))写作
f
(
x
+
1
)
−
f
(
x
)
f(x+1)-f(x)
f(x+1)−f(x)或
f
(
x
)
−
f
(
x
−
1
)
f(x)-f(x-1)
f(x)−f(x−1),则:
∂
2
f
(
x
0
,
y
0
)
∂
x
0
2
+
∂
2
f
(
x
0
,
y
0
)
∂
y
0
2
\frac{\partial^2 f(x_0,y_0)}{\partial x_0^2}+\frac{\partial^2 f(x_0,y_0)}{\partial y_0^2}
∂x02∂2f(x0,y0)+∂y02∂2f(x0,y0)
=
∂
f
(
x
0
+
1
,
y
0
)
∂
x
0
−
∂
f
(
x
0
,
y
0
)
∂
x
0
+
∂
f
(
x
0
,
y
0
+
1
)
∂
y
0
−
∂
f
(
x
0
,
y
0
)
∂
y
0
=\frac{\partial f(x_0+1,y_0)}{\partial x_0} - \frac{\partial f(x_0,y_0)}{\partial x_0} + \frac{\partial f(x_0,y_0+1)}{\partial y_0} - \frac{\partial f(x_0,y_0)}{\partial y_0}
=∂x0∂f(x0+1,y0)−∂x0∂f(x0,y0)+∂y0∂f(x0,y0+1)−∂y0∂f(x0,y0)
=
f
(
x
0
+
1
,
y
0
)
+
f
(
x
0
,
y
0
+
1
)
+
f
(
x
0
−
1
,
y
0
)
+
f
(
x
0
,
y
0
−
1
)
−
4
f
(
x
0
,
y
0
)
=f(x_0+1,y_0)+f(x_0,y_0+1)+f(x_0-1,y_0)+f(x_0,y_0-1)-4f(x_0,y_0)
=f(x0+1,y0)+f(x0,y0+1)+f(x0−1,y0)+f(x0,y0−1)−4f(x0,y0)
而这反映了这个像素点处灰度值的变化大小,某种意义上相当于此处的频率。这也是CV中的拉普拉斯卷积核的来历:
(
0
1
0
1
−
4
1
0
1
0
)
\begin{pmatrix} 0 & 1 & 0 \\ 1 & -4 & 1 \\ 0 & 1 & 0 \end{pmatrix}
0101−41010
既然拉普拉斯算子是干这个用的,可以想见它和傅里叶变换会有些关系。为了寻求这个关系,我们可以回顾一下线性代数中特征值和特征向量的概念:
特征值和特征向量
概念:对于一个矩阵 A A A,若存在向量 u i u_i ui和常数值 λ i \lambda_i λi,使得 A u i = λ i u i Au_i=\lambda_i u_i Aui=λiui,则称 λ i \lambda_i λi为 A A A的特征值, u i u_i ui为 A A A的特征向量。
求法:则 ( A − λ i I ) u i = 0 (A-\lambda_i I)u_i=0 (A−λiI)ui=0,通过解 ∣ A − λ I ∣ = 0 |A-\lambda I|=0 ∣A−λI∣=0可以得到 n n n组解,再相应带入回原式可以得到相应的 λ i \lambda_i λi。矩阵的特征值集合是唯一的,而每个特征值对应的特征向量构成一个特征子空间。
矩阵的对角化:若 A A A有 n n n个线性无关的特征向量 U = ( u 1 , . . . , u n ) U=(u_1,...,u_n) U=(u1,...,un),则 A = U d i a g ( λ 1 , . . . , λ n ) U − 1 A=Udiag(\lambda_1,...,\lambda_n) U^{-1} A=Udiag(λ1,...,λn)U−1
利用对角化计算矩阵向量乘:将向量 x x x映射到空间 U U U中,得到 x = x 1 u 1 + . . . + x n u n x=x_1u_1+...+x_nu_n x=x1u1+...+xnun,则 A x = x 1 λ 1 u 1 + . . . + x n λ n u n Ax=x_1\lambda_1u_1+...+x_n \lambda_n u_n Ax=x1λ1u1+...+xnλnun
那么,假如有这样一个函数
f
f
f和常数值
λ
\lambda
λ,使得
Δ
f
=
λ
f
\Delta f = \lambda f
Δf=λf,岂不是这就是
Δ
\Delta
Δ的特征值和特征函数了吗?那么再想想,什么样的函数,经过两次求导,还能等于一个常数乘以它本身呢?答案是……
sin
x
\sin x
sinx,
cos
x
\cos x
cosx和
e
x
e^x
ex,对吧?事实上,
d
2
e
i
x
d
x
2
e
i
a
x
=
−
a
2
e
i
a
x
\frac{d^2 e^{ix}}{dx^2} e^{iax}=-a^2e^{iax}
dx2d2eixeiax=−a2eiax,也即
e
i
a
x
e^{iax}
eiax系列函数是拉普拉斯算子的特征函数。
我们可不可以像利用特征向量计算矩阵向量乘一样,利用这特征函数来计算拉普拉斯算子呢?那么第一步,我们就需要把一个任意函数
f
(
x
)
f(x)
f(x),映射到
e
i
a
x
e^{iax}
eiax的函数族空间中。实际上,套一下傅里叶函数的公式可知:
f
(
x
)
=
1
2
π
∫
−
∞
+
∞
(
∫
−
∞
+
∞
f
(
t
)
e
−
i
ω
t
d
t
)
e
i
ω
x
d
ω
f(x)=\frac{1}{2\pi}\int_{-\infty}^{+\infty} (\int_{-\infty}^{+\infty} f(t)e^{-i\omega t} dt) e^{i\omega x} d \omega
f(x)=2π1∫−∞+∞(∫−∞+∞f(t)e−iωtdt)eiωxdω
记
c
(
ω
)
=
1
2
π
∫
−
∞
+
∞
f
(
t
)
e
−
i
ω
t
d
t
c(\omega)=\frac{1}{2\pi}\int_{-\infty}^{+\infty} f(t)e^{-i\omega t} dt
c(ω)=2π1∫−∞+∞f(t)e−iωtdt,如果它收敛到一个常数值,则这个常数值是和
f
f
f整体有关,而和自变量
x
x
x的具体取值无关的。
f
(
x
)
f(x)
f(x)也就就此被映射到了特征函数族中。这时候,想做拉普拉斯算子,就是:
Δ f ( x ) = ∫ − ∞ + ∞ ω 2 c ( ω ) e i ω x d ω \Delta f(x)=\int_{-\infty}^{+\infty} \omega^2c(\omega)e^{i\omega x} d\omega Δf(x)=∫−∞+∞ω2c(ω)eiωxdω
四、图的拉普拉斯矩阵
设
A
A
A为图的邻接矩阵(即当i和j存在边时
A
i
j
=
1
A_{ij}=1
Aij=1,否则
A
i
j
=
0
A_{ij}=0
Aij=0,在此我们只考虑无向图,即
A
A
A为对称矩阵),而
D
D
D为图的度数矩阵(对角阵,
D
i
i
D_{ii}
Dii表示点
i
i
i有多少条邻边),定义图拉普拉斯矩阵为:
L
=
D
−
A
L=D-A
L=D−A
形象化地理解,我们考虑这样一个实际问题。有一个公园建在山上,公园内有
n
n
n个景点,一些景点之间有路相连。我们想要分析这个公园某个景点有多陡峭。应用拉普拉斯矩阵的话,是这样的:
Δ
h
(
u
)
=
∑
v
∈
N
e
i
g
h
b
o
r
(
u
)
(
h
(
u
)
−
h
(
v
)
)
\Delta h(u) = \sum_{v \in Neighbor(u)} (h(u)-h(v))
Δh(u)=v∈Neighbor(u)∑(h(u)−h(v))
Δ
h
=
(
Δ
h
(
1
)
⋮
Δ
h
(
n
)
)
=
(
D
−
A
)
h
=
L
A
\Delta h= \begin{pmatrix} \Delta h(1) \\ \vdots \\ \Delta h(n)\end{pmatrix}=(D-A)h=LA
Δh=
Δh(1)⋮Δh(n)
=(D−A)h=LA
当然,就这么直接用似乎还有些问题,直接用上面这个
L
L
L的话,似乎一个节点邻居越多,最后得到的变化值就越大,因此实际中我们一般会对其进行归一化,比如这样:
L
^
=
D
−
1
L
=
I
−
D
−
1
A
\hat L =D^{-1}L=I-D^{-1}A
L^=D−1L=I−D−1A
不过这种非对称归一化会有点小问题,我们假设点1有很多邻居,而点2只有点1一个邻居。在归一化时,
Δ
h
(
1
)
\Delta h(1)
Δh(1)只除了点1的度数,而
Δ
h
(
2
)
\Delta h(2)
Δh(2)只除了点2的度数。在一些问题(例如图上标签预测问题)中,我们认为此时2受到1的影响过高了。解决方案则是,在归一化过程中,点2受到点1的影响,不仅要除以和点2度数相关的量,也要除以和点1度数相关的量。具体来说,就是这样做对称归一化:
L
^
=
D
−
1
2
L
D
−
1
2
=
I
−
D
−
1
2
A
D
−
1
2
\hat L = D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I-D^{-\frac{1}{2}} A D^{-\frac{1}{2}}
L^=D−21LD−21=I−D−21AD−21
五、图傅里叶变换
一维信号的傅里叶变换,本质是用不同频率的正弦波来拟合原信号。那我们应该如何构造一组图上的基本信号,来拟合原图的函数呢。
考虑把信号记为
f
=
(
f
(
1
)
,
.
.
.
,
f
(
n
)
)
T
f=(f(1),...,f(n))^T
f=(f(1),...,f(n))T,然后考虑用下式,通过引入平方消除正负性的影响,来反映整张图的波动性(variation):
f
t
L
f
=
∑
i
,
j
,
i
<
j
A
i
j
(
f
(
i
)
−
f
(
j
)
)
2
f^tLf = \sum_{i,j,i<j}A_{ij}(f(i)-f(j))^2
ftLf=i,j,i<j∑Aij(f(i)−f(j))2
首先我们可以发现,对于
u
1
=
(
1
n
,
.
.
.
,
1
n
)
T
u_1=(\frac{1}{\sqrt{n}},...,\frac{1}{\sqrt{n}})^T
u1=(n1,...,n1)T(这里对向量的模做了归一化),
L
u
1
=
0
Lu_1=0
Lu1=0,即
u
1
u_1
u1是
L
L
L的一个特征向量,
0
0
0为其特征值,而且它能够使得原图的波动最小。接下来,我们不断重复以下过程:
u
k
=
min
∣
∣
f
∣
∣
=
1
,
f
∣
u
1
,
.
.
u
k
−
1
f
t
L
f
u_k = \min_{||f||=1, f \vert u_1,..u_{k-1}}f^t L f
uk=∣∣f∣∣=1,f∣u1,..uk−1minftLf
我们就会得到一组
L
L
L的特征向量正交基,它们也是一组使得原图波动最小的基本图信号,而且对应特征值
λ
k
=
u
k
t
L
u
k
\lambda_k=u_k^tLu_k
λk=uktLuk。
设
x
~
\widetilde x
x
为图信号
x
x
x在频域下的表示,则
x
=
u
1
x
~
1
+
.
.
.
+
u
n
x
~
n
=
U
x
~
x=u_1\widetilde x_1 +...+u_n \widetilde x_n =U \widetilde x
x=u1x
1+...+unx
n=Ux
。相应的,我们可以定义将
x
x
x表示在频域上的图傅里叶变换为
x
~
=
U
T
x
\widetilde x = U^T x
x
=UTx,而特征值
(
λ
1
,
.
.
.
λ
n
)
(\lambda_1,...\lambda_n)
(λ1,...λn),就是
n
n
n组频率。
下图就是一个不同频率上拉普拉斯特征向量的可视化表现:
六、图滤波与图卷积
我们之前提过,在声音信号中,通过改变原信号不同频率的强弱,可以做到诸如分离男女声音之类的功能,这个过程就叫滤波。此外还有一个经常提到的概念叫卷积,假设
f
f
f为原函数,
g
g
g为卷积核,
f
f
f和
g
g
g之间做卷积写成公式是这样的:
(
f
∗
g
)
(
t
)
=
∫
−
∞
∞
f
(
t
′
)
g
(
t
−
t
′
)
d
t
′
(f * g)(t)=\int_{-\infty}^{\infty} f(t')g(t-t') dt'
(f∗g)(t)=∫−∞∞f(t′)g(t−t′)dt′
而我们有:
卷积定理:若 f ^ \hat f f^是 f f f在频域上的表示,则 ( g ∗ g f ) ^ ( t ) = ( f ^ ⋅ g ^ ) ( ω ) = ∫ − ∞ + ∞ f ^ ( ω ) g ^ ( ω ) d ω \hat{(g *_g f)}(t)=(\hat f \cdot \hat g) (\omega)=\int_{-\infty}^{+\infty} \hat f(\omega)\hat g(\omega) d\omega (g∗gf)^(t)=(f^⋅g^)(ω)=∫−∞+∞f^(ω)g^(ω)dω。
虽然在这里我不打算展开证明,但可以简单介绍一下,利用这个定理,我们可以通过(1)将
f
f
f和
g
g
g用
O
(
n
log
n
)
O(n \log n)
O(nlogn)从时域转化为频域 (2)对二者在频域进行
O
(
n
)
O(n)
O(n)点积 (3)频域
O
(
n
log
n
)
O(n \log n)
O(nlogn)转化回时域 的三个步骤,将本来需要
O
(
n
2
)
O(n^2)
O(n2)计算的卷积在
O
(
n
log
n
)
O(n \log n)
O(nlogn)中快速完成。
让我们放眼第二步,你发现了什么?——没错,在频域上进行点积,不就是对
f
f
f在不同频率的强度进行调整吗?所以卷积和滤波本质上是相同的操作。
好,因为我们已经定义过图傅里叶变换了,所以可以以同样流程考虑图的情况,设
f
f
f为图结点的特征组成的向量,
g
g
g是卷积核,则:
(
g
∗
g
f
)
=
U
(
U
T
g
⋅
U
T
f
)
(g *_g f)=U(U^T g \cdot U^T f)
(g∗gf)=U(UTg⋅UTf)
令
W
=
d
i
a
g
(
U
T
g
)
W=diag(U^Tg)
W=diag(UTg),则
(
g
∗
g
f
)
=
U
W
U
T
f
(g *_g f)=UWU^T f
(g∗gf)=UWUTf
也即,如果我们希望对图信号进行处理,只需要找到(使用各种学习方法)合适的一组
W
W
W的
n
n
n个参数即可。这就是谱域(Spectral Domain)上的图卷积的基本思想。
当然,到目前为止,我们得到的这个信号处理方式想要实际应用还存在一些问题:
- W W W是和图形状强相关的,参数量和图的点数也有关,难以适用于不同的图。
- 需要计算图傅里叶算子(拉普拉斯矩阵的特征向量),这个过程是 O ( n 3 ) O(n^3) O(n3)的, n n n为图的点数,复杂度较高且和图规模相关。
- 只能用于无向图(需要拉普拉斯矩阵对称以保证可以找到正交基特征向量)。
- 难以对局部空间信息进行处理(毕竟所有频率都是全局的)。
我们将在下一节继续讨论这些问题。