A Dual Domain Approach to Graph Signal Processing

Graph Signal Processing (GSP) extends Discrete Signal Processing (DSP) to data supported by graphs by redefining traditional DSP concepts like signals, shift, filtering, and Fourier transform among others. This thesis develops and generalizes standard DSP operations for GSP in an intuitively pleasing way: 1) new concepts in GSP are often designed as natural extensions of DSP concepts; 2) GSP is consistent with DSP, i.e., when the underlying graph G is a directed cyclic graph, GSP becomes DSP; and 3) GSP leads to reinterpretation of well known DSP results and sheds new light on DSP facts and assumptions that are commonly taken for granted. 

We build a theoretical foundation for GSP, introducing fundamental GSP concepts such as spectral graph shift, spectral convolution, spectral graph, spectral graph filters, and spectral delta functions. This leads to a spectral graph signal processing theory (GSP_sp) that is the dual of the vertex based GSP. GSP_sp enables us to develop a unified graph signal sampling theory with GSP vertex and spectral domain dual versions for each of the four standard sampling steps of subsampling, decimation, upsampling, and interpolation. 

To define the graph z-transform, GzT, we introduce the canonical companion model with its canonical companion shift and canonical companion graph. The companion shift and the companion graph modifies the structure of the DSP cyclic directed shift by adding appropriate boundary conditions. 

The companion GSP model and GSP_sp show that, in GSP, there are two distinct models: the eigenvector model from current GSP literature and the canonical model we introduce. In DSP, these two models overlap and are equivalent, obscuring which model should be used in GSP for particular data processing tasks. We illustrate the significance of this dichotomy by presenting a GSP uncertainty principle, interpolating GSP filters, and GSP modulation as natural applications of the canonical companion signal model. In doing so, we show that, while equivalent in DSP, both models are needed for the complete picture in GSP.