利用联合平滑性的时变图信号重构算法

索秋月 林基明,2 王俊义

1(桂林电子科技大学信息与通信学院 广西 桂林 541004) 2(西安电子科技大学通信工程学院 陕西 西安 710071)

0 引 言

近年来，在社交网络、电力网络、交通运输网络、传感器网络等领域产生海量数据，这些数据具有复杂的非欧几里得特性。图信号处理就是一种处理高维非欧几里得数据的新工具，它用图捕获数据的拓扑结构。图结构中的顶点对应数据中的每个元素，连接两两顶点的边表示数据元素之间的关联关系，从而从网络中获取的数据对应图结构上的信号。图信号处理工具把传统的信号处理概念扩展到图上，进而处理和分析不规则高维数据[1-3]。

在各种实际应用中，噪声污染、数据丢失，以及为了节省能量或方便传输进行的数据采样现象非常普遍，因此，为了保证所获得数据的真实性，从有噪、有缺失的图信号观测值中重构真实的图信号很有研究意义。从而，图信号重构算法成为了学者们的一个研究热点。在图信号处理领域，随时间变化的图信号为时变图信号。现有的时变图信号重构算法都是从降低算法的复杂度和提高算法的重构精度两方面进行创新。为了降低重构算法的计算复杂度，一些分布式重构算法被提出[4-7]。另一方面，为了提升信号重构精度，现有的文献常常利用数据的相关性。文献[8]提出一个基于正则化的恢复框架，该框架最小化高通图滤波器输出和相对于已知样本的恢复误差，并给出了该优化问题的封闭解。该文提供了一种把信号恢复问题描述为优化问题的解决思路。文献[9]提出一种基于变差最小化的重构算法,将图信号重构问题转化为一个优化问题，并用交替方向乘子法得到重构信号，从而提供了一种通用的信号重构问题解决方案。文献[10]提出一种利用时差信号在图上的平滑性的时变图信号重构算法，该算法显著提高了时变图信号的重构精度。文献[11]将用于时变图信号分析的联合谐波分析概念提升为一个成熟的时间-顶点信号处理框架，该框架把传统信号处理技术与图信号处理新工具联系了起来，并证明了该框架可以用于提高时变图信号的重构精度。文献[12]建立了一种联合图域模型，并根据模型中传感器网络数据的关联特性设计了迭代重构算法，提高了重构精度。

受以上研究的启发，本文提出利用联合平滑性的时变图信号重构算法(Joint Smooth Reconstruction of Time-Varying Graph Signals，JSR-TVGS)。在2个公开的真实数据集上分别进行实验，结果表明：与仅利用时差信号平滑性的批量重构算法[10](Batch Reconstruction of Time-Varying Graph Signals，BR-TVGS)、仅利用联合变差最小化的重构算法[11](Joint Variation Minimization Reconstruction，JVMR)相比，JSR-TVGS算法重构精度更高。

1 图信号处理相关知识

在图信号处理(Graph Signal Processing)[1]中，一个无向、连通、加权图表示为：G=(V，E，W)，其中：V={v1,v2,…,vN}是图的N个顶点的集合；E={ei,j}是连接顶点的连边集合，元素ei,j表示vi和vj有边相连；W∈RN×N是图的加权邻接矩阵,也是对称矩阵。元素wij是非负的，表示vi和vj边的权重，定量地表示了图上顶点信号之间的相似性，两个顶点无边相连时wij=0，且wij=0,i=1,2,…,N。假设图上的时变图信号是等时间间隔采样的连续T个时刻的信号，把N个顶点上的时变图信号表示为X=[x1,x2,…,xT]∈RN×T,式中：xt∈RN,t=1,2,…,T表示在时刻t的图信号，矩阵X的元素xit表示顶点vi在时刻t的信号值。图拉普拉斯矩阵定义为：

LG=D-W

(1)

(2)

不同的特征值λi,i=1,2,…,N视为图谱域的图频率,特征值的大小表示图频率的大小[14]。

2 利用联合平滑性的重构算法

2.1 时差信号平滑性

时变图信号存在两种相关性：(1) 某一时刻，空间上相邻的图信号相似；(2) 某一顶点的图信号随着时间变化缓慢。因此，不能忽略时间维度上的相关性。时变图信号越平滑，则信号之间的变差越小。通过傅里叶变换，可以直观地了解信号的变化快慢，定量表示信号之间的变差。

图信号在t时刻的变差可以表示[1]为：

(3)

(4)

进而把时差信号的平滑性定义为：

S2(XDh)=tr((XDh)TLG(XDh))

(5)

时变图信号的观测矩阵可以表示为：

Y=J∘X+N

(6)

式中：∘表示哈达玛积；N是加性高斯白噪声；J∈{0,1}N×T是采样算子，定义为：

(7)

式中：v表示顶点；St表示在时刻被采样的顶点的集合。

基于时差信号在图域中的平滑性，文献[10]提出一种时变图信号的重构算法(BR-TVGS)，该算法的优化问题表示为：

(8)

式中：η是正则化参数。文献[10]虽然考虑了时间的影响，但其假设时变图信号在时间维度是每个时刻图信号简单独立地序列叠加，忽略了信号在时域中的平滑性。

2.2 时变图信号的联合变差

由第1节可知图傅里叶变换(GFT)定义为：GFT{X}=U-1X，矩阵X左乘一个图傅里叶变换矩阵，相当于矩阵X每列独立地进行图傅里叶变换，忽视了信号的时间维度。为了同时获得时变图信号在时间域和图域的频率分量，文献[15]和文献[11]把图信号处理与传统信号处理统一起来，定义了图-时间傅里叶变换：

JFT{X}=U-1XV-1

(9)

S(X)=tr(XTLGX)+tr(XLTXT)

(10)

式中：LT为时域图拉普拉斯矩阵，LT=VΛTV-1，ΛT(m,m)=2(1-cos(ωm))。S(X)越小，图信号越平滑。由式(10)可知，时变图信号的联合变差是图域变差与时域变差的和，即时变图信号的平滑性可在图域和时域分开讨论。

文献[11]基于联合谐波分析，提出联合变差最小化重构算法(JVMR)，其优化问题模型为：

(11)

式中：γ1、γ2是正则化参数。JVMR算法利用了信号在时域中的全局平滑性，但没有充分利用信号在图域中的平滑性。

2.3 本文算法简介

基于时变图信号的联合变差可分离的性质，本文利用时变图信号分别在图域和时域中的平滑性来重构信号，并把时变图信号重构问题描述为如式(12)所示的优化问题。

(12)

式中:α、β>0是正则化参数。本文默认存在收集所有顶点观测数据Y的计算中心，已知图拉普拉斯矩阵LG和时域图拉普拉斯矩阵LT且不随时间变化。根据式(13)的推导：

(13)

(14)

β(LT⊗IN)z

(15)

1) 对任意的顶点vt∈V,i=1,2,…,N,一定存在一个时刻t∈{1,2,…,T}使Jv,t=1。

2) 有一个基准时刻t0∈{1,2,…,T}，使得对于任一时刻t∈{1,2,…,T}，t≠t0,存在一个顶点vt∈V满足Jvtt0=Jv,t=1。

+β(LT⊗IN)]-1Qvec(Y)

(16)

然而，式(16)涉及大小为MN×MN的矩阵的逆的计算，该计算的计算复杂度较高，尤其是当重构一个大规模顶点集的长期跟踪的数据时，式(16)的计算复杂度更高。因此，本文用快速迭代收缩阈值算法[16-17](Fast Iterative Shrinkage-Thresholding Algorithm，FISTA)求解式(12)。

FISTA求解最小化问题的思想基于梯度下降法，基于梯度下降思想得到迭代计算公式为：

X(k+1)=X(k)-μ▽f(X(k))

(17)

相比梯度下降法优化了每一步迭代起始点X(k)的选择，进而更快地找到最小值点。

根据式(12)，得到f(X)的梯度如下：

基于上述分析，本文提出利用联合平滑性的时变图信号重构算法(JSR-TVGS)。具体步骤如下。

步骤1基于时变图信号联合变差概念，得到图拉普拉斯矩阵LG和时域图拉普拉斯矩阵LT。

步骤2采样。使采样算子J同时满足文献[10]定理中的两个条件，并从真实数据集得到观测数据Y。

步骤3初始化设置。迭代次数k初始值为1，时差算子Dh；正则化参数α、β；步长μ；S(1)=X(0)=Y；τ1=1；最大迭代次数K；终止迭代阈值ε。

步骤4迭代。

1)X(k)=S(k)-μ▽f(S(k))。

步骤5若k=K或|f(X(k)-f(X(k-1))|/|f(X(k))|<ε则迭代终止，并输出重构的时变图信号X(k)；否则令k=k+1，并跳转到步骤4。

3 实验与结果分析

在实验中，选取了2个不同的真实数据集进行重构算法的仿真测试。用图信号处理工具箱GSPBox[18]构建时变图信号的图域模型G=(V,E,W)和联合域图模型中的参数LG、LT。为了不失一般性，采用简单的均匀采样策略，采样率为固定值r∈(0,1)。在每个时刻t∈{1,2,…,T}，采样的顶点数为所有顶点数N与采样率r的积：Ns=N×r，每个时刻从N个顶点中随机地采样Ns个顶点，对应采样矩阵J每列的非零元素。每个时刻的采样互相独立。设置噪声N的标准差σ=0.01。本文实验仿真部分使用凸优化工具箱UNLocBoX[19]中的FISTA得到凸优化问题的解，其中：步长μ采用工具箱的默认值1；最大迭代次数K=3×107；终止迭代阈值ε=10-5。用穷举搜索法选择最优的正则化参数α和β，本文实验中，正则化参数α、β的取值集合为{0.01,0.02,0.05,0.1,0.2,0.5,1}。在相同的实验环境下，分别将本文提出的JSR-TVGS算法和BR-TVGS算法、JVMR算法应用到同一真实数据集，以便对比分析。

在本文实验中，用平均绝对误差(Mean Absolute Error,MAE)评价算法性能，其中平均绝对误差的计算方法为：

(18)

式中：X(k)是重构的信号；X是真实信号；Nx是信号长度。MAE越小，说明真实信号与重构信号越接近，重构误差越小，重构算法的重构精度越高。为了使实验结果更可信，对于每个采样率r，本文进行了100次独立随机采样实验，最终对比的重构误差是所有100次实验的MAE的平均值。

3.1 加利福尼亚州每日平均PM2.5浓度数据

美国环境保护局公布的加利福尼亚州每日平均PM2.5浓度数据集[20]是从2015年1月1日开始的200天内在93个观测点收集的，每天收集每个观测点的数据一次。数据大小为93×100。数据的图域模型如图1所示。可以看出图域模型中顶点的空间分布及顶点之间的关联关系与实际的情况相符，图信号处理工具适用于该数据的处理。

图1 加利福尼亚洲每日平均PM2.5浓度图网络

在该真实数据上的实验仿真结果如图2所示。可以看出：(1) 存在高斯白噪声的情况下，对于不同的采样率，利用JSR-TVGS算法都能重构出误差较小的PM2.5浓度数据。这说明本文算法对于时变图信号的重构是有效的。(2) 随着采样率的提高，本文提出的JSR-TVGS算法的重构误差降低。这是因为用于重构的观测信号信息越充分，重构误差越小。这与实际情况相符，说明了JSR-TVGS算法的合理性。(3) 在采样率相同的情况下，与其他两种算法相比，JSR-TVGS算法的平均绝对误差更小，重构精度更高。

图2 每日平均PM2.5浓度数据在不同采样率下 的平均重构误差

3.2 温度传感器网络数据

温度传感器网络数据[21]是从实验室中分布的54个传感器收集的2004年2月28日09:26到11:06间的数据，传感器每隔30 s采集一次数据。除掉一个故障的传感器，所选数据的大小为53×200。温度传感器网络数据图域模型如图3所示。可以看出图域模型中顶点的空间分布及顶点之间的关联关系与实际的情况相符，图信号处理工具适用于该数据的处理。

图3 温度传感器网络数据图域模型

在该真实数据上的实验仿真结果如图4所示。可以看出：(1) 存在高斯白噪声的情况下，对于不同的采样率，利用JSR-TVGS算法都能重构出误差较小的温度传感器网络数据。这说明本文算法对于时变图信号的重构是有效的。(2) 随着采样率的提高，JSR-TVGS算法的重构误差降低。虽然采样率大于0.5之后，这种现象不太明显，但误差基本保持较小。这是因为用于重构的观测信号信息越充分，重构误差越小。采样率为0.5时，重构温度传感器网络数据的观测信息已足够充分，再增加采样率不会明显降低重构误差。温度传感器网络数据较平滑，不需要过高的采样率就能重构出理想的信号。这些与实际情况相符，说明了JSR-TVGS算法的合理性。(3) 在采样率相同的情况下，与其他两种算法相比，JSR-TVGS算法的平均绝对误差更小，重构精度更高。

图4 温度传感器网络数据在不同采样率下的平均重构误差

4 结 语

本文基于时差信号在图域中比信号本身更平滑的特点以及时变图信号在时域中的平滑性，提出一种利用联合平滑性的时变图信号重构算法。该算法把时变图信号重构问题转化为凸优化问题，并用快速迭代收缩阈值算法求解，得到重构的时变图信号。当我们重构一个大规模顶点集的长期跟踪的数据时，使用本文算法重构信号是快速有效的。实验结果表明了本文算法重构时变图信号的有效性及合理性，且与相关的时变图信号重构算法相比，本文算法重构精度更高。未来的研究重点是将本文算法应用到具体场景中，进一步提高重构精度。