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

4 Citations (Scopus)
18 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1305-1309
Number of pages5
JournalIEEE Signal Processing Letters
Volume25
Issue number9
Early online date22 Jun 2018
DOIs
Publication statusPublished - 30 Sep 2018

Keywords

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

Fingerprint Dive into the research topics of 'Shift-enabled graphs: graphs where shift-invariant filters are representable as polynomials of shift operations'. Together they form a unique fingerprint.

Cite this