Shift-enabled graphs : graphs where shift-invariant filters are representable as polynomials of shift operations

Chen, Liyan and Cheng, Samuel and Stankovic, Vladimir and Stankovic, Lina (2018) Shift-enabled graphs : graphs where shift-invariant filters are representable as polynomials of shift operations. IEEE Signal Processing Letters, 25 (9). pp. 1305-1309. ISSN 1070-9908

[img]
Preview
Text (Chen-etal-SPL2018-Shift-enabled-graphs-graphs-where-shift-invariant-filters)
Chen_etal_SPL2018_Shift_enabled_graphs_graphs_where_shift_invariant_filters.pdf
Accepted Author Manuscript

Download (239kB)| Preview

    Abstract

    In digital signal processing, a shift-invariant filter can be represented as a polynomial expansion of a shift operation, that is, the Z-transform representation. When extended to Graph Signal Processing (GSP), this would mean that a shift-invariant graph filter can be represented as a polynomial of the shift matrix of the graph. Prior work shows that this holds under the shift-enabled condition that the characteristic and minimum polynomials of the shift matrix are identical. While the shiftenabled condition is often ignored in the literature, this letter shows that this condition is essential for the following reasons. First, we prove that this condition is not just sufficient but also necessary for any shift-invariant filter to be representable by the shift matrix. Moreover, we provide a counterexample showing that given a filter that commutes with a non-shift-enabled graph, it is generally impossible to convert the graph to a shift-enabled graph with a shift matrix still commuting with the original filter. The result provides a deeper understanding of shift-invariant filters when applied in GSP and shows that further investigation of shift-enabled graphs is needed to make them applicable to practical scenarios.