The graph FRI framework-spline wavelet theory and sampling on circulant graphs

Abstract

The objective of this work is to consider sparse representations of certain classes of signals on circulant graphs, by introducing families of graph wavelets which possess vanishing (exponential) moment properties. In light of this, we propose a novel framework of sampling and perfect reconstruction of sparse and wavelet-sparse signals on circulant graphs, which we denote as the Graph FRI framework, as an extension to the traditional discrete case. Given the dimensionality-reduced GFT of a sparse signal on a graph G, we can perfectly reconstruct the latter, while inferring a distinct down-sampling pattern and the structure of the associated coarsened graph through decomposition of the GFT-basis as the product between a coefficient matrix C and the multiresolution filtering operation with a low-pass graph e-spline filter. Hereby, we demonstrate that for a sufficiently banded adjacency matrix A of G, the obtained coarse graph preserves the original generating set S of G in a scheme of spectral sampling with respect to the original eigenbasis of A.