高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于笛卡尔乘积图上Sobolev平滑的时变图信号分布式批量重构

张彦海 蒋俊正

张彦海, 蒋俊正. 基于笛卡尔乘积图上Sobolev平滑的时变图信号分布式批量重构[J]. 电子与信息学报, 2023, 45(5): 1585-1592. doi: 10.11999/JEIT221194
引用本文: 张彦海, 蒋俊正. 基于笛卡尔乘积图上Sobolev平滑的时变图信号分布式批量重构[J]. 电子与信息学报, 2023, 45(5): 1585-1592. doi: 10.11999/JEIT221194
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

基于笛卡尔乘积图上Sobolev平滑的时变图信号分布式批量重构

doi: 10.11999/JEIT221194
基金项目: 国家自然科学基金(62171146, 62261014),广西创新驱动发展专项(桂科AA21077008),广西自然科学杰出青年基金(2021GXNSFFA220004),广西科技基地和人才专项(桂科AD21220112),认知无线电与信息处理教育部重点实验室开放基金(CRKL210206)
详细信息
    作者简介:

    张彦海:男,博士生,研究方向为图信号处理理论与算法

    蒋俊正:男,博士,教授,博士生导师,研究方向为图信号处理理论与算法、图滤波器组设计

    通讯作者:

    蒋俊正 jzjiang@guet.edu.cn

  • 中图分类号: TN911.72

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

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)
  • 摘要: 针对大规模网络数据的重构问题,该文以图信号处理(GSP)理论为基础,提出一种基于笛卡尔乘积图上Sobolev平滑的分布式批量重构算法(DBR-SSC)。该算法首先按时间顺序将时变图信号划分为多个信号段,并利用笛卡尔积将每一段内各时刻的图建模为乘积图;然后利用笛卡尔乘积图上的Sobolev差分平滑,将每一段的信号重构问题归结为优化问题;最后设计具有高收敛速度的分布式算法求解该优化问题。采用两种现实世界的数据集进行仿真实验,实验结果表明所提算法重构误差低并具有高收敛速度。
  • 图  1  PM2.5数据集上本文算法与牛顿法的收敛速度对比

    图  2  COVID-19数据集上本文算法与牛顿法的收敛速度对比

    算法1 段内时变图信号$ \bar {\boldsymbol{x}} $的分布式批量重构算法
     输入:矩阵$\bar {\boldsymbol{H}}$,观测信号$\bar {\boldsymbol{y}}$,迭代停止标准$ \varepsilon $,最大迭代次数$ K $, ${\bar {\boldsymbol{x}}^{(0)} }{\text{ = } }{{ {\textit{0}}}}$, $ t = 0 $。
     步骤:
       步骤1 根据式(12)计算$\bar {\boldsymbol{P}}$。
       步骤2 每一个子图中心节点(m,i)计算
                 ${{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t + 1)} } = {{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t)} } - {{\boldsymbol{\chi}} _{(m,i)} }\bar {\boldsymbol{P} }{{\boldsymbol{\chi}} _{(m,i)} }({{\boldsymbol{\chi}} _{(m,i)} }\bar {\boldsymbol{H} }{{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t)} } - {{\boldsymbol{\chi}} _{(m,i)} }\bar {\boldsymbol{y} })$           (14)
     并向${\bar {\boldsymbol{v}}_{(m,i)} }$中的所有节点$ (k,l) $发送相应的信号值${{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t{\text{ + } }1)} }{(h)_{h = N \times (k - 1) + l} }$。
       步骤3 $ \bar V $中的各节点对接收到的信号值进行平均,然后将平均值分别发送给所在子图的中心节点。
       步骤4 各子图中心节点(m,i)将收到的信号值以及自身的信号值组成新的子图信号${{\boldsymbol{\chi}} _{(m,i)} }{\bar {\boldsymbol{x} }^{(t{\text{ + } }1)} }$,如果
           $\left\| { {{\boldsymbol{\chi}} _{(m,i)} }{ {\bar {\boldsymbol{x} } }^{(t + 1)} } - {{\boldsymbol{\chi}} _{(m,i)} }{ {\bar {\boldsymbol{x} } }^{(t)} } } \right\|_2^2 < \varepsilon$成立或$ t > K $,则结束程序。否则,令$ t = t + 1 $,并返回步骤2。
     输出:${\bar {\boldsymbol{x}}^{(t + 1)} }$作为本段的重构信号。
    下载: 导出CSV

    表  1  PM2.5数据集上各种算法的平均重构误差(RMSE)对比

    算法受损节点数量占比(%)
    10 20 30
    BR-DS1.291.942.43
    BR-SS1.291.942.43
    BR-TR1.602.372.91
    DBR-SSC1.291.912.41
    下载: 导出CSV

    表  2  PM2.5数据集上各种算法的平均迭代次数对比

    算法受损节点数量占比(%)
    102030
    BR-DS1.562.723.52
    BR-SS1.532.543.28
    BR-TR0.430.600.66
    DBR-SSC0.150.160.20
    下载: 导出CSV

    表  3  PM2.5数据集上各种算法所用平均CPU时间对比 (10–3 s)

    算法受损节点数量占比(%)
    102030
    BR-DS1.181.952.45
    BR-SS1.171.892.32
    BR-TR0.390.450.49
    DBR-SSC2.012.012.03
    下载: 导出CSV

    表  4  COVID-19数据集上各种算法的平均重构误差(RMSE)对比

    算法受损节点数量占比(%)
    102030
    BR-DS204341463
    BR-SS204341462
    BR-TR5819961254
    DBR-SSC196332447
    下载: 导出CSV

    表  5  COVID-19数据集上各种算法的平均迭代次数对比

    算法受损节点数量占比(%)
    102030
    BR-DS6.646.676.67
    BR-SS4.276.646.67
    BR-TR0.560.700.85
    DBR-SSC0.330.540.75
    下载: 导出CSV

    表  6  COVID-19数据集上各种算法所用平均CPU时间对比 (10–3 s)

    算法受损节点数量占比(%)
    102030
    BR-DS12.5612.5612.67
    BR-SS8.4412.6312.59
    BR-TR1.201.411.73
    DBR-SSC7.978.128.19
    下载: 导出CSV
  • [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
  • 加载中
图(2) / 表(7)
计量
  • 文章访问数:  414
  • HTML全文浏览量:  141
  • PDF下载量:  75
  • 被引次数: 0
出版历程
  • 收稿日期:  2022-09-14
  • 修回日期:  2023-02-13
  • 网络出版日期:  2023-02-19
  • 刊出日期:  2023-05-10

目录

    /

    返回文章
    返回