A Caltech Library Service

IIR Filtering on Graphs with Random Node-Asynchronous Updates

Teke, Oguzhan and Vaidyanathan, Palghat P. (2020) IIR Filtering on Graphs with Random Node-Asynchronous Updates. IEEE Transactions on Signal Processing, 68 . pp. 3945-3960. ISSN 1053-587X.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Teke, Oguzhan0000-0002-1131-5206
Vaidyanathan, Palghat P.0000-0003-3003-7042
Additional Information:© 2020 IEEE. Manuscript received June 23, 2019; revised December 30, 2019 and April 22, 2020; accepted June 22, 2020. Date of publication June 26, 2020; date of current version July 10, 2020. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Pierre Borgnat. This work was supported in part by the Office of Naval Research under Grant N00014-18-1-2390, in part by the National Science Foundation under Grant CCF-1712633, and in part by the Carver Mead Research Seed Fund of the California Institute of Technology.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-18-1-2390
Carver Mead Seed FundUNSPECIFIED
Subject Keywords:Graph signal processing, graph filters, fixed point iteration, randomized iterations, node asynchronicity
Record Number:CaltechAUTHORS:20200706-095543433
Persistent URL:
Official Citation:O. Teke and P. P. Vaidyanathan, "IIR Filtering on Graphs With Random Node-Asynchronous Updates," in IEEE Transactions on Signal Processing, vol. 68, pp. 3945-3960, 2020, doi: 10.1109/TSP.2020.3004912
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104222
Deposited By: Tony Diaz
Deposited On:06 Jul 2020 17:17
Last Modified:14 Jul 2020 22:50

Repository Staff Only: item control page