A distributed algorithm for online reconstruction of spatio-temporal signals
-
摘要: 空时信号的在线重构问题可归结为对差分平滑的时变图信号的恢复问题。对于该凸优化问题，现有的基于梯度下降法的分布式重构算法在优化问题的海森矩阵条件数较大时收敛速度极慢，在单个观测区间内算法最大迭代次数受限时重构误差较大。针对该问题，提出了一种基于近似牛顿法的分布式在线重构算法。首先通过子图划分将原优化问题分解为一系列子图上的局部优化问题，并求出该局部问题的解，然后对子图间的局部解作融合平均计算，得到近似的全局最优解，再依据近似解与实际最优解之间的差距，证明以此方式求得的子图划分与融合矩阵具有稀疏性, 且可作为原优化问题的海森逆近似矩阵，最后将该近似矩阵替换至经典的牛顿法迭代公式，并利用该近似矩阵的结构化稀疏性实现分布式运算。仿真结果表明，与现有算法相比，该算法收敛速度更快，重构误差更小，所需通信量更少。Abstract: The reconstruction problem of spatio-temporal signals can be cast as recovering differential smooth time-varying graph signals. For the optimization problem, the existing distributed algorithm based on gradient descent method shows slow convergence when the condition number of the Hessian matrix of the problem is large which leads to a large reconstruction error when the maximum iteration number is limited in an observation interval. Therefore, an online distributed reconstruction algorithm based on approximate Newton′s method is proposed in the paper, whose principle is to decompose the original optimization problem into a series of local problems on subgraphs through subgraph decomposition and find these solutions, and then obtain the approximate global optimal solution via fusion average of local solutions between each subgraph. According to the gap between the approximate solution and the actual one, it can be proved that the decompostion and fusion matrix obtained in this way is sparse and can be regarded as the approximate Hessian inverse. Hence, the algorithm replaces the approximate matrix into the classical Newton iterative formula which can be implemented in a distributed manner due to the structural sparsity of the approximate matrix. Simulation results show that the proposed algorithm has faster convergence rate and smaller reconstruction error, and requires less communication cost compared with the existing algorithm.
-
当今信息时代，人类社会无处不充斥着海量的空时信号。随着科学技术的进步，这些信号逐渐向规模更大、纬度更高、结构更复杂的趋势发展，如无线传感器网络中的温度或湿度数据、社交媒体中的个人爱好信息、交通网络中的车流量数据和生物神经元网络中的生物电信号等[1-2]。现实世界的空时信号因能量受限、环境污染、机器故障、噪声干扰等因素影响，可能是缺失或不可靠的。以无线传感器网络中的监测工作为例，由于电量、内存和处理能力有限，传感器节点无法做到对数据时刻观测，因此整个网络的观测数据可能是不完整的[3-4]。此外，传感器节点还可能受硬件老化、噪声干扰或剧烈环境变化等因素影响而导致其监测数据异常[5]，此时该节点的可靠信号值是缺失的。在空时信号存在数据缺失时，为了保证后续信号处理工作的正常进行，需利用空时信号的关联特性对信号进行重构[6-7]。
图信号处理理论将传统信号处理邻域中的傅里叶变换、滤波、调制、卷积等概念推广到非规则的图上，是研究非规则域信号的有力工具[8-9]。空时信号在空间域与时间域上的关联性一般可由时变图信号的差分平滑性来描述[10-11]。图信号的差分平滑性是指该信号及其变化量在图上相邻顶点间相近的特性。例如，在温度传感器网络中，地理距离越靠近的节点，其测得的温度值及其变化趋势一般也越相近。利用差分平滑的时变图信号在线重构模型可以对缺失的空时信号进行重构，且该模型具有计算复杂度低、重构时延小、可分布式求解的优点[10]。然而，现有的求解该模型的分布式算法均基于梯度下降法[10]，其收敛速度相对缓慢，且易受优化问题的条件数影响[12-13]。对于分布式算法，过慢的收敛速度会导致分布式系统内节点通信量大增[14-15]，从而缩短系统使用寿命，因此需要设计一种新的收敛速度更快且更稳定的分布式算法。
针对现有算法[10]收敛速度相对慢的问题，提出了一种基于近似牛顿法的空时信号分布式在线重构算法。通过子图划分求出图信号重构优化问题的局部解，再进行子图融合，得到近似的全局最优解，并证明了以此方式求得的子图划分与融合矩阵具有稀疏性，可作为原优化问题的海森逆近似，最后将近似矩阵代替至牛顿法迭代公式，从而得到分布式近似牛顿法。
1. 空时信号在线重构模型
1.1 图信号处理基础知识
任意空间分布的N节点网络可建模为一个图。图G是由一组顶点与连接顶点的边构成的非线性数据结构，记为G=(V, E, W)，其中：V为顶点集合；E为边集合；W∈RN×N为图的加权邻接矩阵。一般地，图加权邻接矩阵可完全描述一个图的拓扑结构，其权值满足条件：若图上顶点i与顶点j相连，则Wij > 0；否则，Wij=0。对于相邻的两顶点i和j，顶点间关联性或相似性越强，则边的权值Wij越大。除了加权邻接矩阵外，还可用图的拉普拉斯矩阵L=D－W描述图的拓扑结构，其中D为图的度矩阵，其元素满足
dii=N∑j=1Wij。 (1) 对于N顶点的图G，图信号可定义为由其所在图G的顶点集合V到实数集R的映射，即x: V→R。若图的顶点顺序按某种方式确定，则图信号可简记为一个N维向量x=[x1，x2，…，xN]T∈RN，其中xi为图信号在顶点i上的信号值。通常将一段时间T内随时间发生变化的图信号称为时变图信号，并将其表示为由一组各时刻图信号向量组成的矩阵X=[x1，x2，…，xT]∈RN×T。
图信号的平滑性是指图信号在图上相邻两顶点间的信号值差异较小的特性。一般地，可由图拉普拉斯二次型xTLx来度量图信号的平滑度。根据图拉普拉斯矩阵的定义，拉普拉斯二次型可改写为
\boldsymbol{x}^{\mathrm{T}} \boldsymbol{L} \boldsymbol{x}=\frac{1}{2} \sum\limits_{i=1}^N \sum\limits_{j=1}^N W_{i j}\left(x_i-x_j\right)^2 。 (2) 由式(2)可知，拉普拉斯二次型的值越小，则权值越大的边相连的两顶点间信号值差异越小，因此图信号越平滑；反之，则图信号越不平滑。
1.2 差分平滑图信号在线重构模型
将不完整的空时信号抽象为一段时间T内经过采样的时变图信号。时变图信号的采样观测模型为
\boldsymbol{y}_t=\boldsymbol{S}_t \boldsymbol{x}_{t, \mathrm{o}}+\boldsymbol{n}_t, t=1,2, \cdots, T \text {, } (3) 其中：yt为t时刻图信号的实际观测值；xt, o为图信号的真实值；nt为独立同分布的观测噪声；St为采样操作。采样操作St是一个对角矩阵，其对角元素满足：若顶点i被采样，则其第i个对角元素为st, i=1；否则，st, i=0。经过采样操作，图信号的实际观测值存在零元素，即观测数据存在缺失的情况。
对于数据缺失的平滑图信号，可通过常用的平滑图信号在线重构模型对不完整信号进行恢复：
\min\limits_{\boldsymbol{x}_t} \frac{1}{2}\left\|\boldsymbol{S}_t \boldsymbol{x}_t-\boldsymbol{y}_t\right\|_2^2+\frac{\theta}{2} \boldsymbol{x}_t^{\mathrm{T}} \boldsymbol{L} \boldsymbol{x}_t, (4) 其中，目标函数第一项为数据匹配项，迫使重构信号在采样点靠近真实值，而第二项为平滑正则项，用来提升重构信号的平滑度。虽然式(4)可用于空时信号的重构任务，但是该模型只考虑了图信号在图顶点域上的平滑性，而未充分利用信号在时间域的关联性，因此重构误差较大[16]。为此，文献[10]指出，空时信号不仅本身在空间域呈平滑性，在时间域也呈平滑变化，并提出了对空时信号重构效果更好的差分平滑图信号在线重构模型：
\min\limits_{\boldsymbol{x}_t} \frac{1}{2}\left\|\boldsymbol{S}_t \boldsymbol{x}_t-\boldsymbol{y}_t\right\|_2^2+\frac{\theta}{2}\left(\boldsymbol{x}_t-\widetilde{\boldsymbol{x}}_{t-1}\right)^{\mathrm{T}} \boldsymbol{L}\left(\boldsymbol{x}_t-\widetilde{\boldsymbol{x}}_{t-1}\right), (5) 其中\widetilde{\boldsymbol{x}}_{t-1}为t－1时刻的重构图信号。根据该模型，当已知当前时刻观测信号和上一时刻的重构图信号时，可利用时变图信号的差分平滑性重构当前时刻信号值。当t=1时，令\widetilde{\boldsymbol{x}}_{t-1}=0，则此时重构模型(5)退化为模型(4)，可见模型(5)得到的第1个时刻重构图信号是平滑的，且所有时刻信号总体呈差分平滑的特点，因此该在线重构模型充分考虑了图信号时间顶点联合域上的平滑性。
2. 分布式在线重构算法
虽然文献[10]提出的在线重构模型(5)可对空时信号进行有效重构，但其求解算法属于一阶算法，收敛速度相对慢，且易受优化问题海森矩阵的条件数影响。对此，设计一种基于近似牛顿法的求解优化模型(5)的分布式算法。
模型(5)属于最小二乘优化问题，可分别求出其梯度gt(k)和海森矩阵Ht：
\boldsymbol{g}_t(k)=\boldsymbol{S}_t \boldsymbol{x}_t(k)-\boldsymbol{y}_t+\theta \boldsymbol{L}\left(\boldsymbol{x}_t(k)-\widetilde{\boldsymbol{x}}_{t-1}\right) \text {; } (6) \boldsymbol{H}_t=\boldsymbol{S}_t+\theta \boldsymbol{L}, (7) 其中k为迭代次数。因为图拉普拉斯矩阵L是一个与图具有相同稀疏模式的局部矩阵，所以梯度gt(k)的计算可分布式实现：
\left[\boldsymbol{v}_t(k)\right]_i=\left[\boldsymbol{x}_t(k)\right]_i-\left[\tilde{\boldsymbol{x}}_{t-1}\right]_i, (8) \begin{aligned} & {\left[\boldsymbol{g}_t(k)\right]_i=s_{t, i}\left[\boldsymbol{x}_t(k)\right]_i-\left[\boldsymbol{y}_t\right]_i+} \\ & \quad \theta \sum\limits_{j \in V_{i, r}} W_{i j}\left(\left[\boldsymbol{v}_t(k)\right]_i-\left[\boldsymbol{v}_t(k)\right]_j\right)， \end{aligned} (9) 其中，[gt(k)]i为向量gt(k)的第i个元素。Vi, r为顶点i的r阶邻域，其定义为：从顶点i出发，在r跳内可到达的所有顶点构成的集合(包含顶点i本身)。可见，各顶点计算梯度信息[gt(k)]i需要与其一阶邻域顶点交换一次信息[vt(k)]i。
根据凸优化理论，牛顿法属于二阶算法，其收敛速度较快，且对海森矩阵条件数不敏感[17]，因而可满足在线重构算法对收敛速度的要求，但需对海森矩阵求逆。矩阵求逆是一个集中式运算过程，因此对于整个图而言，无法分布式计算图规模大小的矩阵逆。不仅如此，矩阵求逆的计算复杂度较高，为O(N3)，不适用于大规模的空时信号重构任务。为了保持二阶算法收敛速度的优势，同时又可实现算法的分布式计算，需寻求一个具有结构化稀疏性的近似矩阵Pt来代替海森逆矩阵Ht-1，以完成牛顿法的近似迭代过程：
\boldsymbol{x}_t(k+1)=\boldsymbol{x}_t(k)+\boldsymbol{d}_t(k)=\boldsymbol{x}_t(k)-\boldsymbol{P}_t \boldsymbol{g}_t(k), (10) 其中dt(k)为近似牛顿步长。
2.1 矩阵逆近似
为了求得优化问题的海森逆近似矩阵Pt，首先将图G划分为一系列重叠的以顶点i为中心的子图Gi, r1：
G:=\bigcup\limits_{i \in V} G_{i, r_1}, (11) G_{i, r_1}:=\left(V_{i, r_1}, E_{i, r_1}\right), (12) 其中，Gi, r1为由顶点i的r1阶邻域顶点集合Vi, r1及连接这些顶点的边集合Ei, r1组成的子图。根据此子图划分方式，可将图G上的全局优化问题(5)分解为一系列子图Gi, r1上的子优化问题：
\begin{aligned} \min _{\boldsymbol{x}_t} & \frac{1}{2}\left\|\boldsymbol{S}_t \boldsymbol{R}_{i, r_1} \boldsymbol{x}_t-\boldsymbol{y}_t\right\|_2^2+ \\ & \frac{\theta}{2}\left(\boldsymbol{R}_{i, r_1} \boldsymbol{x}_t-\widetilde{\boldsymbol{x}}_{t-1}\right)^{\mathrm{T}} \boldsymbol{L}\left(\boldsymbol{R}_{i, r_1} \boldsymbol{x}_t-\widetilde{\boldsymbol{x}}_{t-1}\right) 。 \end{aligned} (13) 优化模型(13)中，Ri, r1为一个表示局部操作的对角矩阵，且满足：若图G上的顶点j在子图Gi, r1内，则Ri, r1的第j个对角元素等于1；否则，等于0。依靠局部操作Ri, r1，子优化问题的目标函数值仅与子图Gi, r1内的优化变量Ri, r1xt相关，而无需该子图外的其他变量。因此，该子优化问题是一个局部优化问题，可根据子图内数据求出局部最优解：
\hat{\boldsymbol{x}}_{t, i}=\left(\boldsymbol{R}_{i, r_1} \boldsymbol{H}_t \boldsymbol{R}_{i, r_1}\right)^{\dagger} \boldsymbol{R}_{i, r_1}\left(\boldsymbol{y}_t+\theta \boldsymbol{L} \widetilde{\boldsymbol{x}}_{t-1}\right)， (14) 其中(·)†表示矩阵求伪逆。由于矩阵Ri, r1HtRi, r1具有与子图Gi, r1相关的稀疏模式，即Ri, r1HtRi, r1只有对应于子图Gi, r1顶点的行列非零，而其他行列均为全零行或全零列。因此，该N阶矩阵求伪逆的计算过程可在子图内局部进行，且计算复杂度等价于一个r1阶小矩阵求逆。
直接通过式(14)求得的局部解损失了子图Gi, r1外的信息。为了互相弥补各子图内信息的缺失，需对子图的局部解作信息融合：
\left[\hat{\boldsymbol{x}}_t\right]_i=\frac{1}{\left|V_{i, r_2}\right|} \sum\limits_{j \in V_{i, r_2}}\left[\hat{\boldsymbol{x}}_{t, j}\right]_i, (15) 其中：\hat{\boldsymbol{x}}_t为经子图融合后得到的对原优化问题(5)的近似解；|Vi, r2|为集合Vi, r2的非零元素个数；r2为控制子图融合规模的参数，通常为一个小于r1的正整数。选取合适的参数r2，可有效降低子图融合的边界效应[18]。
综合子图划分(14)与子图融合(15)两个过程，图上的每个顶点i仅需先与其r1阶邻域顶点交换一次信息，求得\hat{\boldsymbol{x}}_{t, i}，再与其r2阶邻域顶点交换一次信息，便可得到近似最优解\hat{\boldsymbol{x}}_t，因此整个过程可分布式实现。将以上过程合并写为整个图上紧凑的矩阵向量乘积形式：
\hat{\boldsymbol{x}}_t=\left(\sum\limits_{j \in V} \boldsymbol{R}_{j, r_2}\right)^{-1} \sum\limits_{i \in V} \boldsymbol{R}_{i, r_2} \hat{\boldsymbol{x}}_{t, i}。 (16) 结合式(14)，可定义矩阵Pt为
\boldsymbol{P}_t=\left(\sum\limits_{j \in V} \boldsymbol{R}_{j, r_2}\right)^{-1} \cdot \sum\limits_{i \in V} \boldsymbol{R}_{i, r_2}\left(\boldsymbol{R}_{i, r_1} \boldsymbol{H}_t \boldsymbol{R}_{i, r_1}\right)^{\dagger} \boldsymbol{R}_{i, r_1}, (17) 则近似解\hat{\boldsymbol{x}}_t可简写为
\hat{\boldsymbol{x}}_t=\boldsymbol{P}_t\left(\boldsymbol{y}_t+\theta \boldsymbol{L} \widetilde{\boldsymbol{x}}_{t-1}\right) 。 (18) 因为子图划分与融合过程需每个顶点总共交换r1+r2阶邻域顶点的信息，所以矩阵Pt的第i行仅在对应子图Gi, r1+r2顶点的位置上存在非零元素，即该矩阵具有稀疏性。
令原优化问题的梯度向量(6)为零，可得原问题的最优解：
\boldsymbol{x}_t^*=\boldsymbol{H}_t^{-1}\left(\boldsymbol{y}_t+\theta \boldsymbol{L} \widetilde{\boldsymbol{x}}_{t-1}\right)_{\circ} (19) 将式(18)与式(19)对比可发现，近似解\hat{\boldsymbol{x}}_t与最优解的xt*的差异源于近似矩阵Pt与海森逆矩阵Ht－1的差异：
\left\|\hat{\boldsymbol{x}}_t-\boldsymbol{x}_t^*\right\|_2 \leqslant\left\|\boldsymbol{P}_t \boldsymbol{H}_t-\boldsymbol{I}\right\|_2\left\|\boldsymbol{x}_t^*\right\|_2, (20) 其中I为单位矩阵。根据文献[19-20]，随着参数r1、r2增大，‖PtHt－I‖2的值呈逐渐减小的趋势，于是总能找到一对足够大的参数，使‖PtHt－I‖2小于1，即近似解\hat{\boldsymbol{x}}_t与最优解xt*间的相对误差小于1，此时可认为矩阵Pt是海森逆矩阵Ht－1的近似。
2.2 分布式迭代
选取合适的参数对r1、r2后，利用式(17)可得海森逆近似矩阵Pt，将该矩阵代入式(10)，得到近似牛顿法迭代式：
\begin{gathered} \boldsymbol{x}_t(k+1)=\boldsymbol{x}_t(k)-\left(\sum\limits_{j \in V} \boldsymbol{R}_{j, r_2}\right)^{-1} \times \\ \sum\limits_{i \in V} \boldsymbol{R}_{i, r_2}\left(\boldsymbol{R}_{i, r_1} \boldsymbol{H}_t \boldsymbol{R}_{i, r_1}\right)^{\dagger} \boldsymbol{R}_{i, r_1} \boldsymbol{g}_t(k) 。 \end{gathered} (21) 由于矩阵Pt具有稀疏性，迭代式(21)可分布式实现。算法的分布式计算流程如下：
1) 输入数据\left[\widetilde{\boldsymbol{x}}_{t-1}\right]_i, [yt]i, Wij, θ；
2) 初始化[xt(0)]i=\left[\widetilde{\boldsymbol{x}}_{t-1}\right]_i；
循环执行：
3) 计算[vt(k)]i=[xt(k)]i－\left[\widetilde{\boldsymbol{x}}_{t-1}\right]_i；
4) 与1阶领域顶点交换信息[vt(k)]i，并计算
\begin{aligned} {\left[\boldsymbol{g}_t(k)\right]_i } & =s_{t, i}\left[\boldsymbol{x}_t(k)\right]_i-\left[\boldsymbol{y}_t\right]_i+ \\ & \theta \sum\limits_{j \in V_{i, 1}} W_{i j}\left(\left[\boldsymbol{v}_t(k)\right]_i-\left[\boldsymbol{v}_t(k)\right]_j\right) ; \end{aligned} 5) 与r1阶领域顶点交换信息[gt(k)]i，并计算
\boldsymbol{d}_{t, i}(k)=-\left[\boldsymbol{R}_{i, r_1}\left(\boldsymbol{S}_t+\theta \boldsymbol{L}\right) \boldsymbol{R}_{i, r_1}\right]^{\dagger} \boldsymbol{R}_{i, r_1} \boldsymbol{g}_t(k) ; 6) 与r2阶领域顶点交换信息[dt, i(k)]j，并计算
\left[\boldsymbol{d}_t(k)\right]_i=\sum\limits_{j \in V_{i, r_2}}\left[\boldsymbol{d}_{t, j}(k)\right]_i /\left|V_{i, r_2}\right| ; 7) 计算[xt(k+1)]i=[xt(k)]i+[dt(k)]i；
直到满足迭代终止条件。
8) 输出数据\left[\widetilde{\boldsymbol{x}}_t\right]_i。
在分布式近似牛顿算法的每次循环中，各节点需先与1阶领域顶点通信一次，计算梯度[gt(k)]i，然后与r1阶领域顶点通信一次，计算局部牛顿步长dt, i(k)，再与r2阶领域顶点通信一次，计算近似牛顿步长[dt(k)]i，最后完成迭代。大量仿真结果表明，在空时信号在线重构问题中，参数选取为r1=r2=1时，该近似牛顿算法已经拥有足够快的收敛速度。
3. 仿真结果与分析
通过实验对比本算法(参数选取为r1=r2=1的分布式近似牛顿算法)与文献[10]算法在空时信号在线重构任务中的性能。仿真数据集选用人工合成数据集和海平面温度数据集。在对比最大迭代次数K充足情况下的算法性能时，性能评价指标设置为相对误差：
E_{\mathrm{R}}=\frac{\left\|\boldsymbol{x}_t(k)-\boldsymbol{x}_t^*\right\|_2}{\left\|\boldsymbol{x}_t(0)-\boldsymbol{x}_t^*\right\|_2} \text { 。 } (22) 由于实际采用的在线算法通常在每个较短的信号观测区间内最大迭代次数受限，还需对比最大迭代次数K受限情况下的算法性能，此时性能评价指标设置为累积重构误差：
E_{\mathrm{CT}}=\frac{1}{T \sqrt{N}} \sum\limits_{t=1}^T\left\|\widetilde{\boldsymbol{x}}_t-\boldsymbol{x}_{t, \mathrm{o}}\right\|_{2}。 (23) 2种算法的迭代终止条件均设置为
\frac{\left\|\boldsymbol{x}_t(k)-\boldsymbol{x}_t(k-1)\right\|_2}{\left\|\boldsymbol{x}_t(k-1)\right\|_2} \leqslant 10^{-4}, (24) k \geqslant K_{\circ} (25) 实验1 使用MATLAB图信号处理工具箱GSPbox[21]构建一个100顶点的随机传感图，以模拟现实中的无线传感器网络，其拓扑结构如图 1所示。根据构建出的图随机生成一组100个顶点、100个时刻的差分平滑时变图信号。图信号生成方式为：先随机生成一个能量为‖x1, o‖22=104的低频图信号，作为时变信号在第1个时刻的初始信号值，再不断通过
\boldsymbol{x}_{t, \mathrm{o}}=\boldsymbol{x}_{t-1, \mathrm{o}}+\boldsymbol{L}^{-1 / 2} \boldsymbol{\delta}_t 生成下一时刻的图信号。这里扰动δt是一个零均值的高斯白噪声向量，用来控制信号的变化量，以保证合成的时变图信号的随机性。扰动δt的能量为‖δt‖22=1.3，从而保证了合成信号满足差分平滑性。对合成的图信号添加噪声，并进行采样，以模拟空时信号实际观测数据部分缺失的场景。图信号在各顶点的观测噪声nt设置为独立同分布的高斯白噪声，其方差为0.01，均值为0。采样方式设置为在各顶点、各时刻独立同分布的随机采样，采样概率为50%。
图 2为最大迭代次数充足条件下，单一时刻本算法(r1=r2=1)与文献[10]算法在重构任务中相对误差与算法迭代次数、通信代价的关系曲线。对于文献[10]算法，由于实验中优化问题的海森矩阵的条件数为72.3，是一个相对小的数，文献[10]算法可保持一个较快的收敛速度，但依然慢于本算法。因为收敛速度较慢，文献[10]算法达到相同误差精度所需通信量也比本算法高。
考虑迭代次数受限的情形，2种算法在整个时间段内的累积重构误差与在每个观测间隔[t－1, t]内最大迭代次数、最大通信量之间的关系如图 3所示。由图 3可见，当最大迭代次数较小，如K=1时，文献[10]算法由于收敛速度慢，无法在每个时刻t得到准确的重构信号，累积误差较大。作为对比，分布式近似牛顿算法对观测间隔内算法最大迭代次数的要求并不高，即使在K=1时，该算法的误差也很小，同时最大通信量需求也较小。
实验2 为了进一步证明分布式近似牛顿算法的有效性，对比此算法(r1=r2=1)与文献[10]算法对太平洋海平面温度数据的重构表现。数据集选取与文献[10]相同，为太平洋西经170°至90°，南纬60°至北纬10°传感器网络温度数据，其拓扑结构如图 4所示。
同样地，在最大迭代次数充足的条件下，2种算法在重构任务中相对误差与迭代次数、通信代价的关系曲线如图 5所示。实验中海森矩阵的条件数较大，为1 776，此时文献[10]算法的收敛速度变得极为缓慢，从而导致达到目标重构精度的通信需求大增，而分布式近似牛顿算法依然保持较快的收敛速度。迭代次数受限时，2种算法对比如图 6所示。由于收敛速度极慢，文献[10]算法无法在有限次迭代下得到有效精度的重构信号，而分布式近似牛顿算法依然有较好的重构效果。
4. 结束语
针对现有空时信号分布式在线重构算法收敛速度不稳定，且相对缓慢的问题，提出了一种基于近似牛顿法的空时信号分布式在线重构算法。通过子图划分求出图信号重构优化问题的局部解，再进行子图融合计算近似最优解，从而得到一个具有稀疏性的海森逆近似矩阵，最后将该近似矩阵代替至牛顿法迭代公式，推导出分布式近似牛顿法。仿真结果表明，分布式近似牛顿算法收敛速度更快，通信需求更低，且不易受优化问题条件数的影响，因此更适用于空时信号分布式在线重构任务。本研究主要是在已有优化模型的基础上进行算法的改进，后续将考虑设计新的空时信号在线重构模型，以进一步降低信号重构误差。
-
[1] ORTEGA A, FROSSARD P, KOVACEVIC J, et al. Graph signal processing: overview, challenges, and applications[J]. Proceedings of the IEEE, 2018, 106(5): 808-828. doi: 10.1109/JPROC.2018.2820126
[2] SANDRYHAILA, ALIAKSEI, MOURA, et al. Big data analysis with signal processing on graphs: representation and processing of massive data sets with irregular structure[J]. IEEE Signal Processing Magazine, 2014, 31(5): 80-90. doi: 10.1109/MSP.2014.2329213
[3] YICK J, MUKHERJEE, GHOSAL D, et al. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330. doi: 10.1016/j.comnet.2008.04.002
[4] LORENZO P D, BANELLI P, BARBAROSSA S, et al. Distributed adaptive learning of graph signals[J]. IEEE Transactions on Signal Processing, 2017, 65(16): 4193-4208. doi: 10.1109/TSP.2017.2708035
[5] 杨杰. 基于图信号处理的WSN数据异常检测与恢复[D]. 桂林: 桂林电子科技大学, 2019: 1-4. [6] 杨立山. 图信号采样与重建研究[D]. 北京: 北京邮电大学, 2018: 9-12. [7] 韩墨. 图信号的采样与重构理论研究[D]. 哈尔滨: 哈尔滨工业大学, 2017: 1-4. [8] SHUMAN D I, NARANG S K, FROSSARD P, et al. The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE Signal Processing Magazine, 2013, 30(3): 83-98. doi: 10.1109/MSP.2012.2235192
[9] SANDRYHAILA A, MOURA J. Discrete signal processing on graphs[J]. IEEE Transactions on Signal Processing, 2013, 61(7): 1644-1656. doi: 10.1109/TSP.2013.2238935
[10] QIU K, MAO X H, SHEN X Y, et al. Time-varying graph signal reconstruction[J]. IEEE Journal of Selected Topics in Signal Processing, 2017, 11(6): 870-883. doi: 10.1109/JSTSP.2017.2726969
[11] MAO X H, QIU K, LI T J, et al. Spatio-temporal signal recovery based on low rank and differential smoothness[J]. IEEE Transactions on Signal Processing, 2018, 66(23): 6281-6296. doi: 10.1109/TSP.2018.2875886
[12] BOYD S, VANDENBERGHE L. Convex optimization[M]. Cambridge: Cambridge University Press, 2004: 466-509.
[13] JAKOVETIC D, XAVIER J, MOURA J M F. Fast distributed gradient methods[J]. IEEE Transactions on Automatic Control, 2014, 59(5): 1131-1146. doi: 10.1109/TAC.2014.2298712
[14] MOKHTARI A, LING Q, RIBEIRO A. Network Newton distributed optimization methods[J]. IEEE Transactions on Signal Processing, 2017, 65(1): 146-161. doi: 10.1109/TSP.2016.2617829
[15] EISEN M, MOKHTARI A, RIBEIRO A. Decentralized Quasi-Newton methods[J]. IEEE Transactions on Signal Processing, 2017, 65(10): 2613-2628. doi: 10.1109/TSP.2017.2666776
[16] NARANG S K, GADDE A, SANOU E, et al. Localized iterative methods for interpolation in graph structured data[C]//IEEE Global Conference on Signal and Information Processing. Piscataway, NJ: IEEE Press, 2013: 491-494.
[17] NOCEDAL J, WRIGHT S J. Numerical Optimization[M]. New York: Springer Science and Business Media, 2006: 41-47.
[18] JIANG J Z, CHENG C, SUN Q Y. Nonsubsampled graph filter banks: theory and distributed algorithms[J]. IEEE Transactions on Signal Processing, 2019, 67(15): 3938-3953. doi: 10.1109/TSP.2019.2922160
[19] JIANG J Z, TAY D B. Decentralised signal processing on graphs via matrix inverse approximation[J]. Signal Processing, 2019, 165(22): 292-302.
[20] CHENG C, JIANG Y C, SUN Q Y. Spatially distributed sampling and reconstruction[J]. Applied and Computational Harmonic Analysis, 2019, 47(1): 109-148. doi: 10.1016/j.acha.2017.07.007
[21] PERRAUDIN N, PARATTE J, SHUMAN D, et al. GSPBOX: a toolbox for signal processing on graphs[EB/OL]. (2016-03-15)[2021-03-20]. https://arxiv.org/pdf/1408.5781.pdf.
下载:
计量
- 文章访问数: 597
- HTML全文浏览量: 574
- PDF下载量: 3567
