Interpolating Graph Signals using Positive Definite Graph Basis Functions

To interpolate graph signals using generalized shifts of a graph basis function (GBF), we introduce the concept of positive definite functions on graphs. This concept blends kernel-based interpolation with spectral theory on graphs and can be seen as the graph equivalent of radial basis function interpolation in Euclidean spaces or spherical basis functions. We present several descriptions of positive definite functions on graphs, the most relevant one is a Bochner type characterization involving positive Fourier coefficients. These descriptions enable us to construct GBF’s and delve deeper into GBF interpolation: we can characterize the native spaces of the interpolants, we provide explicit estimates for interpolation error and infer bounds for numerical stability. Finally, we show an application where GBF interpolation is used to obtain quadrature formulas on graphs.