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 August 31, 2021 | Published
Journal Article Open

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

Abstract

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.

Additional Information

This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/. 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.

Attached Files

Published - Joint_Vertex-Time_Filtering_on_Graphs_With_Random_Node-Asynchronous_Updates.pdf

Files

Joint_Vertex-Time_Filtering_on_Graphs_With_Random_Node-Asynchronous_Updates.pdf

Additional details

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