无向加权图上信号的采样与重构

Sampling and reconstruction of graph signals plays an important role in graph signal processing. Since graphs in practice are weighted, this project mainly studies sampling and reconstruction of graph signals with some smoothness on undirected weighted graph. First, sampling and reconstruction algorithms of graph signals on an undirected unweighted graph are generalized to the case of undirected weighted graphs. The sampling scheme and reconstruction method will be improved, and the sampling stability will be supplemented by fully considering the influence of weight. Then, wavelet subspaces and reproducing kernel subspaces are defined on an undirected weighted graph based on spectral graph theory, and sampling and reconstruction of graph signals in the correspongding subspaces are studied. In view of the characteristics of undirected weighted graph, we explore reasonable and stable sampling schemes, construct suitale pre-reconstruction operator and the correspongding efficient reconstruction algorithms. Moreover, the mean error and asymptotic pointwise error estimates will be given. At the same time, we will give numerical simulation of the correspongding algorithms for a signal on some undirected weighted graph, and study the effect of sampling set for the convergence of our proposed algorithms. The research of this project will enrich and develop the sampling theory of graph signals, and provide new ideas and methods for graph signal processing.

图信号的采样与重构在图信号处理中扮演着重要的角色，由于实际问题所对应的图一般都是加权图，本项目主要研究无向加权图上具有某种光滑结构的图信号的采样与重构问题。首先，将无向无权带限图信号的采样和重构算法推广到无向加权带限图信号，充分考虑加权图中权的影响，改进现有的采样和重构方式，补充完善现有结果中的采样稳定性。其次，基于图上的谱理论在无向加权图上定义小波子空间和再生核子空间，并研究对应子空间中图信号的采样与重构。针对无向加权图本身的特点探索研究合理的稳定采样方式，构造适当的预重构算子和对应的有效重构算法，并给出对应算法在含噪声情形下的平均误差估计和渐近点态误差估计。同时，以具体的无向加权图上的信号为例给出对应算法的数值模拟，并研究采样集的选择对算法收敛性的影响。本项目的研究将丰富和发展图信号的采样理论，为图信号处理提供新的思路和方法。

本项目主要研究无向加权图上光滑图信号的采样与重构问题。无权带限图信号的采样与重构已经取得了重要的进展，其中清华大学电子工程系的几位学者基于局部集给出了迭代加权重构算法、迭代传播重构算法和迭代局部测量重构算法。由于传播过程中也会受到其它局部集的影响，针对迭代局部测量重构，通过引入一个扩散算子构造了无向加权图信号的一个收敛的迭代重构算法，数值结果表明改进的算法具有更好的收敛性和对噪声的鲁棒性。因为传播重构和局部测量重构中的贪婪算法会产生许多小的局部集，而且小的局部集对周围其它局部集的影响较小，通过对局部集的大小设置一个适当的阈值，分别针对局部集和无心局部集提出了加权图信号的一种迭代分类传播重构。结果表明改进的算法和原算法具有几乎相同的收敛性和抗噪性，但是却减少了通讯代价。时域分布网络在实际中具有重要应用，例如：无线传感器网络，智能电网等。首先，建立时域分布网络节点和信号发射位置的联系，利用图结构描述分布采样与重构系统。其次，系统的鲁棒性可以归结为感知矩阵的稳定性，建立了稳定性的局部验证标准，感知矩阵的稳定性等价于子矩阵的一致稳定性，此标准对于设计鲁棒的分布采样与重构系统至关重要，因为对于传感器的增加、替换或者损坏等，只需要保证受影响子系统的稳定性即可。最后，给出了一个具有指数收敛性的分布式重构算法，在有界噪声存在时可以提供拟最优逼近。该研究首次以图为工具从理论的角度系统地研究了时域分布网络的采样与重构，成果发表在调和分析领域顶级期刊“Applied and Computational Harmonic Analysis”, 受到了数学和信息领域的广泛关注。注意到如果图上的计数测度在测量(geodesic)距离下满足倍增(doubling)条件，那么此图在相应的距离和测度意义下就是一个齐次型空间。因此，在齐次型空间上定义了再生核子空间，并基于有限样本研究了此再生核空间中信号的采样与重构。项目研究过程中也做了一些拓展研究，例如：基于混合范数研究了时变信号的采样问题，也结合采样理论的最新研究进展考虑了一些新的采样方式，如计时采样和随机采样等。