Diagonalizable Shift and Filters for Directed Graphs Based on the Jordan-Chevalley Decomposition
Panagiotis Misiakos, Chris Wendler, Markus Püschel
Abstract
Graph signal processing on directed graphs poses theoretical challenges since an eigendecomposition of filters is in general not available. Instead, Fourier analysis requires a Jordan decomposition and the frequency response is given by the Jordan normal form, whose computation is numerically unstable for large sizes. In this paper, we propose to replace a given adjacency shift A by a diagonalizable shift A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</sub> obtained via the Jordan-Chevalley decomposition. This means, as we show, that A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</sub> generates the subalgebra of all diagonalizable filters and is itself a polynomial in A (i.e., a filter). For several synthetic and real-world graphs, we show how A <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">D</sub> adds and removes edges compared to A.
BibTeX
@inproceedings{icassp2020_diagonalizablesh,
title = {Diagonalizable Shift and Filters for Directed Graphs Based on the Jordan-Chevalley Decomposition},
author = {Panagiotis Misiakos and Chris Wendler and Markus Püschel},
booktitle = {ICASSP 2020},
year = {2020}
}