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 (https://doi.org/10.1109/LSP.2018.2849685)

[thumbnail of Chen-etal-SPL2018-Shift-enabled-graphs-graphs-where-shift-invariant-filters]
Preview
 Text. Filename: 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.

ORCID iDs

Chen, Liyan, Cheng, Samuel, Stankovic, Vladimir ORCID logoORCID: https://orcid.org/0000-0002-1075-2420 and Stankovic, Lina ORCID logoORCID: https://orcid.org/0000-0002-8112-1976;
  • Item type:Article
    ID code:64425
    Dates:
    Date
    Event
    30 September 2018
    Published
    22 June 2018
    Published Online
    8 June 2018
    Accepted
    Notes:© 2018 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
    Subjects:Technology > Electrical engineering. Electronics Nuclear engineering
    Department:Faculty of Engineering > Electronic and Electrical Engineering
    Depositing user: Pure Administrator
    Date deposited:12 Jun 2018 13:24
    Last modified:11 Nov 2024 12:01
    Related URLs:
    URI:https://strathprints.strath.ac.uk/id/eprint/64425
CORE (COnnecting REpositories)