IIR Filtering on Graphs With Random Node-Asynchronous Updates
IIR Filtering on Graphs With Random Node-Asynchronous Updates
复制标题
DOI：
10.1109/tsp.2020.3004912
复制
发表时间：
2020-06
影响因子：
5.4
通讯作者：
Oguzhan Teke;P. Vaidyanathan
中科院分区：
文献类型：
--
作者：
Oguzhan Teke;P. Vaidyanathan
图滤波器在图信号处理中起着重要的作用，在图信号处理中，相对于底层网络（图）结构来分析数据。作为对经典信号处理的扩展，图滤波器通常被构造为底层图运算符的多项式（FIR）或有理（IIR）函数，其可以经由图上的连续移位来实现。虽然图移位是局部化操作，但它要求所有节点同步通信，这可能是大规模网络的限制。为了克服这一限制，本研究提出了一个节点异步实现的理性过滤器在任意图形。在所提出的算法中，节点遵循随机收集-计算-广播方案：如果节点处于被动阶段，则它收集其传入邻居发送的数据并仅存储最新数据。当一个节点在一个随机的时刻进入活动阶段时，它在本地进行必要的过滤计算，并向其传出的邻居广播一个状态向量。对于算法的分析，本研究首先考虑一般情况下的随机异步状态递归，并提出了一个充分条件，其收敛性。在此基础上，证明了当滤波器、图算子和节点更新速率满足一定条件时，该算法在均方意义下收敛于滤波器输出.使用有理滤波器和多项式滤波器对该算法进行了仿真，证明了该算法在各种不同情况下的收敛性，同时也表明了该算法对随机通信故障的鲁棒性。
Graph filters play an important role in graph signal processing, in which the data is analyzed with respect to the underlying network (graph) structure. As an extension to classical signal processing, graph filters are generally constructed as a polynomial (FIR), or a rational (IIR) function of the underlying graph operator, which can be implemented via successive shifts on the graph. Although the graph shift is a localized operation, it requires all nodes to communicate synchronously, which can be a limitation for large scale networks. To overcome this limitation, this study proposes a node-asynchronous implementation of rational filters on arbitrary graphs. In the proposed algorithm nodes follow a randomized collect-compute-broadcast scheme: if a node is in the passive stage it collects the data sent by its incoming neighbors and stores only the most recent data. When a node gets into the active stage at a random time instance, it does the necessary filtering computations locally, and broadcasts a state vector to its outgoing neighbors. For the analysis of the algorithm, this study first considers a general case of randomized asynchronous state recursions and presents a sufficiency condition for its convergence. Based on this result, the proposed algorithm is proven to converge to the filter output in the mean-squared sense when the filter, the graph operator and the update rate of the nodes satisfy a certain condition. The proposed algorithm is simulated using rational and polynomial filters, and its convergence is demonstrated for various different cases, which also shows the robustness of the algorithm to random communication failures.