博文

基于图谱域移位的带限图信号重构算法

已有 1856 次阅读 2022-7-23 16:43 |系统分类:博客资讯

引用文本

杨杰, 赵磊, 郭文彬. 基于图谱域移位的带限图信号重构算法. 自动化学报, 2021, 47(9): 2132−2142 doi: 10.16383/j.aas.c200802

Yang Jie, Zhao Lei, Guo Wen-Bin. Graph band-limited signals reconstruction method based graph spectral domain shifting. Acta Automatica Sinica, 2021, 47(9): 2132−2142 doi: 10.16383/j.aas.c200802

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200802

关键词

图信号处理，信号重构，图谱理论，位移算子

摘要

针对带限图信号的重构问题, 本文提出了基于图谱域移位的带限图信号重构模型, 该模型将图带限分量的恒等不变特性建模为最小二乘问题. 基于所提出的重构模型, 本文设计了基于谱移位的重构算法和基于残差谱移位的重构算法. 相比于其他重构算法, 两种新算法提升了迭代效率和重构精度. 此外, 本文算法还适用于分段带限图信号的重构问题, 并且具有良好的迭代效率和重构精度.通过实验仿真表明, 相比于目前其他的带限图信号重构算法, 新算法的迭代效率提升约70%和重构精度提升约60%.

文章导读

随着信息技术的高速发展, 各领域中所产生的数据维度正在以前所未有的速度增长, 例如社交网络数据、金融交易数据和城市交通流量数据等.

然而, 传统的数据表征方法无法适用于具有复杂关联特征的网络数据集. 所以, 图网络[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算法, 本文算法具有较好的重构性能. 此外, 由于本文提出的图带限分量的恒等不变性不需要考虑带限频率所在的频段, 所以针对分段带限图信号的重构问题同样适用, 并且具有良好的重构性能.