带限图信号的最优采样集设计

doi:10.12305/j.issn.1001-506X.2022.02.01

系统工程与电子技术 ›› 2022, Vol. 44 ›› Issue (2): 357-364.doi: 10.12305/j.issn.1001-506X.2022.02.01

• 电子技术 • 下一篇

带限图信号的最优采样集设计

谢煊¹, 冯辉^1,*, 胡波¹, 李旦^1,²

1. 复旦大学信息科学与工程学院智慧网络与系统研究中心, 上海 200433
2. 上海市空间智能控制技术重点实验室, 上海 200433

收稿日期:2020-10-19 出版日期:2022-02-18 发布日期:2022-02-24
通讯作者: 冯辉
作者简介:谢煊(1993—), 女, 博士研究生, 主要研究方向为图信号处理|冯辉(1980—), 男, 副教授, 博士, 主要研究方向为分布式信号处理与应用|胡波(1968—), 男, 教授, 博士, 主要研究方向为数字通信、数字图像处理与电子系统设计|李旦(1982—), 男, 副教授, 博士, 主要研究方向为信号处理与电子系统设计
基金资助:
国家重点研发计划213项目;复旦-长光合作基金(FC2019-003)

Design of optimal sampling set for bandlimited graph signal

Xuan XIE¹, Hui FENG^1,*, Bo HU¹, Dan LI^1,²

1. Research Center of Smart Networks and Systems, Fudan University, Shanghai 200433, China
2. Shanghai Key Laboratory of Aerospace Intelligent Control Technology, Shanghai 200433, China

Received:2020-10-19 Online:2022-02-18 Published:2022-02-24
Contact: Hui FENG

摘要/Abstract

摘要：

针对在实际中采样所需人力或设备数量受限的情况, 为图信号优化设计了一种多阶段的采样集, 使得在采样数量约束下尽可能减少信号估计误差。将采样集设计建模为组合优化问题, 并通过松弛-量化的方法求得原始优化问题的次优解, 同时也给出了该松弛-量化方法的适用条件和渐进最优性。不同于已有的图信号采样集设计方法, 所提方法不仅得到了最优采样集还分析了影响节点采样重要性的因素, 给出了节点采样重要性的评价指标和其物理意义。最后, 提出了一种低复杂度的近似算法以解决大规模图信号的采样集设计问题, 并能逼近原始优化方法的结果。

关键词: 图信号, 采样理论, 实验设计

Abstract:

For the limitation of manpower or the equipment, we design a sampling set for multi-stage graph signal sampling. Given sampling budget constraints, the design of the sampling set aims to minimize the estimation error. We formulate the design of sampling set as an optimization problem and find the suboptimal solution by a relaxation-quantization approach. The applying condition and the asymptotic optimality of our approach are also proposed. Different from the existing methods, in addition to obtaining the optimal sampling set, we analyze the factors affecting the importance of vertices in sampling. Meanwhile, the metric of sampling importance and some insights into it are also given. Finally, a low-complexity approximation algorithm is proposed for large-scale graph signal sampling. The algorithm approaches the optimal solution efficiently.

Key words: graph signal, sampling theory, experimental design

中图分类号:

TN911.7

谢煊, 冯辉, 胡波, 李旦. 带限图信号的最优采样集设计[J]. 系统工程与电子技术, 2022, 44(2): 357-364.

Xuan XIE, Hui FENG, Bo HU, Dan LI. Design of optimal sampling set for bandlimited graph signal[J]. Systems Engineering and Electronics, 2022, 44(2): 357-364.

图/表 7

图1

图2

图3

图4

图5

图6

图7

参考文献 27

1	SHUMAN D I , NARANG S K , FROSSARD P , et al. The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains[J]. IEEE Signal Processing Magazine, 2013, 30 (3): 83- 98. doi: 10.1109/MSP.2012.2235192
2	ORTEGA A , FROSSARD P , KOVACČEVICĆ J , et al. Graph signal processing: overview, challenges, and applications[J]. Proceedings of the IEEE, 2018, 106 (5): 808- 828. doi: 10.1109/JPROC.2018.2820126
3	CHEN S , VARMA R , SANDRYHAILA A , et al. Discrete signal processing on graphs: sampling theory[J]. IEEE Trans.on Signal Processing, 2015, 63 (24): 6510- 6523. doi: 10.1109/TSP.2015.2469645
4	TANAKA Y , ELDAR Y C . Generalized sampling on graphs with subspace and smoothness priors[J]. IEEE Trans.on Signal Processing, 2020, 68, 2272- 2286. doi: 10.1109/TSP.2020.2982325
5	杨立山, 游康勇, 郭文彬, 等. 基于扩散算子的带限图信号加权重建策略[J]. 电子与信息学报, 2017, 39 (12): 2937- 2944.
	YANG L S , YOU K Y , GUO W B , et al. Graph diffusion ope-rator based weighted reconstruction strategy for band-limited graph signals[J]. Journal of Electronics & Information Techno-logy, 2017, 39 (12): 2937- 2944.
6	霍立寰, 廖桂生, 杨志伟, 等. 基于图信号处理的大口径阵面测量数据恢复[J]. 系统工程与电子技术, 2019, 41 (6): 1230- 1235.
	HUO L Y , LIAO G H , YANG Z W , et al. Large aperture array measured data recovery method based on graph signal[J]. Systems Engineering and Electronics, 2019, 41 (6): 1230- 1235.
7	GAVILI A , ZHANG X P . On the shift operator, graph frequency, and optimal filtering in graph signal processing[J]. IEEE Trans.on Signal Processing, 2017, 65 (23): 6303- 6318. doi: 10.1109/TSP.2017.2752689
8	ISUFI E , LOUKAS A , SIMONETTO A , et al. Autoregressive moving average graph filtering[J]. IEEE Trans.on Signal Processing, 2017, 65 (2): 274- 288. doi: 10.1109/TSP.2016.2614793
9	SHUMAN D I , RICAUD B , VANDERGHEYNST P . Vertex-frequency analysis on graphs[J]. Applied and Computational Harmonic Analysis, 2016, 40 (2): 260- 291. doi: 10.1016/j.acha.2015.02.005
10	WAI H T , SEGARRA S , OZDAGLAR A E , et al. Blind community detection from low-rank excitations of a graph filter[J]. IEEE Trans.on Signal Processing, 2020, 68, 436- 451. doi: 10.1109/TSP.2019.2961296
11	卢光跃, 周亮, 吕少卿, 等. 基于图信号处理的无线传感器网络异常节点检测算法[J]. 计算机应用, 2020, 40 (3): 783- 787.
	LU G Y , ZHOU L , LYU S Q , et al. Outlier node detection algorithm in wireless sensor networks based on graph signal processing[J]. Journal of Computer Applications, 2020, 40 (3): 783- 787.
12	杨杰. 基于图信号处理的WSN数据异常检测与恢复[D]. 桂林: 桂林电子科技大学, 2019.
	YNAG J. Data outlier detection and recovery in WSN based on graph signal processing[D]. Guilin: Guilin University of Electronic Technology, 2019.
13	KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[C]//Proc. of the International Conference on Learning Representations, 2017.
14	DEFFERRARD M, BRESSON X, VANDERGHEYNST P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Proc. of the 30th International Conference on Neural Information Processing Systems, 2016: 3844-3852.
15	HAMILTON W, YING Z, LESKOVEC J. Inductive representation learning on large graphs[C]//Proc. of the 31st International Conference on Neural Information Processing Systems, 2017: 1025-1035.
16	ANIS A , GADDE A , ORTEGA A . Efficient sampling set selection for bandlimited graph signals using graph spectral proxies[J]. IEEE Trans.on Signal Processing, 2016, 64 (14): 3775- 3789. doi: 10.1109/TSP.2016.2546233
17	XIE X, FENG H, JIA J, et al. Design of sampling set for bandlimited graph signal estimation[C]//Proc. of the IEEE Global Conference on Signal and Information Processing, 2017: 653-657.
18	SAKIYAMA A , TANAKA Y , TANAKA T , et al. Eigend ecomposition free sampling set selection for graph signals[J]. IEEE Trans.on Signal Processing, 2019, 67 (10): 2679- 2692. doi: 10.1109/TSP.2019.2908129
19	PUY G , TREMBLAY N , GRIBONVAL R , et al. Random sampling of bandlimited signals on graphs[J]. Applied and Computational Harmonic Analysis, 2018, 44 (2): 446- 475. doi: 10.1016/j.acha.2016.05.005
20	CHEN S , VARMA R , SINGH A , et al. Signal recovery on graphs: fundamental limits of sampling strategies[J]. IEEE Trans.on Signal and Information Processing over Networks, 2016, 2 (4): 539- 554.
21	BAI Y , WANG F , CHEUNG G , et al. Fast graph sampling set selection using Gershgorin disc alignment[J]. IEEE Trans.on Signal Processing, 2020, 68, 2419- 2434. doi: 10.1109/TSP.2020.2981202
22	JOSHI S , BOYD S . Sensor selection via convex optimization[J]. IEEE Trans.on Signal Processing, 2008, 57 (2): 451- 462.
23	TSITSVERO M , BARBAROSSA S , DI LORENZO P . Signals on graphs: uncertainty principle and sampling[J]. IEEE Trans.on Signal Processing, 2016, 64 (18): 4845- 4860. doi: 10.1109/TSP.2016.2573748
24	BOYD S P , VANDENBERGHE L . Convex optimization[M]. Cambridge: Cambridge University Press, 2004: 385- 390.
25	AYSAL T C, COATES M, RABBAT M. Distributed average consensus using probabilistic quantization[C]//Proc. of the IEEE 14th Workshop on Statistical Signal Processing, 2007: 640-644.
26	DEMMEL J W . Applied numerical linear algebra[M]. NewYork: Society for Industrial and Applied Mathematics, 1997: 28- 29.
27	GOLUB G H , VAN LOAN C F . Matrix computations[M]. London: Johns Hopkins University Press, 1996.

[1]	雷永林, 王言, 于芹章, 朱智, 董微, 朱一凡. 面向复杂仿真元建模的序贯近邻探索实验设计方法[J]. 系统工程与电子技术, 2021, 43(5): 1232-1239.
[2]	李响, 邢清华, 董涛. 基于多指标正交实验设计的UAV编队配系优化[J]. Journal of Systems Engineering and Electronics, 2013, 35(2): 331-337.
[3]	窦立谦, 宗群, 刘文静. 面向控制的系统辨识研究进展[J]. Journal of Systems Engineering and Electronics, 2009, 31(1): 158-164.
[4]	窦立谦, 宗群, 刘文静. 面向控制的系统辨识研究进展[J]. Journal of Systems Engineering and Electronics, 2009, 31(01): 158-164.

带限图信号的最优采样集设计

Design of optimal sampling set for bandlimited graph signal

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 27

相关文章 4

编辑推荐

Metrics

本文评价