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