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

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

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

CLC Number:

TN911.7

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.

Figures/Tables 7

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

References 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]	Yonglin LEI, Yan WANG, Qinzhang YU, Zhi ZHU, Wei DONG, Yifan ZHU. Design method of sequential neighbor exploratory experimental for complex simulation metamodeling [J]. Systems Engineering and Electronics, 2021, 43(5): 1232-1239.
[2]	LI Xiang, XING Qing-hua, DONG Tao. Deployment optimization of UAV formation based on multi-index orthogonal experimental design [J]. Journal of Systems Engineering and Electronics, 2013, 35(2): 331-337.
[3]	ZHANG Li ，LI Hong，FENG Da-zheng. Differential evolution with orthogonal crossover for solving mixedinteger programming [J]. Journal of Systems Engineering and Electronics, 2011, 33(9): 2126-2132.

Design of optimal sampling set for bandlimited graph signal

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 27

Related Articles 3

Recommended Articles

Metrics

Comments