Diagonalizable Shift And Filters For Directed Graphs Based On The Jordan-Chevalley Decomposition

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_D$ obtained via the Jordan-Chevalley decomposition. This means, as we show, that $A_D$ 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_D$ adds and removes edges compared to $A$.