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

• 电子技术 •    下一篇

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

谢煊1, 冯辉1,*, 胡波1, 李旦1,2   

  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 XIE1, Hui FENG1,*, Bo HU1, Dan LI1,2   

  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:

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

中图分类号: