图上信号的广义采样理论与重建方法研究

In this project we will focus on the generalized sampling theory and reconstruction methods for graph signals, which are important in both theory and application. First, high-dimensional, massive, distributed, and irregular data may be readily modeled as graph signals. As a consequence, graph signal processing may provide a novel framework for handling big data. Second, one of the fundamental problems in information theory is sampling and reconstruction. The generalized and non-uniform sampling theories in high-dimensional space and manifold have been well studied, yet few works on generalized graphs signal sampling have been done. Finally, the sampling theory studied in this project is a natural generalization of traditional graph signal sampling (or decimation), which could be readily used in modeling data collection in sensor network robustly. In this project, we will establish the theory of generalized graph signal sampling and reconstruction, address the key issues systematically and thoroughly, and obtain high-level research achievements accordingly. Specifically, we will first partition the nodes into local sets and model the generalized sampling locally, after which we will derive the necessary and sufficient conditions for unique reconstruction. Then we will find the optimal sampling method and evaluate the sampling method with random measurements. As to the reconstruction, we will devise highly efficient reconstruction methods and carry on the theoretical performance analysis. Furthermore, we will devise new methods for efficiently tracking dynamic graphs and time-varying signals in a distributed manner. Based on the theoretical analysis of the above results under non-ideal conditions, we will lay a solid foundation for potential applications of our theory and methods.

本项目研究图上信号的广义采样和重建问题，具有重要的理论意义和潜在的应用价值。首先，图上信号是高维、海量、分布式和不规则数据的有效表征方式，其处理技术可为大数据处理提供全新解决思路；其次，采样和重建是信息科学技术的基本问题，高维空间和流形上的非均匀采样理论日趋完备，但尚无图上的广义采样理论和重建方法；最后，图上广义采样是传统抽取式采样的一般性推广，是传感网数据采集等应用问题的自然抽象，具有抗噪声等先天优势。本项目具体将建立图上信号的广义采样和重建理论，系统深入地研究其关键技术，力争取得一批高水平的研究成果。具体将构造基于局部节点集的采样模型，研究由局部观测值唯一重建原信号的充要条件；研究最优观测方式，评估随机观测的性能；设计高性能的重建算法并进行理论分析；针对时变图结构、时变信号和仅邻居节点可见的分布式场景，设计跟踪算法；将上述理论和技术推广到非理想情形，为潜在应用奠定技术基础。

本项目本首先将图上信号的采样方式从抽取式采样拓展到局部观测，提出 一种利用局部观测值重建原信号的算法——迭代局部观测重建 (ILMR) 算法， 并证明在一定条件下，带限图上信号可以由其局部观测值精确重建。然后项目从时变图上信号的集中式重建问题出发，提出了时变图上信号的结构模型，基于该模型又提出了时变图上信号的集中式重建方法，并对最优重建、采样算子的选择等进行了相应的理论分析。随后项目解决了时变图上信号的在线分布式重建问题。提出了图上时变信号的在线重建方法，并对非理想信号生成情况在线重建误差展开了理论分析。接下来项目研究了一般的空时信号重建问题。通过发掘原始信号的低秩性 质和时间差分信号的空间光滑性，提出了一种新的空时信号重建方法，将其描述为一个无约束优化问题，并采用交替方向乘子法进行求解。通过对空间光滑性假设、时间光滑性假设以及差分光滑性假设的分析，我们证明了所提方法比 现有方法的适用范围更广。最后，项目从时变图上信号的异常检测问题出发，提出了图上信号跳变点检测模型。基于该模型又提出了时变图上信号跳变点检测算法，包括集中式和分布式两种，并对算的虚警率和检测延时进行了理论分析，证明了算法性能在阶的意义上具有最优性。此外，项目还抽象出图上信号处理问题的一般优化形式，形成一致优化问 题。针对图上信号处理场景中的分布式计算需求，进一步研究了分布式一致优化算法。设计了游走前后向梯度算法，并证明该算法在求解强凸优化问题时具有线性收敛性质，及其能耗相比现有算法有阶上的下降。