论文部分内容阅读
随着信息的爆炸性增长,海量图结构数据以前所未有的速度产生于各种信号源。这些数据往往具有高维度、空间分布不规则等特征,为了有效分析和处理,图信号处理技术应运而生。采样是处理有关高维度数据问题的核心途径,重建则是求解逆问题的重要工具,它们在图信号处理中扮演着重要的角色。矩阵逆近似（Matrix Inversion Approximation,MIA）图信号重建算法已经被证明比传统的最小二乘（Least Squares,LS）重建具有更低的复杂度,然而却需要图拉普拉斯矩阵的特征值信息。本文针对现有的MIA算法所需的特征值信息,提出了一种在图信号处理领域中快速计算图拉普拉斯算子特征值的方法,该方法比现有的特征值求解方法复杂度更低。然后,使用所提出的特征值求解方法改进MIA算法,得到了一种重建速度更快的加速矩阵逆近似（Accelerated-Matrix Inverse Approximation,A-MIA）图信号重建策略。本文的主要内容及创新点如下:1.在已有的图信号处理相关理论基础上,首先概述了图信号、图频域、图信号的截止频率和图傅里叶变换等基本概念,给出了图信号在节点域和图频域的两种表示。然后,归纳了图信号的一些基本性质和定理,分析了图信号的变换机理,并提出了图信号采样和重建需要解决的问题,介绍了已有的几种解决方法及其基本原理。2.通过分析、研究图截止频率的特征,介绍了两种计算截止频率的方法,一种为近似求解方法,其揭示了截止频率和约化矩阵（￡k）Sc的最小奇异值之间的关系;另外一种为精确求解方法,该方法给出了样本集大小、截止频率和图拉普拉斯矩阵特征值之间的关系,结合这两种计算截止频率的方法,我们提出了一种在图信号处理领域中快速计算图拉普拉斯算子特征值的方法,经过仿真验证了所提出方法的可行性,并且与现有的几种特征值计算方法进行了对比。仿真实验表明,所提出方法较现有的特征值计算方法具有更快的速度。3.以带宽有限图信号的重建理论为基础,介绍了矩阵逆近似图信号重建算法,该算法已经被证明不再需要矩阵求逆,然而却需要图拉普拉斯矩阵的特征值信息,我们利用前面所提出的快速求解特征值方法获得了所需的特征值,从而提出了一种计算复杂度更低、重建精度更高的图信号重建策略。最后,通过使用三种典型的图结构和手写数字集构造的拓扑图对所提出的策略进行仿真,验证了该策略的可行性,并且与现有的几种重建方法进行了对比。仿真实验表明,所提出方法比现有图信号重建方法具有更好的信号重建性能。