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

Liyan Chen, Samuel Cheng, Vladimir Stankovic, Lina Stankovic

Research output: Contribution to journalArticle

2 Citations (Scopus)

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.
LanguageEnglish
Pages1305-1309
Number of pages5
JournalIEEE Signal Processing Letters
Volume25
Issue number9
Early online date22 Jun 2018
DOIs
Publication statusPublished - 30 Sep 2018

Fingerprint

Polynomials
Filter
Polynomial
Invariant
Graph in graph theory
Signal processing
Signal Processing
Z transforms
Digital signal processing
Graph Invariants
Commute
Convert
Counterexample
Transform
Sufficient
Scenarios

Keywords

  • graph signal processing
  • shift-invariant filter
  • polynomial
  • digital signal processing (DSP)

Cite this

@article{55a95db85c3c4a2b808a280185207916,
title = "Shift-enabled graphs: graphs where shift-invariant filters are representable as polynomials of shift operations",
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 alsonecessary 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-invariantfilters when applied in GSP and shows that further investigation of shift-enabled graphs is needed to make them applicable to practical scenarios.",
keywords = "graph signal processing, shift-invariant filter, polynomial, digital signal processing (DSP)",
author = "Liyan Chen and Samuel Cheng and Vladimir Stankovic and Lina Stankovic",
note = "{\circledC} 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.",
year = "2018",
month = "9",
day = "30",
doi = "10.1109/LSP.2018.2849685",
language = "English",
volume = "25",
pages = "1305--1309",
journal = "IEEE Signal Processing Letters",
issn = "1070-9908",
number = "9",

}

Shift-enabled graphs : graphs where shift-invariant filters are representable as polynomials of shift operations. / Chen, Liyan; Cheng, Samuel; Stankovic, Vladimir; Stankovic, Lina.

In: IEEE Signal Processing Letters, Vol. 25, No. 9, 30.09.2018, p. 1305-1309.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Shift-enabled graphs

T2 - IEEE Signal Processing Letters

AU - Chen, Liyan

AU - Cheng, Samuel

AU - Stankovic, Vladimir

AU - Stankovic, Lina

N1 - © 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.

PY - 2018/9/30

Y1 - 2018/9/30

N2 - 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 alsonecessary 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-invariantfilters when applied in GSP and shows that further investigation of shift-enabled graphs is needed to make them applicable to practical scenarios.

AB - 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 alsonecessary 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-invariantfilters when applied in GSP and shows that further investigation of shift-enabled graphs is needed to make them applicable to practical scenarios.

KW - graph signal processing

KW - shift-invariant filter

KW - polynomial

KW - digital signal processing (DSP)

UR - https://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=97&year=2002

U2 - 10.1109/LSP.2018.2849685

DO - 10.1109/LSP.2018.2849685

M3 - Article

VL - 25

SP - 1305

EP - 1309

JO - IEEE Signal Processing Letters

JF - IEEE Signal Processing Letters

SN - 1070-9908

IS - 9

ER -