图信号处理——拉普拉斯矩阵
用 G ( V , E ) G(V,E) G(V,E) 表示图， V V V 为图的节点集， E E E 为图的边集。
用 A = [ a i j ] A = [a_{ij}] A=[aij] 表示图的邻接矩阵。图的拉普拉斯矩阵为： L = D − A L = D-A L=D−A，其中 D = [ d i j ] D = [d_{ij}] D=[dij]，为对角矩阵，对角元满足 d i i = ∑ j a i j d_{ii} = \sum_j a_{ij} dii=∑jaij，即 A A A 的第 i i i行元素之和。
拉普拉斯矩阵有几个重要性质：
- L ⋅ 1 ⃗ = 0 ⃗ L\cdot \vec{1} = \vec{0} L⋅1=0，暗示含有特征值 0；
- 对称矩阵，有N个实特征值和特征向量；
- 对于任意图信号 x x x， ( L x ) i = ∑ j ∈ N i ( x i − x j ) (Lx)_i = \sum_{j\in N_i} (x_i - x_j) (Lx)i=∑j∈Ni(xi−xj)，即 L x Lx Lx 的第 i i i 个元素的含义为节点 i i i 的信号与其邻居节点的信号的差距之和，因此称其为 variation；
- 对于任意向量 x ∈ R N x\in\mathbb{R}^N x∈RN， x T L x = ∑ i x i ∑ j ∈ N i ( x i − x j ) = ∑ i ∑ j ∈ N i x i ( x i − x j ) = ∑ i , j ( x i − x j ) 2 ≥ 0 x^TLx = \sum_i x_i\sum_{j\in N_i} (x_i - x_j)= \sum_i \sum_{j\in N_i} x_i(x_i - x_j)= \sum_{i,j}(x_i - x_j)^2\geq 0 xTLx=∑ixi∑j∈Ni(xi−xj)=∑i∑j∈Nixi(xi−xj)=∑i,j(xi−xj)2≥0 。说明 L L L 是半正定矩阵。 x T L x x^TLx xTLx 称为 total variation，常作为 Graph Laplacian Regularizer 用于正则化.
- 拉普拉斯矩阵有几种归一化方式： L ^ = I − D − 1 A \hat{L} = I-D^{-1}A L^=I−D−1A或者 L ˉ = I − D − 1 2 A D − 1 2 \bar{L} = I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} Lˉ=I−D−21AD−21其中 L ^ \hat{L} L^ 保证每一行元素之和为 1， L ˉ \bar{L} Lˉ 为对称矩阵。
图信号滤波
假设向量
x
⃗
∈
R
N
\vec{x}\in\mathbb{R}^N
x∈RN 为原始图信号，其中
N
N
N 为图的节点数，我们可以用
A
,
W
,
D
,
L
,
L
1
,
L
2
A,W,D,L,L1,L2
A,W,D,L,L1,L2 对原始图信号滤波。
具体来看：
y
=
A
x
y = Ax
y=Ax，则
y
i
=
∑
j
∈
N
i
x
j
y_i = \sum_{j\in N_i} x_j
yi=∑j∈Nixj，即新的图信号
y
y
y 表示邻居节点的原始信号之和。易得
D
−
1
A
D^{-1}A
D−1A 表示所有邻居节点的原始信号的均值。