Distributed Batch Reconstruction of Time-varying Graph Signals via Sobolev Smoothness on Cartesian Product Graph

ZHANG Yanhai; JIANG Junzheng

doi:10.11999/JEIT221194

Volume 45 Issue 5

May 2023

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2023 > 45(5): 1585-1592

ZHANG Yanhai, JIANG Junzheng. Distributed Batch Reconstruction of Time-varying Graph Signals via Sobolev Smoothness on Cartesian Product Graph[J]. Journal of Electronics & Information Technology, 2023, 45(5): 1585-1592. doi: 10.11999/JEIT221194

Citation:

ZHANG Yanhai, JIANG Junzheng. Distributed Batch Reconstruction of Time-varying Graph Signals via Sobolev Smoothness on Cartesian Product Graph[J]. Journal of Electronics & Information Technology, 2023, 45(5): 1585-1592. doi: 10.11999/JEIT221194

Citation:

PDF( 807 KB)

Distributed Batch Reconstruction of Time-varying Graph Signals via Sobolev Smoothness on Cartesian Product Graph

doi: 10.11999/JEIT221194

ZHANG Yanhai^{1, 3},
JIANG Junzheng^{1, 2
,
,}

1.
School of Information and Communication, Guilin University of Electronic Technology, Guilin 541004, China
2.
Key Laboratory of Cognitive Radio and Information Processing, Ministry of Education, Guilin University of Electronic Technology, Guilin 541004, China
3.
College of Science, Guilin University of Technology, Guilin 541004, China

Funds: The National Natural Science Foundation of China (62171146, 62261014), Guangxi Special Fund Project for Innovation-driven Development(GuikeAA21077008), Guangxi Natural Science Foundation for Distinguished Young Scholar (2021GXNSFFA220004), Guangxi Science and Technology Base and Talent Special Project(Guike AD21220112), Opening Fund of Key Laboratory of Cognitive Radio and Information Processing, Ministry of Education (CRKL210206)

Received Date: 2022-09-14
Rev Recd Date: 2023-02-13

Available Online: 2023-02-19

Publish Date: 2023-05-10

Abstract

Abstract

For the reconstruction of large-scale network data, a Distributed Batch Reconstruction algorithm via Sobolev Smoothness on Cartesian product graph (DBR-SSC) is proposed, which is based on the Graph Signal Processing (GSP) theory. In the proposed algorithm, the time-varying graph signal is firstly divided into multiple signal segments in time dimension, and a product graph is constructed from graphs at each time instant via Cartesian product. Secondly, the reconstruction of the time-varying graph signal in each segment is formulated as an optimization problem by exploiting the Sobolev difference smoothness on the Cartesian product graph. Finally, a distributed algorithm with high convergence rate is devised to solve the optimization problem. Two real world data sets are used for experiments, and it is shown that the proposed algorithm has low reconstruction error and high convergence rate.
- Graph Signal Processing (GSP),
- Time-varying graph signal,
- Distributed algorithm,
- Batch reconstruction,
- Sobolev smoothness

FullText(HTML)

References(20)

References

[1]	CHEN Min, MAO Shiwen, and LIU Yunhao. Big data: A survey[J]. Mobile Networks and Applications, 2014, 19(2): 171–209. doi: 10.1007/s11036-013-0489-0
[2]	李建中, 刘显敏. 大数据的一个重要方面: 数据可用性[J]. 计算机研究与发展, 2013, 50(6): 1147–1162. doi: 10.7544/issn1000-1239.2013.20130646 LI Jianzhong and LIU Xianmin. An important aspect of big data: Data usability[J]. Journal of Computer Research and Development, 2013, 50(6): 1147–1162. doi: 10.7544/issn1000-1239.2013.20130646
[3]	SANDRYHAILA A and MOURA J M F. Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure[J]. IEEE Signal Processing Magazine, 2014, 31(5): 80–90. doi: 10.1109/MSP.2014.2329213
[4]	SANDRYHAILA A and MOURA J M F. Discrete signal processing on graphs: Frequency analysis[J]. IEEE Transactions on Signal Processing, 2014, 62(12): 3042–3054. doi: 10.1109/TSP.2014.2321121
[5]	DONG Xiaowen, THANOU D, TONI L, et al. Graph signal processing for machine learning: A review and new perspectives[J]. IEEE Signal Processing Magazine, 2020, 37(6): 117–127. doi: 10.1109/MSP.2020.3014591
[6]	GIRALDO J H, JAVED S, and BOUWMANS T. Graph moving object segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44(5): 2485–2503. doi: 10.1109/TPAMI.2020.3042093
[7]	ITANI S and THANOU D. A graph signal processing framework for the classification of temporal brain data[C]. 2020 28th European Signal Processing Conference (EUSIPCO), Amsterdam, Netherlands, 2021: 1180–1184.
[8]	FENG Jie, CHEN Fangjiong, and CHEN Hongbin. Data reconstruction coverage based on graph signal processing for wireless sensor networks[J]. IEEE Wireless Communications Letters, 2022, 11(1): 48–52. doi: 10.1109/LWC.2021.3120276
[9]	LEWENFUS G, MARTINS W A, CHATZINOTAS S, et al. Joint forecasting and interpolation of time-varying graph signals using deep learning[J]. IEEE Transactions on Signal and Information Processing over Networks, 2020, 6: 761–773. doi: 10.1109/TSIPN.2020.3040042
[10]	CHEN Siheng, LIU Baoan, FENG Chen, et al. 3D point cloud processing and learning for autonomous driving: Impacting map creation, localization, and perception[J]. IEEE Signal Processing Magazine, 2021, 38(1): 68–86. doi: 10.1109/MSP.2020.2984780
[11]	PERRAUDIN N, LOUKAS A, GRASSI F, et al. Towards stationary time-vertex signal processing[C]. 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, USA, 2017: 3914–3918.
[12]	ROMERO D, IOANNIDIS V N, and GIANNAKIS G B. Kernel-based reconstruction of space-time functions on dynamic graphs[J]. IEEE Journal of Selected Topics in Signal Processing, 2017, 11(6): 856–869. doi: 10.1109/JSTSP.2017.2726976
[13]	QIU Kai, MAO Xianghui, SHEN Xinyue, et al. Time-varying graph signal reconstruction[J]. IEEE Journal of Selected Topics in Signal Processing, 2017, 11(6): 870–883. doi: 10.1109/JSTSP.2017.2726969
[14]	GIRALDO J H, MAHMOOD A, GARCIA-GARCIA B, et al. Reconstruction of time-varying graph signals via Sobolev smoothness[J]. IEEE Transactions on Signal and Information Processing over Networks, 2022, 8: 201–214. doi: 10.1109/TSIPN.2022.3156886
[15]	MOTEE N and SUN Qiyu. Sparsity and spatial localization measures for spatially distributed systems[J]. SIAM Journal on Control and Optimization, 2017, 55(1): 200–235. doi: 10.1137/15M1049294
[16]	CHENG Cheng, JIANG Yingchun, and SUN Qiyu. Spatially distributed sampling and reconstruction[J]. Applied and Computational Harmonic Analysis, 2019, 47(1): 109–148. doi: 10.1016/j.acha.2017.07.007
[17]	BOUTIN D L. The determining number of a Cartesian product[J]. Journal of Graph Theory, 2009, 61(2): 77–87. doi: 10.1002/jgt.20368
[18]	JIANG Junzheng, CHENG Cheng, and SUN Qiyu. Nonsubsampled graph filter banks: Theory and distributed algorithms[J]. IEEE Transactions on Signal Processing, 2019, 67(15): 3938–3953. doi: 10.1109/TSP.2019.2922160
[19]	US Environmental Protection Agency. Air quality data[EB/OL].https://www.epa.gov/outdoor-airquality-data, 2016.
[20]	DONG Ensheng, DU Hongru, and GARDNER L M. An interactive web-based dashboard to track COVID-19 in real time[J]. The Lancet Infectious Diseases, 2020, 20(5): 533–534. doi: 10.1016/S1473-3099(20)30120-1