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

Design of optimal sampling set for bandlimited graph signal

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

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.