### Abstract

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 language | English |
---|---|

Pages (from-to) | 1305-1309 |

Number of pages | 5 |

Journal | IEEE Signal Processing Letters |

Volume | 25 |

Issue number | 9 |

Early online date | 22 Jun 2018 |

DOIs | |

Publication status | Published - 30 Sep 2018 |

### Fingerprint

### Keywords

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

### Cite this

}

*IEEE Signal Processing Letters*, vol. 25, no. 9, pp. 1305-1309. https://doi.org/10.1109/LSP.2018.2849685

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

Research output: Contribution to journal › Article

TY - JOUR

T1 - Shift-enabled graphs

T2 - graphs where shift-invariant filters are representable as polynomials of shift operations

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 -