Undirected graphs: is the shift-enabled condition trivial or necessary?
It has recently been shown that, contrary to the wide belief that a shift-enabled condition (necessary for any shift-invariant filter to be representable by a graph shift matrix) can be ignored because any non-shift-enabled matrix can be converted to a shift-enabled matrix, such a conversion in general may not hold for a directed graph with non-symmetric shift matrix. This letter extends this prior work, focusing on undirected graphs where the shift matrix is generally symmetric. We show that while, in this case, the shift matrix can be converted to satisfy the original shift-enabled condition, the converted matrix is not associated with the original graph, that is, it does not capture anymore the structure of the graph signal. We show via a counterexample, that a non-shift-enabled matrix cannot be converted to a shift-enabled one and still maintain the topological structure of the underlying graph, which is necessary to facilitate localized signal processing.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Shift-enabled graphs: Graphs where shift-invariant filters are representable as polynomials of shift operations
In digital signal processing, shift-invariant filters 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 …
Deep learning long-range information in undirected graphs with wave networks
Graph algorithms are key tools in many fields of science and technology. Some of these algorithms depend on propagating information between distant nodes in a graph. Recently, there have been a number of deep learning ar…
Shift-invariant spaces, bandlimited spaces and reproducing kernel spaces with shift-invariant kernels on undirected finite graphs
In this paper, we introduce the concept of graph shift-invariant space (GSIS) on an undirected finite graph, which is the linear space of graph signals being invariant under graph shifts, and we study its bandlimiting, k…
Learning Undirected Graphs in Financial Markets
We investigate the problem of learning undirected graphical models under Laplacian structural constraints from the point of view of financial market data. We show that Laplacian constraints have meaningful physical inter…
ClusteringOn Robustness of Consensus over Pseudo-Undirected Path Graphs
Consensus over networked agents is typically studied using undirected or directed communication graphs. Undirected graphs enforce symmetry in information exchange, leading to convergence to the average of initial states,…