Graph Band-limited Signals Reconstruction Method Based Graph Spectral Domain Shifting
-
摘要: 针对带限图信号的重构问题, 本文提出了基于图谱域移位的带限图信号重构模型, 该模型将图带限分量的恒等不变特性建模为最小二乘问题. 基于所提出的重构模型, 本文设计了基于谱移位的重构算法和基于残差谱移位的重构算法. 相比于其他重构算法, 两种新算法提升了迭代效率和重构精度. 此外, 本文算法还适用于分段带限图信号的重构问题, 并且具有良好的迭代效率和重构精度.通过实验仿真表明, 相比于目前其他的带限图信号重构算法, 新算法的迭代效率提升约70%和重构精度提升约60%.Abstract: Aiming at the problem of graph band-limited signals reconstruction, a novel reconstruction model based shift strategy in graph spectral domain is proposed in this paper, and it models the identity invariance of graph spectral band-limited components as a least-square problem. For solving the established reconstruction model, two novel reconstruction methods are proposed based on spectral shift operator and residual spectral shift operator. Compared with other methods, the novel methods improve iteration efficiency and reconstruction accuracy. Besides, the novel methods are suitable for the problem of separate band-limited graph signals reconstruction and have good performances. The simulation shows that compared with other reconstruction methods of band-limited graph signals, the novel methods improve about seventy percent in iterative efficiency and sixty percent of reconstruction accuracy.
-
Key words:
- Graph signal processing /
- signal reconstruction /
- graph spectral theory /
- shift operator
-
随着信息技术的高速发展, 各领域中所产生的数据维度正在以前所未有的速度增长, 例如社交网络数据、金融交易数据和城市交通流量数据等.
然而, 传统的数据表征方法无法适用于具有复杂关联特征的网络数据集. 所以, 图网络[1]——一种非规则域中用于表征关联数据的模型应运而生. 如何更好地分析这些基于图网络表征的数据集, 从而更加高效地挖掘数据集的深度信息成为当下研究的热点问题之一.
近年来, 随着图信号处理的兴起和发展, 图网络中的信号(数据)分析与处理引起了研究者们的广泛关注. 图信号处理是将传统的信号处理理论衍生至基于图网络表征的非规则域信号处理理论[2]. 目前,图信号处理的理论研究主要包括图滤波器(组)的设计[3]、图信号采样/恢复[4]、图信号压缩[5]和图拓扑学习[6]等. 相关的应用研究有传感网络中的异常数据检测[7]及修复[8], 基于图数据的机器学习等[9-10]. 然而, 目前该研究领域中仍然存在着许多亟待探索和解决的理论问题和应用瓶颈[11]. 例如, 图信号处理中尚未出现类似于奈奎斯特采样定理的统一采样理论[12]. 相关的挑战还包括图信号的大规模分布式计算[13]、异构网络中的图信号处理[14]、如何融合多尺度下的图信号特征而进行信号多分辨分析[15], 以及如何分析张量图网络中的多层图数据之间的关联性[16]等. 随着图信号处理的不断发展, 必将成为有效应对数据泛滥现象和降低数据冗余的重要工具, 并为网络数据的高效处理提供理论支撑.
由于存在图网络的拓扑结构复杂多变以及数据维度带来的计算消耗大的问题, 如何利用尽可能少的采样节点信号和网络拓扑信息更加高效和完备地表征未采样节点信号, 从而为网络数据的传输和处理提供高效的技术支撑是图信号处理中的核心问题[17]. 在图信号重构的相关研究中, 由于带限图信号重构问题可作为其他类型图信号重构问题的源问题进行相关推广; 如何设计高效的带限图信号重构算法是一个重要的研究课题, 它为设计平滑图信号重构算法和实际网络数据重构方法提供了理论基础.
基于Papoulis-Gerchberg信号重构算法[18], Narang等[19]提出一种基于空域迭代图滤波的信号重构方法(Iteration least square reconstruction, ILSR). 该方法通过将采样信号和每次迭代后产生的采样信号残差进行累加后, 再进行图谱域带限滤波处理, 从而达到重构目的. 在ILSR重构算法的基础上, Wang等[20]提出了基于迭代加权策略的信号重构算法(Iteration weighting reconstruction, IWR)和基于迭代传播策略的信号重构算法(Iteration propagating reconstruction, IPR), 两种算法优于ILSR算法的原因在于对采样节点进行了残差滤波处理. 在IWR算法中, Wang等[20]首先将采样信号的残差扩大相应的权重, 然后进行图滤波处理; 而在IPR算法中, 首先是基于预先划分好的局部集将采样节点的信号残差传递给相邻的未采样节点, 然后进行图滤波处理. 由于两种算法在每步迭代中加入了对于采样信号残差的处理, 增大了未采样信号在插值过程中的增量, 进而提高了重构的效率和精度. 为了进一步地提高对于残差信号的估计精度, Yang等[21]提出了基于扩散算子的迭代重构算法(Iteration graph reconstruction based diffusion operator, IGDR). IGDR算法修正了IWR和IPR算法中由于采样信号残差在局部集内均匀传递而导致的过平滑现象, 在每步迭代中基于局部扩散算子和全局扩散算子对信号采样进行了联合处理, 使得迭代滤波得到的未采样信号为图带限滤波信号和残差扩散信号的总和. 不同于IWR、IPR和IGDR算法聚焦于迭代残差信号的处理方法, Brugnoli等[22]同样在ILSR算法的基础上提出了基于最优参数的Papoulis-Gerchberg信号迭代重构算法(Optimal Papoulis-Gerchberg iterative reconstruction, O-PGIR), 该算法通过在每步迭代中设置松弛参数的最优解而达到较高的迭代效率.
不同于基于空域滤波的重构算法研究, 为了完善图信号谱域理论框架及提升图信号的谱域特征分析能力, 基于图傅里叶变换的图谱域重构算法同样是近年来的研究热点.
Tseng等先后提出基于压缩感知的硬阈值截断图谱域重构算法[23]和基于图傅里叶变换的图谱域重构算法[24]. 在硬阈值截断图谱域重构算法中,作者首先将图信号重构问题转化为图谱域中的稀疏优化问题, 然后采用经典压缩感知理论中的基追踪算法和正交匹配算法或迭代硬阈值截断法分别进行求解. 通过上述方法估计出未采样图信号在图谱域中的频率分量, 最后基于图傅里叶逆变换将估计的频率分量转换为空域图信号. 在正交匹配算法的基础上作者又提出了基于图傅里叶变换的信号重构算法; 在正交匹配算法中, 完整频率分量是通过逐步重构出每个图频率分量值而实现的. 而在基于图傅里叶变换的信号重构算法中, 作者通过重构出小于截止图频率内的频率分量值实现信号重构. 该算法实质上是将ILSR算法转化到图频域进行处理. 然而, 两种方法并没有针对低通带限图信号的谱域特性进行更深入的分析, 只是将空域重构算法转化到变换域进行.
本文首先基于图傅里叶变换的分块矩阵形式和图带限信号特性分析得出图带限分量的恒等不变性. 基于该特性, 本文将重构问题建模为一个最小二乘模型. 本文所提出的重构模型是根据图高频部分的恒等关系, 相比于基于图低频段相似性的ILSR重构模型, 更加能够准确地表征信号的图谱域带限特性, 提高了重构精度. 此外, 由于根据重构模型而设计的迭代算法采用拟牛顿法进行求解, 在避免海森矩阵求解的同时高效利用了模型的二阶梯度信息, 相比于ILSR和O-PGIR提高了迭代效率. 而在基于残差信号的重构算法中, 本文根据残差信号同样具备图带限分量的恒等不变性, 设计了一种基于残差谱移位的重构算法. 相比于IWR/IPR和IGDR算法, 本文算法具有较好的重构性能. 此外, 由于本文提出的图带限分量的恒等不变性不需要考虑带限频率所在的频段, 所以针对分段带限图信号的重构问题同样适用, 并且具有良好的重构性能.
1. 基于谱移位的重构算法
图信号是指定义在具有网络拓扑结构中的信号集合, 其拓扑结构采用图模型
$G = (V{\rm{, }}\;E{\rm{, }}\;{\boldsymbol{W}})$ 进行表征. 其中, 节点集为$V = \{ {v_1}, \cdot \cdot \cdot ,{v_N}\} $ .$E = \{ e(i,j)\} $ 是图模型中的边集合,$e(i,j)$ 表示节点${v_i}$ 和节点${v_j}$ 之间有边相连. 信号${\boldsymbol{f}} = \{ f(i)\} \in {{\mathbf{R}}^N},$ 其中$f(i)$ 为图模型${{G}}$ 中节点${v_i}$ 上的信号值. 邻接矩阵${\boldsymbol{W}} = $ $ \{ w(i,j)\} \in {{\mathbf{R}}^{N \times N}}$ 用于表征节点之间的相关性,${\boldsymbol{W}}$ 中的元素$w(i,j)$ 如式(1)所示.$$w(i,j) = \left\{ {\begin{aligned} &1,\;\;\;\;{e(i,j) \in {{E}}}\\ &0,\;\;\;\;{\text{其他}} \end{aligned}} \right.$$ (1) 由矩阵
${\boldsymbol{W}}$ 可得到图拉普拉斯矩阵${\boldsymbol{L}} = {\boldsymbol{D}} - {\boldsymbol{W}}$ 和归一化图拉普拉斯矩阵${{\boldsymbol{L}}_{{Nor}}} = {{\boldsymbol{D}}^{ - 1/2}}{\boldsymbol{L}}{{\boldsymbol{D}}^{ - 1/2}}$ , 其中的度矩阵定义为${\boldsymbol{D}} = {\rm{diag}}\{ {d_i}\}$ ,对角线元素${d_i}$ 为邻接矩阵中第$i$ 行元素之和. 通过对归一化图拉普拉斯矩阵${{\boldsymbol{L}}_{Nor}}$ 进行特征值分解, 得到特征向量矩阵${\boldsymbol{U}} = [{{\boldsymbol{u}}_1}\;\cdots\;{{\boldsymbol{u}}_N}]$ 和与其对应的特征值矩阵${\boldsymbol{\Lambda }} = $ $ {\rm{diag}} \{ {\lambda _1},\cdots,{\lambda _N}\}$ .在图信号处理理论中, 图傅里叶变换对建立了图信号在空间域和图谱域之间的联系, 从谱聚类的角度分析和处理图信号[25]. 其正变换和逆变换分别如式(2)和式(3)所示, 其中
${\boldsymbol{f}}$ 和${\tilde{\boldsymbol f}}$ 分别表示空域信号和图频率分量.$${\tilde{\boldsymbol f}} = {{\boldsymbol{U}}^{\rm{T}}}{\boldsymbol{f}}$$ (2) $${\boldsymbol{f}} = {\boldsymbol{U\tilde f}}$$ (3) 根据图傅里叶变换对的定义, 图带限信号(Band-limited graph signals)
${{\boldsymbol{f}}_{BLG}} \in P{W_\omega }$ 的定义为: 当${\lambda _i} > \omega $ 时,${{\tilde{\boldsymbol f}}_{BLG}}(i) = 0$ ; 其中$\omega $ 为带限图信号${{\boldsymbol{f}}_{BLG}}$ 的截止图频率. 如图1所示, 图1(a)为空间域中节点信号的分布图; 下层为图信号的拓扑结构, 上层为将各节点信号连接而成的平面图. 图1(b)表示的是图信号经过图傅里叶变换后得到的图谱域示意图; 在其图谱域示意图中, 其高频段的图频率分量为零. 由于在图信号重构问题中, 如何设计采样策略同样对于能否实现精确重构有着一定的影响. 在本文中将采用基于重构唯一性条件而设计采样策略. 在满足该条件的情况下, 任意的带限图信号均可实现精确重构. 图截止频率($\omega $ )的重构唯一性的条件为[26]: 当带限图信号${{\boldsymbol{f}}_{BLG}} \in P{W_\omega }$ 的截止图频率${\omega ^2} \leq \eta$ 时, 从任意的采样节点集合重构得到的带限图信号具有唯一性. 其中$\eta $ 是关于${\boldsymbol{L}}_{Nor}^ *$ 的最小特征值,${\boldsymbol{L}}_{Nor}^ *$ 是由${{\boldsymbol{L}}_{Nor}}^2$ 中对应于未采样节点集合的行和列而构成的子矩阵.本文所研究的是带限图信号重构问题,即是在已知图信号
${\boldsymbol{f}}$ 的先验信息 —图带限特性$({\boldsymbol{f}} \in $ $ P{W_\omega })$ 和采样信号${\boldsymbol{f}}(S)$ 的情况下, 如何重构得到未采样信号${\boldsymbol{f}}({S^c})$ .采样矩阵${{\boldsymbol{P}}_S} = {\rm{diag}}\{ {{\boldsymbol{1}}_S}\} \in {{\mathbf{R}}^{N \times N}}$ (对应于采样节点的主对角线元素为1,其余为0). 本文定义带限图信号的带宽为$B$ , 即共有$B$ 个${\lambda _i} \leq \omega$ , 采样节点个数为$M$ , 未采样节点个数为$N - M .$ 若将图信号
${\boldsymbol{f}}$ 中的采样信号${\boldsymbol{f}}(S)$ 和未采样信号${\boldsymbol{f}}({S^c})$ 进行适当的重新排序后可得图信号${\boldsymbol{f}} = $ $ {[{\boldsymbol{f}}^{\rm{T}}{(S)}{\boldsymbol{\Phi }}^{\rm{T}}{(S)}{\rm{ }}\quad\Phi^{\rm{T}} {({S^c})}{\boldsymbol{f}}^{\rm{T}}{({S^c})}]^{\rm{T}}}, $ 其中${\boldsymbol{\Phi }}(S) \in {{\mathbf{R}}^{M \times N}}$ 是由${{\boldsymbol{P}}_{\rm{S}}}$ 中$M$ 个非全零的行向量而构成,${\boldsymbol{\Phi }}({S^c}) \in $ $ {{\mathbf{R}}^{(N - M) \times N}}$ 是由$({\boldsymbol{I}} - {{\boldsymbol{P}}_{\rm{S}}})$ 中$N - M$ 个非全零行向量组成.图傅里叶变换对的分块矩阵表示形式如式(4)和式(5)所示.
${{\boldsymbol{U}}_L}(S) \in {{\mathbf{R}}^{M \times B}}$ 和${{\boldsymbol{U}}_L}({S^c}) \in $ $ {{\mathbf{R}}^{(N - M) \times B}}$ 分别由矩阵${\boldsymbol{U}}$ 的子矩阵$[{{\boldsymbol{u}}_1}\;\cdots\;{{\boldsymbol{u}}_B}]$ 中对应于采样节点和未采样节点的行向量所构成的子矩阵; 子矩阵${{\boldsymbol{U}}_H}(S)$ 和${{\boldsymbol{U}}_H}({S^c})$ 分别是由${\boldsymbol{U}}$ 的子矩阵$[{{\boldsymbol{u}}_{B + 1}}\;\cdots\;{{\boldsymbol{u}}_N}]$ 中对应于采样节点和未采样节点的行向量所构成的子矩阵.${{\tilde{\boldsymbol f}}_L} \in {{\mathbf{R}}^B}$ 和${{\tilde{\boldsymbol f}}_H} \in {{\mathbf{R}}^{(N - B)}}$ 分别表示对应于前$B$ 个图频率分量(图低频分量)和第$(B + 1)$ 至第$N$ 个图频率分量(图高频分量).$$\begin{split} \left[ \begin{array}{l} {{{\tilde{\boldsymbol f}}}_L} \\ {{{\tilde{\boldsymbol f}}}_H} \end{array} \right] = \left[ \begin{array}{l} {{\boldsymbol{U}}^{\rm{T}}_L}{(S)}{\rm{ }}\;\quad{{\boldsymbol{U}}^{\rm{T}}_L}{({S^c})} \\ {{\boldsymbol{U}}^{\rm{T}}_H}{(S)}{\rm{ }}\quad{{\boldsymbol{U}}^{\rm{T}}_H}{({S^c})} \end{array} \right]\left[ \begin{array}{l} \Phi (S){\boldsymbol{f}}(S) \\ \Phi ({S^c}){\boldsymbol{f}}({S^c}) \end{array} \right] \end{split}$$ (4) $$ \left[ \begin{array}{l} {\Phi(S)}{\boldsymbol{f}}(S) \\ {\Phi ({S^c})}{\boldsymbol{f}}({S^c}) \end{array} \right] = \left[ \begin{array}{l} {{\boldsymbol{U}}_L}(S){\rm{ }}\;\,\quad{{\boldsymbol{U}}_H}(S) \\ {{\boldsymbol{U}}_L}({S^c}){\rm{ }}\quad{{\boldsymbol{U}}_H}({S^c}) \end{array} \right]\left[ \begin{array}{l} {{{\tilde{\boldsymbol f}}}_L} \\ {{{\tilde{\boldsymbol f}}}_H} \end{array} \right] $$ (5) 在ILSR算法中[19], Narang等根据图带限特性——
${{\tilde{\boldsymbol f}}_H} = {\mathbf{0}}$ , 将式(5)表示为式(6). 该算法的重构准则是通过中间变量——带限图信号的低频分量${{\tilde{\boldsymbol f}}_L}$ 恒定, 建立了采样信号${\boldsymbol{f}}(S)$ 和未采样信号${\boldsymbol{f}}({S^c})$ 之间的联系, 得到重构信号的闭式解, 如式(6)所示.$$\begin{split} {\boldsymbol{f}}({S^c}) =\;&\Phi^{\rm{T}} ({S^c}){{\boldsymbol{U}}_L}({S^c}){[{{\boldsymbol{U}}^{\rm{T}}_L}{(S)}{{\boldsymbol{U}}_L}(S)]^{ - 1}}\times \\ &{{\boldsymbol{U}}^{\rm{T}}_L}{(S)}\Phi (S){\boldsymbol{f}}(S) \end{split} $$ (6) 与ILSR算法的重构准则不同, 本文提出的重构准则是基于采样信号的高频分量和未采样信号的图高频分量之和为零; 即图带限分量的恒等不变性, 如式(7)所示. 根据此特性, 可得重构信号
${\boldsymbol{f}}({{{S}}^c})$ 的闭式解, 如式(8)所示.$$ {{\tilde{\boldsymbol f}}_H} = [{{\boldsymbol{U}}^{\rm{T}}_H}{(S)}{\rm{ }}\quad{{\boldsymbol{U}}^{\rm{T}}_H}{({S^c})}]\left[ \begin{array}{l} {\Phi (S)}{\boldsymbol{f}}(S) \\ {\Phi ({S^c})}{\boldsymbol{f}}({S^c}) \end{array} \right] $$ (7) $$ \begin{split} {\boldsymbol{f}}({S^c}) =\;& - \Phi^{\rm{T}} {({S^c})}{[{{\boldsymbol{U}}_H}({S^c}){{\boldsymbol{U}}^{\rm{T}}_H}{({S^c})}]^{ - 1}} \times\\ &{{\boldsymbol{U}}_H}({S^c}){{\boldsymbol{U}}^{\rm{T}}_H}{(S)}\Phi (S){\boldsymbol{f}}(S) \end{split} $$ (8) 然而, 由于闭式解中涉及到矩阵逆运算, 导致求解的计算开销大. 尤其是当处理大规模图网络数据时, 计算和存储的成本都较高. 为了避免此问题, 本文基于图带限分量的恒等不变性提出如式(9)所示的重构模型, 采用迭代求解实现重构带限图信号的目的. 该模型的目标函数利用了图带限分量的恒等不变性, 将其建模为最小二乘模型. 进而估计出未采样信号
${\boldsymbol{f}}({S^c})$ .$$ \begin{split} & \mathop {{\rm{min}}}\limits_{{\boldsymbol{f}}({S^c})} {\rm{ }}\left\| {{\boldsymbol{Y}} - {{\boldsymbol{U}}^{\rm{T}}_H}{{({S^c})}}\Phi ({S^c}){\boldsymbol{f}}({S^c})} \right\|_2^2 \\ & {\rm{ }}{\rm{s.t}}\;\;\;{\rm{ }}{\boldsymbol{Y}} = - {{\boldsymbol{U}}^{\rm{T}}_H}{(S)}\Phi (S){\boldsymbol{f}}(S) \end{split} $$ (9) 通过设计该重构模型的求解算法, 本文提出了基于谱移位的带限图信号重构算法(Reconstruction algorithm of band-limited graph signals based graph frequency shifting, BGSR-GFS). BGSR-GFS算法流程如算法1所示.
算法 1. BGSR-GFS算法
输入.
${{\boldsymbol{U}}_1} = {{\boldsymbol{U}}_H}({S^c}){{\boldsymbol{U}}^{\rm{T}}_H}{({S^c})},$ $\sigma, $ $\Phi (S)$ $\Phi ({S^c}),$ ${\boldsymbol{f}}(S),$ $K,$ ${{\boldsymbol{U}}_2} = {{\boldsymbol{U}}_{{H}}}({S^c}){{\boldsymbol{U}}^{\rm{T}}_{{H}}}{(S)}$ 输出.
${{\boldsymbol{f}}_{{R}}}({S^c})$ 初始化.
${\boldsymbol{f}}({S^c}) = {\mathbf{0}},$ ${{\boldsymbol{H}}^{(1)}} = {\bf {I}},$ $k = 1$ ${{\boldsymbol{G}}^{(1)}} = {{\boldsymbol{U}}_2}{\boldsymbol{\Phi }}(S){\boldsymbol{f}}(S)$ 当
$k \leq K,$ 则:步骤 1.
${{\boldsymbol{d}}^{(k)}} = - {{\boldsymbol{H}}^{(k)}}{{\boldsymbol{G}}^{(k)}}$ ;步骤 2.
${\alpha ^{(k)}} = \frac{{{({\boldsymbol{G}}^{(k)})}^{{\rm{ T}}}{{\boldsymbol{d}}^{(k)}}}}{{{({\boldsymbol{d}}^{(k)})}^{{\rm{ T}}}{{\boldsymbol{U}}_1}{{\boldsymbol{d}}^{(k)}}}}$ ;步骤 3.
${\boldsymbol{f}}^{(k + 1)}{({S^c})} = {\boldsymbol{f}}^{(k)}{({S^c})} + {\alpha ^{(k)}}{{\boldsymbol{d}}^{(k)}} ;$ 步骤 4.
${{\boldsymbol{G}}^{(k + 1)}} = {{\boldsymbol{U}}_1}{\boldsymbol{f}}^{(k + 1)}{({S^c})} + {{\boldsymbol{G}}^{(1)}}$ ;步骤 5.
${{\boldsymbol{p}}^{(k)}} = {\boldsymbol{f}}^{(k + 1)}{({S^c})} - {\boldsymbol{f}}{({S^c})^{(k)}}$ ;步骤 6.
${{\boldsymbol{q}}^{(k)}} = {{\boldsymbol{G}}^{(k + 1)}} - {{\boldsymbol{G}}^{(k)}}$ ;步骤 7.
$$\Delta {{\boldsymbol{H}}^{(k)}} = \frac{{{{\boldsymbol{p}}^{(k)}}{({\boldsymbol{p}}^{(k)})}^{\rm{T}}}}{{{({\boldsymbol{p}}^{(k)})}^{\rm{T}}{{\boldsymbol{q}}^{(k)}}}} - \frac{{{{\boldsymbol{H}}^{(k)}}{{\boldsymbol{q}}^{(k)}}{({\boldsymbol{q}}^{(k)})}^{\rm{T}}{{\boldsymbol{H}}^{(k)}}}}{{{({\boldsymbol{p}}^{(k)})}^{\rm{T}}{{\boldsymbol{H}}^{(k)}}{{\boldsymbol{q}}^{(k)}}}}$$ 步骤 8.
${{\boldsymbol{H}}^{(k + 1)}} = {{\boldsymbol{H}}^{(k + 1)}} + \Delta {{\boldsymbol{H}}^{(k)}} ;$ 步骤 9. 若
$\big\| {{\boldsymbol{f}}^{(k + 1)}{{({S^c})}} - {\boldsymbol{f}}^{(k)}{{({S^c})}}}\big\|_2^2$ , 小于门限阈值$\sigma $ 或达到最大迭代次数$K\,(k > K)$ , 则终止迭代, 输出参数${\boldsymbol{f}}{({S^c})^{(k + 1)}},$ 否则, 继续迭代, 跳转至步骤1;步骤 10.
${{\boldsymbol{f}}_{{R}}}({S^c}) = {\boldsymbol{f}}^{(k + 1)}{({S^c})}$ .该重构算法基于拟牛顿法进行迭代求解. 在高效利用其重构模型二阶梯度信息的同时, 避免了海森矩阵的求解.
当且仅当
${{\boldsymbol{U}}^{\rm{T}}_H}{({S^c})}$ 满足其行数大于等于列数时, 该最小二乘问题有唯一解. 可知BGSR-GFS重构算法的适用条件为图信号具有带限特性且带宽$B$ 小于等于采样节点个数$M$ .2. 基于残差谱移位的重构算法
由于ILSR重构算法并没有对迭代过程中的残差信号进行分析和处理, 所以无论在还是迭代效率上都较为有限. 因此, 针对如何根据迭代残差信号的相关特性提升和迭代效率, 研究者们先后提出了IPR/IWR[20]和IGDR重构算法[21]. 此类基于残差估计的重构算法的关键在于如何根据采样节点的残差信号
${{\boldsymbol{f}}^{(k)}_{{{\rm{Re}}{\rm{s}}}}}(S)$ 估计未采样节点的残差信号${{\boldsymbol{f}}^{(k)}_{{{\rm{Re}} {\rm{s}}}}}({S^c})$ .基于残差估计的重构算法的迭代步骤归纳为公式(10), 不同算法之间的差异在于如何更好地估计采样残差信号
${{\boldsymbol{f}}^{(k)}_{{\rm{Re}} {\rm{s}}}}{(S)}$ 和未采样残差信号${{\boldsymbol{f}}^{(k)}_{{\rm{Re}} {\rm{s}}}}{({{\rm{S}}^c})}$ .$$ \begin{split} {{\boldsymbol{f}}^{(k + 1)}} = \;&\Phi^{\rm{T}} {({S^c})}{\boldsymbol{U}}^{{S^c}}_L\Phi ({S^c}){\boldsymbol{f}}^{(k)}{({S^c})} + \\ &\Phi^{\rm{T}}{(S)}{\boldsymbol{U}}^S_L\Phi (S){\boldsymbol{f}}^{(k)}{(S)} +\\ & {{\boldsymbol{f}}^{(k)}_{{{\rm{Re}}{\rm{s}}}}}{({S^c})} + {{\boldsymbol{f}}^{(k)}_{{{\rm{Re}} {\rm{s}}}}}{(S)} \end{split} $$ (10) $$ \begin{split} &{\boldsymbol{U}}_L^{{S^c}} = {{\boldsymbol{U}}_L}({S^c}){{\boldsymbol{U}}^{\rm{T}}_L}{({S^c})} \qquad\qquad\quad\quad \\ &{\boldsymbol{U}}_L^S = {{\boldsymbol{U}}_L}({S}){{\boldsymbol{U}}^{\rm{T}}_L}{(S)} \\ & {\boldsymbol{f}}^{(k)}{({{S}})} = ({\boldsymbol{I}} - {{\boldsymbol{P}}_S}){{\boldsymbol{f}}^{(k)}} \\ &{\boldsymbol{f}}^{(k)}{({{{S}}^c})} = {{\boldsymbol{P}}_S}{{\boldsymbol{f}}^{(k)}} \end{split} $$ (11) Wang等[20]基于局部聚合的处理方法, 提出了基于局部集采样的IPR和IWR重构算法. 在IWR重构算法中, 采样残差首先进行相应权重的扩大(权重矩阵
${{\boldsymbol{W}}_{{\rm{IPR}}}}$ ), 然后再进行图带限滤波, 如式(12)所示.$$ \begin{split} & {{\boldsymbol{f}}^{(k)}_{{\rm{Res}}}}{(S)} = \Phi^{\rm{T}} {(S)}{\boldsymbol{U}}_L^S\Phi (S) \times\\ &\qquad\qquad\;\;{{\boldsymbol{W}}_{{\rm{IPR}}}}[{\boldsymbol{f}}(S) - {\boldsymbol{f}}^{(k)}{(S)}] \\ & {{\boldsymbol{f}}^{(k)}_{{\rm{Res}}}}{({S^c})} = {\boldsymbol{0}} \end{split} $$ (12) 不同于IWR算法, IPR重构算法通过采样残差
${{\boldsymbol{f}}_{{\rm{Re}}{\rm{ s}}}}({{S}})$ 和网络拓扑特性, 估计未采样残差${{\boldsymbol{f}}_{{\rm{Re}} {\rm{s}}}}({{{S}}^c})$ . 具体而言, 首先是基于局部集内平滑特性, 将未采样残差设置为局部集内的采样残差, 然后再进行图带限滤波. 如式(13)所示, 其中${\boldsymbol{V}}({v_d})$ 为采样节点${v_d}$ 的未采样邻居节点集.$$\begin{split} &{{\boldsymbol{f}}^{(k)}_{{\rm{Res}}}}{(S)} = \Phi^{\rm{T}} {(S)}{\boldsymbol{U}}_L^S\Phi (S)[{\boldsymbol{f}}(S) - {\boldsymbol{f}}^{(k)}{(S)}] \\ &{{\boldsymbol{f}}^{(k)}_{{\rm{Res}}}}{({S^c})} = \Phi^{\rm{T}} {({S^c})}{\boldsymbol{U}}_L^{{S^c}}\Phi ({S^c})[{{{\boldsymbol{f}}^{{\rm{Prop}}}}{(S)}]^{(k)}} \\ & [{{{\boldsymbol{f}}^{{\rm{Prop}}}}{(S)}]^{(k)}}\{ {v_i}\} = {\boldsymbol{f}}(S)\{ {v_d}\} - {\boldsymbol{f}}^{(k)}{(S)}\{ {v_d}\} , \\ &\qquad\qquad\qquad\qquad\qquad\qquad\quad\forall {v_i} \in {\boldsymbol{V}}({v_d}) \end{split} $$ (13) 由于IPR/IWR算法在迭代过程中, 都对采样残差进行相应的预处理工作; 所以相比于ILSR算法, 两种算法的和迭代效率均有提升. 然而, 由于IWR和IPR重构算法对于未采样图信号的迭代残差估计是基于平滑准则, 导致会出现过平滑现象[27]. 为了缓解“过平滑” 问题, Yang等[21]提出基于局部扩散算子的IGDR重构算法, 如式(14)所示. 其中,
$J$ 为采样节点和未采样节点之间的最大跳数,${\delta _j}$ 表示与采样节点集$S$ 和未采样节点${v_j}$ 之间的最短路径相关的指示函数. IGDR算法通过将采样残差经过图带限滤波后得到的全局未采样残差${\boldsymbol{f}}_{{\rm{Re}}{\rm{ s}}}^G({S^c})$ 和采样残差基于随机游走策略得到的局部未采样残差${\boldsymbol{f}}_{{\rm{Re}} {\rm{s}}}^L({S^c})$ 相加, 得到最终的未采样残差${{\boldsymbol{f}}_{{\rm{Re}}{\rm{ s}}}}({S^c})$ .$$ \begin{split} & {{\boldsymbol{f}}^{(k)}_{{\rm{Res}}}}{(S)} = \Phi^{\rm{T}} {(S)}{\boldsymbol{U}}_L^S\Phi (S)[{\boldsymbol{f}}(S) - {\boldsymbol{f}}^{(k)}{(S)}] \\ & {{\boldsymbol{f}}^{(k)}_{{\rm{Res}}}}{({S^c})} = [{\boldsymbol{f}}_{{\rm{Re}} {\rm{s}}}^G{({S^c})]^{(k)}} + [{\boldsymbol{f}}_{{\rm{Re}} {\rm{s}}}^L{({S^c})]^{(k)}} =\\ & \qquad\qquad\qquad{{\boldsymbol{U}}_{\rm{H}}}({S^c}){{\boldsymbol{U}}_{\rm{H}}^{\rm{T}}{(S)}}[{\boldsymbol{f}}(S) - {\boldsymbol{f}}^{(k)}{(S)}]+ \\ & \qquad\qquad\qquad{{\boldsymbol{P}}_S}\sum\limits_{j = 1}^J {{\delta _j}{{\boldsymbol{D}}^{ - 1}}{{\boldsymbol{A}}^j}[{\boldsymbol{f}}(S) - {\boldsymbol{f}}^{(k)}{{(S)}}]} \end{split} $$ (14) 综上所述, IPR/IWR重构算法是基于图平滑滤波估计残差信号, 而IGDR算法是基于图带限特性的原则而设计的. 两种残差重构法都是基于重构信号的低频分量相似性而设计的, 对于高频分量缺乏相应的分析和处理, 导致迭代效率和相比于ILSR算法的提升有限.
根据ILSR算法以及凸集映射原理[18]可知, 在第
$k$ 次迭代中的信号${{\boldsymbol{f}}^{(k)}}$ 满足图带限特性[28]. 因为${{\boldsymbol{f}}^{(k)}}$ 满足图带限特性以及图傅里叶变换具有线性特征, 所以可知残差信号${\boldsymbol{f}}_{{\rm{Re}} s}^{(k)} = {\boldsymbol{f}} - {{\boldsymbol{f}}^{(k)}}$ 同样满足图带限分量的恒等不变性. 由此, 本文设计了一种基于残差谱移位的图信号重构模型, 如式(15)所示.$$ \begin{split} &{{\boldsymbol{f}}^{(k)}_{{\rm{Res}}}}{(S)} = \Phi^{\rm{T}} {(S)}{\boldsymbol{U}}_L^S{\Phi _S}[{\boldsymbol{f}}(S) - {\boldsymbol{f}}^{(k)}{(S)}] \\ & {{\boldsymbol{f}}^{(k)}_{{\rm{Res}}}}{({S^c})} = \Phi^{\rm{T}} {({S^c})}{{\boldsymbol{f}}^*} \\ &\mathop {\min }\limits_{{{\boldsymbol{f}}^ * }}\;\;{\rm{ }}\left\| {{\boldsymbol{Y}} - {{\boldsymbol{U}}^{\rm{T}}_H}{{({S^c})}}{{\boldsymbol{f}}^ * }} \right\|_2^2 \\ &{\rm{s.t}}\qquad{\rm{ }}{\boldsymbol{Y}} = - {{\boldsymbol{U}}^{\rm{T}}_H}{(S)}\Phi (S)[{\boldsymbol{f}}(S) - {\boldsymbol{f}}^{(k)}{(S)}]{\rm{ }} \end{split} $$ (15) 基于此重构模型, 本文提出基于残差谱移位的重构算法(Band-limited graph signals reconstruction based graph frequency shifting of residual signals, BGSR-GFS-R), 算法流程如算法2所示.
算法 2. BGSR-GFS-R算法
输入.
${{\boldsymbol{U}}_1} = {{\boldsymbol{U}}_H}({S^c}){{\boldsymbol{U}}^{\rm{T}}_H}{({S^c})},$ $K,$ $M$ 输出.
${{\boldsymbol{f}}_{{R}}}({S^c})$ .${{\boldsymbol{H}}_{{\rm{BL}}}} = {[{{\boldsymbol{U}}^{\rm{T}}_{{L}}}{(S)}{\rm{ }}\;\;\;{{\boldsymbol{U}}^{\rm{T}}_{{L}}}{(S^c)}]^{\rm{T}}}[{{\boldsymbol{U}}^{\rm{T}}_{{L}}}{(S)}{\rm{ }}\;\;\;{{\boldsymbol{U}}^{\rm{T}}_{{L}}}{(S^c)}]$ ${{\boldsymbol{U}}_2} = {{\boldsymbol{U}}_H}({S^c}){{\boldsymbol{U}}^{\rm{T}}_H}{(S)},$ $\Phi (S),$ $\Phi ({S^c}),$ ${\boldsymbol{f}}(S),$ ${{\boldsymbol{P}}_{{S}}},$ $\sigma $ 步骤 1. 初始化
$k = 1,$ ${{\boldsymbol{f}}^{(1)}} = {{\boldsymbol{H}}_{{\rm{BL}}}}{\boldsymbol{f}}(S)$ ;当
$k \leq K,$ 则:步骤 2.
${{\boldsymbol{f}}_{{\rm{Res}}}}(S) = {\boldsymbol{f}}(S) - {{\boldsymbol{P}}_S}{{\boldsymbol{f}}^{(k)}}$ ;步骤 3. 设置零向量
${{\boldsymbol{f}}^{(1)}_{{\rm{Res}}}}{({S^c})}$ , 单位矩阵${{\boldsymbol{H}}^{(1)}}$ ,${{\boldsymbol{G}}^{(1)}} = $ $ {{\boldsymbol{U}}_{\rm{2}}}{\boldsymbol{\Phi }}(S){{\boldsymbol{f}}_{{\rm{Res}}}}(S),$ 初始化$m=1 $ ;当
$m \leq M$ , 则:步骤 4.
${{\boldsymbol{d}}^{(m)}} = - {{\boldsymbol{H}}^{(m)}}{{\boldsymbol{G}}^{(m)}}$ ;步骤 5.
${\alpha ^{(m)}} = \frac{{{({\boldsymbol{G}}^{(m)})}^{{\rm{ T}}}{{\boldsymbol{d}}^{(m)}}}}{{{({\boldsymbol{d}}^{(m)})}^{{\rm{ T}}}{{\boldsymbol{U}}_1}{{\boldsymbol{d}}^{(m)}}}}$ ;步骤 6.
${{\boldsymbol{f}}^{(m + 1)}_{{\rm{Res}}}}{({S^c})} = {\boldsymbol{f}}^{(m)}{({S^c})} + {\alpha ^{(m)}}{{\boldsymbol{d}}^{(m)}}$ ;步骤 7.
${{\boldsymbol{G}}^{(m + 1)}} = {{\boldsymbol{U}}_1}{\boldsymbol{f}}^{(m + 1)}{({S^c})} + {{\boldsymbol{G}}^{(1)}}$ ;步骤 8.
${{\boldsymbol{p}}^{(m)}} = {{\boldsymbol{f}}^{(m + 1)}_{{\rm{Res}}}}{({S^c})} - {{\boldsymbol{f}}^{(m)}_{{\rm{Res}}}}{({S^c})}$ ;步骤 9.
${{\boldsymbol{q}}^{(m)}} = {{\boldsymbol{G}}^{(m + 1)}} - {{\boldsymbol{G}}^{(m)}}$ ;步骤 10.
$$\Delta {{\boldsymbol{H}}^{(m)}} = \frac{{{{\boldsymbol{p}}^{(m)}}{({\boldsymbol{p}}^{(m)})}^{\rm{T}}}}{{{({\boldsymbol{p}}^{(m)})}^{\rm{T}}{{\boldsymbol{q}}^{(m)}}}} - \frac{{{{\boldsymbol{H}}^{(m)}}{{\boldsymbol{q}}^{(m)}}{({\boldsymbol{q}}^{(m)})}^{\rm{T}}{{\boldsymbol{H}}^{(m)}}}}{{{({\boldsymbol{p}}^{(m)})}^{\rm{T}}{{\boldsymbol{H}}^{(k)}}{{\boldsymbol{q}}^{(m)}}}}$$ 步骤 11.
${{\boldsymbol{H}}^{(m + 1)}} = {{\boldsymbol{H}}^{(m + 1)}} + \Delta {{\boldsymbol{H}}^{(m)}}$ ;步骤 12. 若
$\big\| {{{\boldsymbol{f}}^{(m + 1)}_{{\rm{Res}}}}{{({S^c})}} - {{\boldsymbol{f}}^{(m)}_{{\rm{Res}}}}{{({S^c})}}} \big\|_2^2$ 小于门限阈值$\sigma $ 或达到最大迭代次数$M\,(m > M),$ 则终止迭代, 输出参数${{\boldsymbol{f}}^{(k + 1)}_{{\rm{Res}}}}{({S^c})},$ 否则, 继续迭代, 跳转至步骤4;步骤 13.
$[{{\boldsymbol{f}}^ * _{{\rm{Res}}}}{({S^c})}]^{(k)} = \Phi^{\rm{T}} {({S^c})}{{\boldsymbol{f}}^{(m + 1)}_{{\rm{Res}}}}{({S^c})}$ ;步骤 14.
${{\boldsymbol{f}}^{(k + 1)}} = {{\boldsymbol{H}}_{{\rm{BL}}}}{{\boldsymbol{f}}^{(k)}} + {{\boldsymbol{H}}_{{\rm{BL}}}}{{\boldsymbol{f}}_{{\rm{Res}}}}(S) + [{{\boldsymbol{f}}^ *_{{\rm{Res}}}}{({S^c}) }]^{(k)}$ 步骤 15. 若
$\left\| {{{\boldsymbol{f}}^{(k + 1)}} - {{\boldsymbol{f}}^{(k)}}} \right\|_2^2$ 小于门限阈值$\sigma $ 或达到最大迭代次数$K\,(k >K),$ 则终止迭代, 输出参数${{\boldsymbol{f}}^{(k + 1)}},$ 否则, 继续迭代, 跳转至步骤2;步骤 16.
${{\boldsymbol{f}}_{{R}}}({S^c}) = ({\boldsymbol{I}} - {{\boldsymbol{P}}_{{S}}}){{\boldsymbol{f}}^{(k + 1)}}$ .本文提出的BGSR-GFS-R重构算法基于迭代中的采样残差信号和谱移位策略, 估计得到未采样残差信号. 然后将未采样残差信号与经过带限图滤波后的未采样信号相加, 最终得到重构后的未采样信号. 相比于其他基于残差处理的重构算法(IWR/IPR和IGDR), 本算法对于残差信号的处理不依赖与图网络的子图集合. 并且, 由于本算法利用的是其残差信号的图带限分量的恒等不变性, 将其建模为最小二乘问题后进行迭代求解, 避免了“过平滑”现象.
由于其残差信号的图傅里叶变换的变换矩阵同样为
${{\boldsymbol{U}}^{\rm{T}}_{{H}}}{({S^c})} ,$ 所以要求矩阵${\boldsymbol{U}}_1={\boldsymbol{U}}_0({S^c}){\boldsymbol{U}}^{\rm{T}}_0({S^c})$ 为满秩矩阵, 即采样节点个数不小于带限信号的带宽.3. 分段带限图信号重构算法
在现有的图信号重构算法中, 所针对的图信号往往具备平滑或者是低频段受限的信号特征; 即各节点的信号值与其邻居节点的信号值差异较小, 在图谱域上呈现出能量较为集中在低频区域内. 除此以外, 由于在实际情况中由于物理设备及传输手段的限制, 采集得到的图信号中往往存在着少量的异常节点数据[7]. 将上述的数据集基于地理距离建模为图信号后, 本文发现由于其中存在着少量节点信号值与其邻居节点的信号值差异较大, 其在图谱域上所呈现的是类似于分段带限的信号特性, 如图2所示.
$$ \left[ \begin{array}{l} {{{\tilde{\boldsymbol f}}}_L} \\ {{{\tilde{\boldsymbol f}}}_0} \\ {{{\tilde{\boldsymbol f}}}_H} \end{array} \right] = \left[ \begin{array}{l} {{\boldsymbol{U}}^{\rm{T}}_L}{(S)}{\rm{ }}\quad{{\boldsymbol{U}}^{\rm{T}}_L}{({S^c})} \\ {{\boldsymbol{U}}^{\rm{T}}_0}{(S)}{\rm{ }}\quad{{\boldsymbol{U}}^{\rm{T}}_0}{({S^c})} \\ {{\boldsymbol{U}}^{\rm{T}}_H}{(S)}{\rm{ }}\quad{{\boldsymbol{U}}^{\rm{T}}_H}{({S^c})} \end{array} \right]\left[ \begin{array}{l} {\Phi (S)}{\boldsymbol{f}}(S) \\ {\Phi ({S^c})}{\boldsymbol{f}}({S^c}) \end{array} \right] $$ (16) 针对分段带限图信号的重构问题, 本文上述两种重构算法同样适用. 由
${{\tilde{\boldsymbol f}}_0} = {\mathbf{0}}$ , 可知分段带限图信号在图频率${\lambda _i} \in ({\omega _1},{\omega _2})$ 内, 同样满足图带限分量的恒等不变性, 如式(16)所示. 基于上述分析, 本文提出分段带限图信号重构的优化模型, 如式(17)所示.$$\begin{split} & \mathop {\min }\limits_{{\boldsymbol{f}}({S^c})} {\rm{ }}\left\| {{\boldsymbol{Y}} - {{\boldsymbol{U}}^{\rm{T}}_0}{{({S^c})}}\Phi ({S^c}){\boldsymbol{f}}({S^c})} \right\|_2^2 \\ &{\rm{ s}}{\rm{.t }}\;\;\;\;\;\;{\boldsymbol{Y}} = - {{\boldsymbol{U}}^{\rm{T}}_0}{(S)}\Phi (S){\boldsymbol{f}}(S) \end{split} $$ (17) 基于上述模型, 只需更改重构算法BGSR-GFS/BGSR-GFS-R中的部分输入变量, 便可实现分段带限图信号的重构. 具体而言, 在BGSR-GFS中更改的输入变量
${{\boldsymbol{U}}_1} = {{\boldsymbol{U}}_0}({S^c}){{\boldsymbol{U}}^{\rm{T}}_0}{({S^c})}$ /${{\boldsymbol{U}}_2} = {{\boldsymbol{U}}_0}({S^c}){{\boldsymbol{U}}^{\rm{T}}_0}{(S)}$ , 在GBSR-GFS-R算法中除了同样更新矩阵${{\boldsymbol{U}}_1}$ 和${{\boldsymbol{U}}_2}$ , 还需要将${{\boldsymbol{H}}_{{\rm{BL}}}}$ 更新为${\boldsymbol{H}}_{{\rm{BL}}}^ *$ .$${\boldsymbol{H}}_{{\rm{BL}}}^ * = \left[ \begin{array}{l} {{\boldsymbol{U}}_{{L}}}(S){\rm{ }}\;\;\;\;\;\,{{\boldsymbol{U}}_{{H}}}(S) \\ {{\boldsymbol{U}}_{{L}}}({S^c}){\rm{ }}\;\;\;\;{{\boldsymbol{U}}_{{H}}}({S^c}) \end{array} \right]\left[ \begin{array}{l} {{\boldsymbol{U}}^{\rm{T}}_{{L}}}{(S)}{\rm{ }}\;\;\;\,\;\;{{\boldsymbol{U}}^{\rm{T}}_{{H}}}{(S)} \\ {{\boldsymbol{U}}^{\rm{T}}_{{L}}}{({S^c})}{\rm{ }}\;\;\;\;{{\boldsymbol{U}}^{\rm{T}}_{{H}}}{({S^c})} \end{array} \right]$$ (18) 4. 实验仿真及分析
本文将BGSR-GFS和BGSR-GFS-R重构算法与4种重构算法(ILSR、O-PGIR、IPR和IGDR)进行对比. 由于IPR算法性能优于IWR算法,故实验中只对比了IPR算法; 其次, 由于GBSR-IHT和GBSR-GFT是将ILSR算法变换至图谱域上进行重构, 其迭代效率和ILSR算法一致, 故本文未将其加入对比算法. 本文的实验仿真是在3.40 GHz的Intel i7-6700处理器和16 GB RAM的个人计算机上运行, 使用的软件为MATLAB R2019b.
实验中采用的数据集分别为美国明尼苏达州交通网络(
${G_1}$ )和美国部分主要城市温度网络(${G_2}$ ), 如图3所示.${G_1}$ 是由2642个节点和6608条边构成的, 节点和边分别表示交通网中的十字路口和实际的州际公路[29];${G_2}$ 中的节点个数为218, 节点表示美国主要城市[30], 本文采用$K$ 近邻法构建节点之间的边连接$(K = 5).$ 数据集中的带限图信号是由服从高斯分布的随机信号经过带限图滤波后构成的. 数据集${G_1}$ 的截止频率为0.4077, 数据集${G_2}$ 的截止频率为0.3698. 迭代阈值$\sigma $ 设置为$1 \times {10^{ - 8}}$ .本文采用的采样策略为贪婪采样[20]和随机采样. 基于贪婪采样策略,
${G_1}$ 和${G_2}$ 分别得到的采样节点数为873和33, 如图3所示. 为了公平地比较各算法在不同采样情况下的重构效果, 仿真中随机采样的节点个数与贪婪采样一致. 本文采用重构信号和原始信号之间的相对误差(Relative error, RE) 评估算法的重构精度, 如式(19)所示. 其中${\boldsymbol{f}}_S^R$ 和${{\boldsymbol{f}}_S}$ 分别表示重构信号和原始信号.$${{RE}} = \frac{{\left\| {{{\boldsymbol{f}}_S} - {\boldsymbol{f}}_S^R} \right\|_2^2}}{{\left\| {{{\boldsymbol{f}}_S}} \right\|_2^2}}$$ (19) 在无噪情况中, 不同算法的重构性能如图4所示, 其中图4(a)和图4(c)表示基于随机采样的
${G_1}$ 和${G_2}$ 数据集的重构性能, 图4(b)和图4(d)表示基于贪婪采样的${G_1}$ 和${G_2}$ 数据集的重构性能. 相比于ILSR和O-PGIR算法, 由于BGSR-GFS算法利用了信号的图高频分量特征; 无论采用随机采样或贪婪采样, 新算法都具有更优的迭代效率和重构误差. 此外, 由于BGSR-GFS-R算法基于残差信号的图高频分量特征进行重构, 该算法能够高效地估计未采样节点的残差信号, 相比于IPR和IGDR重构算法, 其迭代效率和重构精度均有提升.
图 4 无噪环境下带限图信号重构性能对比Fig. 4 Comparison of graph band-limited signals reconstruction performances in noiseless environment如图4(a)所示, 本文将重构算法应用于基于随机采样的
${G_1}$ 数据集中, BGSR-GFS和BGSR-GFS-R的重构精度分别为$3.75 \times {10^{ - 15}}$ 和$2.07 \times {10^{ - 15}}$ , 算法ILSR, OPGIR, IPR和IGDR的重构精度分别为$1.05 \times {10^{ - 7}}$ ,$7.82 \times {10^{ - 13}}$ ,$8.13 \times {10^{ - 15}}$ 和$6.51 \times $ $ {10^{ - 15}}$ . 而基于贪婪采样, BGSR和BGSR-GFS-R的重构精度分别为$3.79 \times {10^{ - 15}}$ 和$2.70 \times {10^{ - 15}}$ , ILSR, OPGIR, IPR和IGDR的重构精度分别为$1.47 \times $ $ {10^{ - 14}}$ ,$9.01 \times {10^{ - 15}}$ ,$7.06 \times {10^{ - 15}}$ 和$6.51 \times {10^{ - 15}}$ . 新算法的重构精度提升40 % ~ 70 %.如图4(b)所示, 本文将重构算法应用于数据集
${G_2}$ 中, 新算法BGSR-GFS的重构精度分别为$1.97 \times {10^{ - 15}}$ (随机)和$2.47 \times {10^{ - 15}}$ (贪婪), 新算法BGSR-GFS-R的重构精度分别为$5.53 \times {10^{ - 16}}$ (随机)和$7.51 \times {10^{ - 16}}$ (贪婪). 在随机采样中, 算法ILSR, OPGIR, IPR和IGDR的重构精度分别为$7.59 \times $ $ {10^{ - 6}}$ ,$6.73 \times {10^{ - 11}}$ ,$2.76 \times {10^{ - 15}}$ 和$3.42 \times {10^{ - 15}}$ . 基于贪婪采样,算法ILSR, OPGIR, IPR和IGDR的重构精度分别为$1.65 \times {10^{ - 9}}$ ,$4.65 \times {10^{ - 15}}$ ,$1.43 \times {10^{ - 15}}$ 和$3.40 \times {10^{ - 15}}$ . 相比于其他算法, 新算法的重构精度提升约60 %.如表1和表2所示, 相比于ILSR和O-PGIR算法, BGSR-GFS算法的重构效率提升70 %. 相比于ILSR和O-PGIR算法, BGSR-GFS-R算法的重构效率提升75 %.
表 1 无噪情况下基于随机采样的${G_1}$ 重构效率Table 1${G_1}$ reconstruction efficiency of random sampling in noiseless算法 迭代次数 运行时间 (s) ILSR 220 139.99 OPGIR 114 108.78 IPR 96 61.87 IGDR 33 20.47 BGSR-GFS 27 5.73 BGSR-GFS-R 8 8.97 表 2 无噪情况下基于随机采样的${G_2}$ 重构效率Table 2${G_2}$ reconstruction efficiency of random sampling in noiseless算法 迭代次数 运行时间 (s) ILSR 269 0.1509 OPGIR 139 0.1291 IPR 64 0.0405 IGDR 34 0.0271 BGSR-GFS 7 0.0065 BGSR-GFS-R 5 0.0146 为了对比噪声环境中的算法的鲁棒性, 本文在采样信号中分别加入信噪比为
$20\;{\rm{dB}}$ 和$40\;{\rm{dB}}$ 的随机高斯噪声. 信号重构性能对比如图5所示, 本文提出的重构算法和对比算法的抗噪鲁棒性相同, 然而BGSR-GFS和BGSR-GFS-R的迭代效率更高. 无论是本文算法还是对比算法均没有进行噪声抑制或消除的步骤, 导致无法消除噪声对于重构性能的影响.
图 5 含噪环境下带限图信号重构性能对比Fig. 5 Comparison of graph band-limited signals reconstruction performances in noisy environment在第3组仿真中, 本文将针对分段带限图信号进行重构性能对比. 本文将第1组仿真实验中的图信号加入高频分量. 即随机选取
${{Q}}$ 个连续的高频分量后, 再通过图傅里叶逆变换得到分段带限图信号(${G_1}$ 和${G_2}$ 的${{Q}}$ 值分别为10和3). 为了确保对比试验的公平性, 本文将对比算法中的低通图滤波器调整为带通图滤波器.如图6所示, 无论是基于随机采样或贪婪采样, 本文算法都具有良好的重构精度和迭代效率. 由于ILSR和O-PGIR算法都是利用图信号的低频分量相似性原则设计重构算法, 而没有考虑到图信号的高频段分量的差异性, 所以迭代效率十分有限. 算法IPR在ILSR的基础上, 基于相邻节点残差信号等值传递的原则进行迭代过程中增量的估计, 而算法IGDR在IPR的基础上增加了扩散策略, 进一步提高了迭代效率; 两种基于残差法的重构策略实质上都是利用了残差信号低频分量之间的相似性, 同样无法实现高效的信号重构. 与上述4种算法不同的是, 由于本文提出的两种算法同时考虑了图低频相似性和图高频差异性, 通过图谱域移位策略重构分段带限图信号, 具有较高的重构精度和迭代效率.
图 6 分段带限图信号重构性能对比Fig. 6 Comparison of graph separate band-limited signals reconstruction performances5. 结束语
本文针对带限图信号的重构问题, 提出了基于图带限分量恒等特性的重构模型. 通过将该重构模型转化为最小二乘问题, 本文提出了两种基于图谱域移位的重构算法. 此外, 本文所提出的新算法同样适用于分段带限图信号的重构问题. 最后, 数值仿真表明, 相比于其他重构算法, 本文算法的重构性能更优.
-
图 4 无噪环境下带限图信号重构性能对比
Fig. 4 Comparison of graph band-limited signals reconstruction performances in noiseless environment
图 5 含噪环境下带限图信号重构性能对比
Fig. 5 Comparison of graph band-limited signals reconstruction performances in noisy environment
图 6 分段带限图信号重构性能对比
Fig. 6 Comparison of graph separate band-limited signals reconstruction performances
表 1 无噪情况下基于随机采样的
${G_1}$ 重构效率Table 1
${G_1}$ reconstruction efficiency of random sampling in noiseless算法 迭代次数 运行时间 (s) ILSR 220 139.99 OPGIR 114 108.78 IPR 96 61.87 IGDR 33 20.47 BGSR-GFS 27 5.73 BGSR-GFS-R 8 8.97 
下载: 导出CSV
表 2 无噪情况下基于随机采样的
${G_2}$ 重构效率Table 2
${G_2}$ reconstruction efficiency of random sampling in noiseless算法 迭代次数 运行时间 (s) ILSR 269 0.1509 OPGIR 139 0.1291 IPR 64 0.0405 IGDR 34 0.0271 BGSR-GFS 7 0.0065 BGSR-GFS-R 5 0.0146
下载: 导出CSV
-
[1] 刘建伟, 黎海恩, 罗雄麟. 概率图模型学习技术研究进展[J]. 自动化学报, 2014, 40(06): 1025-1044.Liu Jian-Wei, Li Hai-En, Luo Xiong-Lin. Learning technique of probabilistic graphical models: a review. Acta Automatica Sinica, 2014, 40(6): 1025−1044. [2] Shuman D I, Narang S K, Frossard P, Ortega A, Vandergheynst P. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 2013, 30(3): 83-98 doi: 10.1109/MSP.2012.2235192 [3] Tremblay N, Gonalves P, Borgnat P. Design of graph filters and filterbanks. Cooperative and Graph Signal Processing. Academic Press, 2018: 299−324 [4] Chen S H, Varma R, Sandryhaila A, Kovačević J. Discrete signal processing on graphs: Sampling theory. IEEE Transactions on Signal Processing, 2015, 63(24): 6510-6523 doi: 10.1109/TSP.2015.2469645 [5] Hu W, Cheung G, Ortega A, Au O C. Multiresolution graph Fourier transform for compression of piecewise smooth images. IEEE Transactions on Image Processing, 2014, 24(1): 419-433 [6] Liu Y L, Yang L S, You K Y, Guo W B, Wang W B. Graph learning based on spatiotemporal smoothness for time-varying graph signal. IEEE Access, 2019, 7: 62372-62386 doi: 10.1109/ACCESS.2019.2916567 [7] 蒋俊正, 杨杰, 欧阳缮. 一种新的无线传感器网络中异常节点检测定位算法[J]. 电子与信息学报, 2018, 40(10): 2358-2364.Jiang Jun-Zheng, Yang Jie, Ouyang Shan. Novel method for outlier nodes detection and localization in wireless sensor networks. Journal of Electronics and Information Technology, 2018, 40(10): 2358-2364. [8] 杨杰, 蒋俊正. 利用联合图模型的传感器网络数据修复方法[J]. 西安电子科技大学学报, 2020, 47(01): 44-51.YANG Jie, JIANG Junzheng. Method for data recovery in the sensor network based on the joint graph model[J]. Journal of Xidian University, 2020, 47(1): 44-51. [9] 廖祥文, 陈兴俊, 魏晶晶, 陈国龙, 程学旗. 基于多层关系图模型的中文评价对象与评价词抽取方法[J]. 自动化学报, 2017, 43(03): 462-471.LIAO Xiang-Wen, CHEN Xing-Jun, WEI Jing-Jing, CHEN Guo-Long, CHENG Xue-Qi. A Multi-layer Relation Graph Model for Extracting Opinion Targets and Opinion Words. Acta Automatica Sinica, 2017, 43(3): 462-471. [10] 张建朋, 裴雨龙, 刘聪, 李邵梅, 陈鸿昶. 基于因子图模型的动态图半监督聚类算法[J]. 自动化学报, 2020, 46(04): 670-680.ZHANG Jian-Peng, PEI Yu-Long, LIU Cong, LI Shao-Mei, CHEN Hong-Chang. A Semi-supervised Clustering Algorithm Based on Factor Graph Model for Dynamic Graphs. Acta Automatica Sinica, 2020, 46(4): 670-680. [11] Ortega A, Frossard P, Kovačević J, Moura J M F, Vandergheyns P. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 2018, 106(5): 808-828. doi: 10.1109/JPROC.2018.2820126 [12] Tanaka Y. Spectral domain sampling of graph signals[J]. IEEE Transactions on Signal Processing, 2018, 66(14): 3752-3767. doi: 10.1109/TSP.2018.2839620 [13] Guler B, Avestimehr S, Ortega A. TACC: Topology-Aware Coded Computing for Distributed Graph Processing[J]. IEEE Transactions on Signal and Information Processing over Networks, 2020, 6(99): 508-525. [14] Hosseinalipour S, Wang J, Dai H Y, Wang W Y. Detection of infections using graph signal processing in heterogeneous networks. In: Proceedings of the 2017 IEEE Global Communications Conference. Singapore, Singapore: IEEE, 2017.1−6. [15] Shuman D I, Faraji M J, Vandergheynst P. A multiscale pyramid transform for graph signals[J]. IEEE Transactions on Signal Processing, 2015, 64(8): 2119-2134. [16] Shen Y, Baingana B, Giannakis G B. Tensor decompositions for identifying directed graph topologies and tracking dynamic networks[J]. IEEE Transactions on Signal Processing, 2017, 65(14): 3675-3687. doi: 10.1109/TSP.2017.2698369 [17] Tanaka Y, Eldar Y C, Ortega A, Cheung G. Sampling signals on graphs: From theory to applications. IEEE Signal Processing Magazine, 2020, 37(6): 14-30 doi: 10.1109/MSP.2020.3016908 [18] Ferreira P. Interpolation and the Discrete Papoulis Gerchberg Algorithm[J]. IEEE Transactions on Signal Processing, 1994, 42(10): 2596-2606. doi: 10.1109/78.324726 [19] Narang S K, Gadde A, Sanou E, Ortega A. Localized iterative methods for interpolation in graph structured data. In: Proceedings of the 2013 IEEE Global Conference on Signal and Information Processing. Austin, TX, USA: IEEE, 2013. 491−494 [20] Wang X, Liu P, Gu Y. Local-set-based graph signal reconstruction[J]. IEEE Transactions on Signal Processing, 2015, 63(9): 2432-2444. doi: 10.1109/TSP.2015.2411217 [21] Yang L S, You K Y, Guo W B. Bandlimited graph signal reconstruction by diffusion operator. EURASIP Journal on Advances in Signal Processing, 2016, Article number: 120 (2016) [22] Brugnoli E, Toscano E, Vetro C. Iterative Reconstruction of Signals on Graph[J]. IEEE Signal Processing Letters, 2019, 27: 76-80. [23] Tseng C C, Lee S L. A missing data recovery method of sparse graph signal in GFT domain. In: Proceedings of the 2018 IEEE International Conference on Consumer Electronics. Taipei, China: IEEE, 2018. 1−2 [24] Tseng C C, Lee S L, Su R H. A missing temperature data estimation method using graph Fourier transform. In: Proceedings of the 2017 IEEE International Conference on Consumer Electronics. Taipei, China: IEEE, 2017. 87−88 [25] Sandryhaila A, Moura J M F. Discrete signal processing on graphs: Graph Fourier transform. In: Proceedings of the 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing. Vancouver, BC, Canada: IEEE, 2013. 6167−6170. [26] Narang S K, Gadde A, Ortega A. Signal processing techniques for interpolation in graph structured data. In: Proceedings of the 2013 IEEE International Conference on Acoustics, Speech, and Signal Processing. Vancouver, BC, Canada: IEEE, 2013. 5445−5449. [27] Chen S H, Varma R, Singh A, Kovačević J. Representations of piecewise smooth signals on graphs. In: Proceedings of the 2016 IEEE International Conference on Acoustics, Speech, and Signal Processing. Shanghai, China: IEEE, 2016. 6370−6374 [28] Youla D C, Webb H. Image restoration by the method of convex projections: Part I-Theory[J]. IEEE Transactions on Medical Imaging, 1982, 1(2), 81–94. doi: 10.1109/TMI.1982.4307555 [29] Narang S K, Ortega A. Perfect reconstruction two-channel wavelet filter banks for graph structured data[J]. IEEE Transactions on Signal Processing, 2012, 60(6): 2786-2799. doi: 10.1109/TSP.2012.2188718 [30] Sandryhaila A, Moura J M F. Discrete signal processing on graphs[J]. IEEE Transactions on Signal Processing, 2013, 61(7): 1644-1656. doi: 10.1109/TSP.2013.2238935 期刊类型引用(4)
1. 郑薇. 基于混沌BP算法的数字温度传感器温度误差模糊控制方法. 工业仪表与自动化装置. 2023(03): 122-126+133 . 
百度学术2. 易利群，盛玉霞，柴利. 融合MRI信息的PET图像去噪:基于图小波的方法. 自动化学报. 2023(12): 2605-2614 . 本站查看3. 王涵予，姜永元，张守亮，吴任翔，孙伟. 人工气候加速试验箱温湿度图信号重构智能监测算法. 计算机应用. 2022(S1): 376-379 . 百度学术4. 张戍育，余国文. 基于无人机蜂群的雷达波束特征提取方案. 空军预警学院学报. 2021(05): 353-358 . 百度学术其他类型引用(5)
-
计量
- 文章访问数: 1186
- HTML全文浏览量: 323
- PDF下载量: 134
- 被引次数: 9
