Advances in Graph Signal Processing

Abstract

This thesis consists of two parts in both data science and signal processing over graphs. In the first part of this thesis, we aim to solve the problem of graph construction in big data scenario, which is critical for practical tasks, like collaborative filtering in recommender systems, spectral embedding or clustering in learning algorithms. We achieve to accelerate the data-driven graph construction algorithms by relying on an approximation technique for large matrix multiplication, diamond sampling. We show its potential in real problems by extensive experiments. In the second part, we improve the performance of the graph signal reconstructions by exploiting the local properties of graph signals. We propose a node-adaptive regularization with an improved degree of freedom, so a more general signal smoothness assumption is allowed. Different regularization weights design methods are proposed to achieve its best performance. By comparing it with Tikhonov regularization, we observe its superiority in graph signal reconstruction and interpolation, also in graph signal sampling.