Shift-Invariant Spaces, Bandlimited Spaces and Reproducing Kernel Spaces With Shift-Invariant Kernels on Undirected Finite Graphs

Abstract

In this paper, we introduce the concept of graph shift-invariant spaces (GSISs) of graph signals on undirected finite graphs and investigate their bandlimiting, reproducing kernel, and sampling properties. Bandlimited spaces are the most widely adopted models for representing graph signals. In this paper, under some technical conditions on the graph shift, we show that every GSIS is a graph bandlimited space (GBLS), and every GBLS is a principal GSIS. Functions in a reproducing kernel Hilbert space with shift-invariant kernel on graphs could be learnt with significantly low computational cost. In this paper, we demonstrate that every GSIS is a reproducing kernel Hilbert space with a shift-invariant kernel. Based on the nested Krylov structure of GSISs, we propose a finite-step sampling and reconstruction algorithm in the spatial domain. Its effectiveness is demonstrated on well-localized signals over cycle graphs and the flight delay dataset of the 50 busiest U.S. airports. On this flight delay dataset, the GSIS approach surpasses bandlimited spaces and RKHS models with diffusion and random walk kernels in both model suitability, data fitting capability and practical interpretability.