图上的信号

图上的信号一般表达为一个向量。假设有n个节点,假设每个节点的信号为: x = [ x 1 , x 2 , … , x n ] T ∈ R n x=[x_1,x_2,\dots,x_n]^T\in R^n x=[x1,x2,,xn]TRn。第 i i i个节点的信号值 x ( i ) = x i x(i)=x_i x(i)=xi
若图为灰度图,则x的每个元素为单一的数值;若图为多通道的彩色图,那么x中的每个元素则为一个多维度的向量。下面假设图为单一的灰度图,即 x i x_i xi为数值。

经典的傅里叶变换

连续傅里叶变换和逆变换公式:
f ^ ( w ) = ∫ − ∞ ∞ f ( t ) e − 2 π i w t d t f ( t ) = ∫ − ∞ ∞ f ^ ( w ) e − 2 π i w t d t (1) \hat{f}(w)=\int_{-\infty}^{\infty} f(t) e^{-2 \pi i wt} d t\\ {f}(t)=\int_{-\infty}^{\infty}\hat f(w) e^{-2 \pi i w t} d t\tag 1 f^(w)=f(t)e2πiwtdtf(t)=f^(w)e2πiwtdt(1)
其中 w w w为任意实数,表示频率。
离散傅里叶变换和逆变换的的公式:
x ^ ( w ) = ∑ t = 1 n x ( t ) e − i 2 π n w t x ( t ) = 1 n ∑ w = 1 n x ^ ( w ) e i 2 π n w t (2) \begin{array}{l} \hat x(w)=\sum_{t=1}^{n} x(t) e^{-i \frac{2 \pi}{n} w t} \\ x(t)=\frac{1}{n} \sum_{w=1}^{n} \hat x(w) e^{i \frac{2 \pi}{n} w t}\tag 2 \end{array} x^(w)=t=1nx(t)ein2πwtx(t)=n1w=1nx^(w)ein2πwt(2)
傅里叶变换中的不同频率的余弦函数可以被视为基函数,其傅里叶系数表示基的振幅:

傅里叶反变换的本质是把任意一个函数表示成若干个正交基函数的线性组合。

傅里叶变换的本质是求线性组合的系数。(2)式中可以看出,具体由原函数和基函数内积求得系数 f ^ ( w ) \hat f(w) f^(w)

图傅里叶变换

由于经典傅里叶变换的基函数是拉普拉斯算子的本征函数:
− Δ ( e 2 π i w t ) = − ∂ 2 ∂ t 2 e 2 π i w t = ( 2 π w ) 2 e 2 π i w t -\Delta\left(e^{2 \pi i w t}\right)=-\frac{\partial^{2}}{\partial t^{2}} e^{2 \pi i w t}=(2 \pi w)^{2} e^{2 \pi i w t} Δ(e2πiwt)=t22e2πiwt=(2πw)2e2πiwt

e 2 π i w t e^{2 \pi i w t} e2πiwt Δ \Delta Δ的本征函数。
本征函数是针对于算子而言的,可以推广到矩阵中。这里可以将本征函数看做是类似于特征向量,本征值看做类似于特征值。
拉普拉斯矩阵就是图上的拉普拉斯算子,所以图傅里叶变换的基函数可以直接选择拉普拉斯矩阵的特征向量。
L u ⃗ l = λ l u ⃗ l L\vec u_l = \lambda_l\vec u_l Lu l=λlu l

可以得出 u ⃗ l \vec u_l u l是矩阵 L L L的特征向量, λ l \lambda_l λl为其特征值。

由傅里叶反变换的本质得出,对于图上的任意信号值 x x x,我们需要找到一组正交基通过线性组合来表示这个 x x x
可以发现,上篇提到的拉普拉斯矩阵的特征向量 U = ( u ⃗ 1 , u ⃗ 2 , ⋯   , u ⃗ n ) U=\left(\vec{u}_{1}, \vec{u}_{2}, \cdots, \vec{u}_{n}\right) U=(u 1,u 2,,u n)就是一组这样的正交基,他可以用来作为图傅里叶变换的基函数。
那么任意图上的信号值 x x x可以表示为:
x = x ^ ( λ 1 ) u ⃗ 1 + x ^ ( λ 2 ) u ⃗ 2 + ⋯ + x ^ ( λ n ) u ⃗ n x=\hat{x}\left(\lambda_{1}\right) \vec{u}_{1}+\hat{x}\left(\lambda_{2}\right) \vec{u}_{2}+\cdots+\hat{x}\left(\lambda_{n}\right) \vec{u}_{n} x=x^(λ1)u 1+x^(λ2)u 2++x^(λn)u n

其中 x ^ ( λ i ) \hat x(\lambda_i) x^(λi)就为这组基函数的系数,即傅里叶系数,在这里 x x x相当于 f ( t ) f(t) f(t),系数相当于 f ^ ( w ) \hat f(w) f^(w)
则一般式可以推广到多维空间:
x = x ^ ( λ 1 ) u ⃗ 1 + x ^ ( λ 2 ) u ⃗ 2 + ⋯ + x ^ ( λ n ) u ⃗ n x ( i ) = ∑ l = 1 n x ^ ( λ l ) u l ( i ) \begin{array}{l} x=\hat{x}\left(\lambda_{1}\right) \vec{u}_{1}+\hat{x}\left(\lambda_{2}\right) \vec{u}_{2}+\cdots+\hat{x}\left(\lambda_{n}\right) \vec{u}_{n} \\ x(i)=\sum_{l=1}^{n} \hat{x}\left(\lambda_{l}\right) u_{l}(i) \end{array} x=x^(λ1)u 1+x^(λ2)u 2++x^(λn)u nx(i)=l=1nx^(λl)ul(i)

x ( i ) x(i) x(i)表示的是信号 x x x的第 i i i个值, u l ( i ) u_{l}(i) ul(i)表示第 u i u_i ui个特征向量的第 i i i个值。矩阵展开表示为:
( x ( 1 ) x ( 2 ) ⋮ x ( n ) ) = ( u 1 ( 1 ) u 2 ( 1 ) ⋯ u n ( 1 ) u 1 ( 2 ) u 2 ( 2 ) ⋯ u n ( 2 ) ⋮ ⋮ ⋱ ⋮ u 1 ( n ) u 2 ( n ) ⋯ u n ( n ) ) ( x ^ ( λ 1 ) x ^ ( λ 2 ) ⋮ x ^ ( λ n ) ) \left(\begin{array}{c} x(1) \\ x(2) \\ \vdots \\ x(n) \end{array}\right)=\left(\begin{array}{cccc} u_{1}(1) & u_{2}(1) & \cdots & u_{n}(1) \\ u_{1}(2) & u_{2}(2) & \cdots & u_{n}(2) \\ \vdots & \vdots & \ddots & \vdots \\ u_{1}(n) & u_{2}(n) & \cdots & u_{n}(n) \end{array}\right)\left(\begin{array}{c} \hat{x}\left(\lambda_{1}\right) \\ \hat{x}\left(\lambda_{2}\right) \\ \vdots \\ \hat{x}\left(\lambda_{n}\right) \end{array}\right) x(1)x(2)x(n)=u1(1)u1(2)u1(n)u2(1)u2(2)u2(n)un(1)un(2)un(n)x^(λ1)x^(λ2)x^(λn)
可以化简为:
( x ( 1 ) x ( 2 ) ⋮ x ( n ) ) = ( u ⃗ 1 , u ⃗ 2 , ⋯   , u ⃗ n ) ( x ^ ( λ 1 ) x ^ ( λ 2 ) ⋮ x ^ ( λ n ) ) \left(\begin{array}{c} x(1) \\ x(2) \\ \vdots \\ x(n) \end{array}\right)=\left(\vec{u}_{1}, \vec{u}_{2}, \cdots, \vec{u}_{n}\right) \left(\begin{array}{c} \hat{x}\left(\lambda_{1}\right) \\ \hat{x}\left(\lambda_{2}\right) \\ \vdots \\ \hat{x}\left(\lambda_{n}\right) \end{array}\right) x(1)x(2)x(n)=(u 1,u 2,,u n)x^(λ1)x^(λ2)x^(λn)

即:
x = U x ^ x = U\hat x x=Ux^

x x x就是原信号, x ^ \hat x x^就为谱域上的信号,每个元素对应基函数的一个系数(振幅)。

那么如何求这个系数呢??通过傅里叶变换。
由傅里叶变换得,系数由原函数和基函数内积得到:
x ^ ( λ l ) = ⟨ x , u ⃗ l ⟩ = ∑ i = 1 n x ( i ) u l ( i ) \hat{x}\left(\lambda_{l}\right)=\left\langle x, \vec{u}_{l}\right\rangle=\sum_{i=1}^{n} x(i) u_{l}(i) x^(λl)=x,u l=i=1nx(i)ul(i)
即:
( x ^ ( λ 1 ) x ^ ( λ 2 ) ⋮ x ^ ( λ n ) ) = ( u 1 ( 1 ) u 1 ( 2 ) ⋯ u 1 ( n ) u 2 ( 1 ) u 2 ( 2 ) ⋯ u 2 ( n ) ⋮ ⋮ ⋱ ⋮ u n ( 1 ) u n ( 2 ) ⋯ u n ( n ) ) ( x ( 1 ) x ( 2 ) ⋮ x ( n ) ) \left(\begin{array}{c} \hat x(\lambda_1) \\ \hat x(\lambda_2) \\ \vdots \\ \hat x(\lambda_n) \end{array}\right)=\left(\begin{array}{cccc} u_{1}(1) & u_{1}(2) & \cdots & u_{1}(n) \\ u_{2}(1) & u_{2}(2) & \cdots & u_{2}(n) \\ \vdots & \vdots & \ddots & \vdots \\ u_{n}(1) & u_{n}(2) & \cdots & u_{n}(n) \end{array}\right)\left(\begin{array}{c} {x}\left({1}\right) \\ {x}\left({2}\right) \\ \vdots \\ {x}\left({n}\right) \end{array}\right) x^(λ1)x^(λ2)x^(λn)=u1(1)u2(1)un(1)u1(2)u2(2)un(2)u1(n)u2(n)un(n)x(1)x(2)x(n)

即:
x ^ = U T x \hat x = U^T x x^=UTx

可以求出傅里叶系数。
由此得出图傅里叶变换为(由于拉普拉斯矩阵为半正定矩阵,其特征向量都是实向量,所以其共轭后还是自身,相对于离散型傅里叶变换,其基函数共轭后指数需加个符号):
x ( i ) = ∑ l = 1 n x ^ ( λ l ) u l ( i ) x ^ ( λ l ) = ∑ i = 1 n x ( i ) u l ( i ) \begin{array}{l} x(i)=\sum_{l=1}^{n} \hat{x}\left(\lambda_{l}\right) u_{l}(i) \\ \hat{x}\left(\lambda_{l}\right)=\sum_{i=1}^{n} x(i) u_{l}(i) \end{array} x(i)=l=1nx^(λl)ul(i)x^(λl)=i=1nx(i)ul(i)

经典傅里叶变换和图傅里叶变换的对比

经典傅里叶变换: f ^ ( w ) = ∫ R f ( t ) e − 2 π i w t d t \hat f(w)=\int_{\mathbb{R}} f(t) e^{-2 \pi i w t} d t f^(w)=Rf(t)e2πiwtdt(连续), x ^ ( w ) = ∑ i = 1 n e − 2 π n t w x ( t ) \hat x(w)=\sum_{i=1}^{n} e^{-\frac{2 \pi}{n} t w} x(t) x^(w)=i=1nen2πtwx(t)(离散)
基: e − 2 π i w t e^{-2 \pi i w t} e2πiwt(连续) , e − 2 π n t w e^{-\frac{2 \pi}{n} t w} en2πtw(离散)
频率: w w w
分量的振幅(和相位): f ^ ( w ) \hat f(w) f^(w)

图傅里叶变换: x ^ ( λ l ) = ∑ i = 1 n x ( i ) u l ( i ) \hat{x}\left(\lambda_{l}\right)=\sum_{i=1}^{n} x(i) u_{l}(i) x^(λl)=i=1nx(i)ul(i)
基: u ⃗ l \vec u_{l} u l
频率: λ l \lambda_l λl
分量的振幅: x ^ ( λ l ) \hat x(\lambda_l) x^(λl)

在图傅里叶变换中,拉普拉斯矩阵的特征值 λ \lambda λ担任了和频率 w w w类似的位置,特征向量 u ⃗ \vec u u 担任了基函数 e − 2 π n t w e^{-\frac{2 \pi}{n} t w} en2πtw的位置。
1.拉普拉斯的特征值都非负,最小值为0。
2.0特征值对应一个常数特征向量。
3.低特征值对应的特征向量比较平滑,高特征值对应的特征向量比较剧烈,可以类比为低频和高频基函数。

图类比到余弦函数,从左到右, u ⃗ 1 \vec u_1 u 1为特征值为0,类似于常数值基函数, u ⃗ 2 \vec u_2 u 2低特征值类似于低频基函数, u ⃗ 5 0 \vec u_50 u 50为高特征值类似于高频基函数。
可以通过图拉普拉斯二次型定义平滑程度,其表示有边相连的两个节点信号的平方差乘以边的权重后,其值越小,代表 x x x越平滑:
x T L x = 1 / 2 ∑ i , j = 1 m W i , j ( x ( i ) − x ( j ) ) 2 x^{T} L x=1 / 2 \sum_{i, j=1}^{m} W_{i, j}(x(i)-x(j))^{2} xTLx=1/2i,j=1mWi,j(x(i)x(j))2
x x x代为特征向量 u ⃗ l \vec u_l u l,则:
u ⃗ l T L u ⃗ 1 = λ l {\vec u_l}^TL \vec u_1=\lambda_l u lTLu 1=λl即符合特征值代表频率,特征值越高,基函数(余弦函数)越陡峭。

图傅里叶变换的作用

依靠图傅里叶变换,将图上节点的信号 x ∈ R n x\in R^n xRn从空间域转换到谱域, U U U为拉普拉斯矩阵的特征向量组成的基:
空间域——>谱域: x ^ = U T x ∈ R 2 \hat x=U^Tx\in R^2 x^=UTxR2
谱域——>空间域: x = U x ^ x=U \hat x x=Ux^