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

被引:0
作者
Teke, Oguzhan [1 ]
Vaidyanathan, Palghat P. [1 ]
机构
[1] CALTECH, Dept Elect Engn, Pasadena, CA 91125 USA
关键词
State-space methods; Signal processing; Mathematical model; Analytical models; Numerical stability; Eigenvalues and eigenfunctions; Transient analysis; Autonomous networks; asynchronous updates; randomized iterations; vertex-time filters; INFINITE PRODUCTS; ALGORITHMS; STABILITY; SYSTEMS; SERIES;
D O I
10.1109/ACCESS.2021.3109288
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:122801 / 122818
页数:18
相关论文
共 61 条
  • [21] INFINITE PRODUCTS OF NONNEGATIVE MATRICES
    HARTFIEL, DJ
    [J]. SIAM JOURNAL ON APPLIED MATHEMATICS, 1974, 26 (02) : 297 - 301
  • [22] Observing and tracking bandlimited graph processes from sampled measurements
    Isufi, Elvin
    Banelli, Paolo
    Di Lorenzo, Paolo
    Leus, Geert
    [J]. SIGNAL PROCESSING, 2020, 177
  • [23] Forecasting Time Series With VARMA Recursions on Graphs
    Isufi, Elvin
    Loukas, Andreas
    Perraudin, Nathanael
    Leus, Geert
    [J]. IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2019, 67 (18) : 4870 - 4885
  • [24] Filtering Random Graph Processes Over Random Time-Varying Graphs
    Isufi, Elvin
    Loukas, Andreas
    Simonetto, Andrea
    Leus, Geert
    [J]. IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2017, 65 (16) : 4406 - 4421
  • [25] Isufi E, 2016, IEEE GLOB CONF SIG, P405, DOI 10.1109/GlobalSIP.2016.7905873
  • [26] Isufi E, 2016, EUR SIGNAL PR CONF, P200, DOI 10.1109/EUSIPCO.2016.7760238
  • [27] Autoregressive Moving Average Graph Filtering
    Isufi, Elvin
    Loukas, Andreas
    Simonetto, Andrea
    Leus, Geert
    [J]. IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2017, 65 (02) : 274 - 288
  • [28] Jungers R, 2009, LECT NOTES CONTR INF, V385, P1
  • [29] Kailath T, 2000, PR H INF SY, pXIX
  • [30] Kambatla Karthik, 2010, Proceedings of the 2010 IEEE International Conference on Cluster Computing (CLUSTER 2010), P245, DOI 10.1109/CLUSTER.2010.30