Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 26, 2020 | public
Journal Article

IIR Filtering on Graphs with Random Node-Asynchronous Updates

Abstract

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.

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.

Additional details

Created:
August 19, 2023
Modified:
October 20, 2023