Modeling and Learning Strategies for Graph Signal Processing

Abstract

This thesis proposes methods for modeling and learning over graphs. In the scope of graph modeling, we first address the construction of graphs suitable for compressing images that share strong redundancy — in particular, light-field images. For compression, we leverage the energy concentration in the graph-frequency domain provided by the graph Fourier transform (GFT). We propose methods to construct a sparse adjacency matrix optimized jointly for sets of pixel blocks, considerably reducing the amount of data required for graph representation. A second proposal for graph modeling is the extended adjacency obtained by introducing new edges to an initial sparse adjacency matrix. This methodology uses diffusion distances to measure relations between unconnected nodes. Using the extended adjacency, we define the scale-dependent GFT, which reveals additional spectral information of graph signals. We show that graph signal processing tools benefit from the additional spectral information. In the scope of learning over graphs, this thesis introduces nonlinear graph filters. The proposed nonlinear graph filtering consists of a nonlinearity applied to a combination of graph-shifted versions of the input graph signal. To identify the parameters of the nonlinear graph filter, we first propose the centralized graph kernel least mean squares (GKLMS) algorithm. We develop implementations of the GKLMS using coherence-check and random Fourier features (RFF) to reduce the dictionary size. Using the graph structure, we propose the fully distributed graph-diffusion kernel least mean squares (GDKLMS) algorithm using RFF. Additionally, we propose a second methodology for learning over graphs based on kernel regression. This methodology considers the case where the input signal is not a graph signal. We propose both batch-based and online algorithms with reduced computational-complexity and competitive performance when compared to state-of-the-art methodologies. Moreover, we provide first- and second-order theoretical convergence analysis for all the proposed online algorithms for learning over graphs.