IIR Filtering on Graphs With Random Node-Asynchronous Updates

摘要: Graph filters play an important role in graph signal processing, which the data is analyzed with respect to underlying network (graph) structure. As extension classical are generally constructed as a polynomial (FIR), or rational (IIR) function of operator, can be implemented via successive shifts on graph. Although shift localized operation, it requires all nodes communicate synchronously, limitation for large scale networks. To overcome this limitation, study proposes node-asynchronous implementation arbitrary graphs. In proposed algorithm follow randomized collect-compute-broadcast scheme: if node passive stage collects sent by its incoming neighbors and stores only most recent data. When gets into active at random time instance, does necessary filtering computations locally, broadcasts state vector outgoing neighbors. For analysis algorithm, first considers general case asynchronous recursions presents sufficiency condition convergence. Based result, proven converge filter output mean-squared sense when filter, operator update rate satisfy certain condition. The simulated using filters, convergence demonstrated various different cases, also shows robustness communication failures.