A Caltech Library Service

Joint Vertex-Time Filtering on Graphs With Random Node-Asynchronous Updates

Teke, Oguzhan and Vaidyanathan, Palghat P. (2021) Joint Vertex-Time Filtering on Graphs With Random Node-Asynchronous Updates. IEEE Access, 9 . pp. 122801-122818. ISSN 2169-3536. doi:10.1109/ACCESS.2021.3109288.

[img] PDF - Published Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


In graph signal processing signals are defined over a graph, and filters are designed to manipulate the variation of signals over the graph. On the other hand, time domain signal processing treats signals as time series, and digital filters are designed to manipulate the variation of signals in time. This study focuses on the notion of vertex-time filters, which manipulates the variation of a time-dependent graph signal both in the time domain and graph domain simultaneously. The key aspects of the proposed filtering operations are due to the random and asynchronous behavior of the nodes, in which they follow a collect-compute-broadcast scheme. For the analysis of the randomized vertex-time filtering operations, this study first considers the random asynchronous variant of linear discrete-time state-space models, in which each state variable gets updated randomly and independently (and asynchronously) in every iteration. Unlike previous studies that analyzed similar models under certain assumptions on the input signal, this study considers the model in the most general setting with arbitrary time-dependent input signals, which lay the foundations for the vertex-time graph filtering operations. This analysis shows that exponentials continue to be eigenfunctions in a statistical sense in spite of the random asynchronous nature of the model. This study also presents the necessary and sufficient condition for the mean-squared stability and shows that stability of the underlying state transition matrix is neither necessary nor sufficient for the mean-squared stability of the randomized asynchronous recursions. Then, the proposed filtering operations are proven to be mean-square stable if and only if the filter, the graph operator and the update probabilities satisfy a certain condition. The results show that some unstable vertex-time graph filters (in the synchronous case) can be implemented in a stable manner in the presence of randomized asynchronicity, which is also demonstrated by numerical examples.

Item Type:Article
Related URLs:
URLURL TypeDescription
Teke, Oguzhan0000-0002-1131-5206
Vaidyanathan, Palghat P.0000-0003-3003-7042
Additional Information:This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see Received July 15, 2021, accepted August 16, 2021, date of publication August 31, 2021, date of current version September 13, 2021. This work was supported in part by the Office of Naval Research under Grant N00014-18-1-2390 and Grant N00014-21-1-2521, and in part by the California Institute of Technology.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-18-1-2390
Office of Naval Research (ONR)N00014-21-1-2521
Subject Keywords:Autonomous networks, asynchronous updates, randomized iterations, vertex-time filters
Record Number:CaltechAUTHORS:20211008-170015580
Persistent URL:
Official Citation:O. Teke and P. P. Vaidyanathan, "Joint Vertex-Time Filtering on Graphs With Random Node-Asynchronous Updates," in IEEE Access, vol. 9, pp. 122801-122818, 2021, doi: 10.1109/ACCESS.2021.3109288.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:111280
Deposited By: Tony Diaz
Deposited On:08 Oct 2021 19:08
Last Modified:08 Oct 2021 19:08

Repository Staff Only: item control page