Optimized sampling of graph signals

Abstract

A graph signal is a vector, for which complicated dependencies between the vector components can be expressed by a weight matrix that connects components that, e.g., tend to take similar values. A very common example is an image signal (=graph signal), which has a very regular weight matrix, in which neighbouring pixels (=graph signal components) tend to take similar values (textures, such as blue skies, white walls); edges are few, and only here the components take values that are significantly different from one pixel to another. Graph signals can also be defined in various other applications such as recommender systems in online-shopping and in social networks. A common strand of research in the field is how to reconstruct a graph signal from few sampled components of the signal, when the weight matrix is known. The weight matrix is used to regularize and, thereby, solve the reconstruction problem (which as such is under-determined). For so-called Tikhonov regularization the recovery problem can be solved analytically, and, moreover, the well-known Gauss-Seidel iterative algorithm can be used to solve the resulting system of linear equations efficiently (without LU-decomposition, Gaussian elimination or a matrix inversion). Hence, graph signal recovery with Tikhonov regularization is feasible even for very large signal dimension. A particularly interesting problem is how to sample a graph signal with a small number of samples such that the reconstruction with Tikhonov regularization works well (measured by the mean squared error between the original graph signal and its reconstruction). Of course the choice of samples from the graph signal depends on the weight matrix, and it is a main goal of the thesis to analyze and numerically investigate specific sampling schemes. The most simple one is random sampling, which shall be used as a reference scheme. A more sophisticated approach is to exploit the weight matrix to optimize the choice of sampled components.

A graph signal is a vector, for which complicated dependencies between the vector components can be expressed by a weight matrix that connects components that, e.g., tend to take similar values. A very common example is an image signal (=graph signal), which has a very regular weight matrix, in which neighbouring pixels (=graph signal components) tend to take similar values (textures, such as blue skies, white walls); edges are few, and only here the components take values that are significantly different from one pixel to another. Graph signals can also be defined in various other applications such as recommender systems in online-shopping and in social networks. A common strand of research in the field is how to reconstruct a graph signal from few sampled components of the signal, when the weight matrix is known. The weight matrix is used to regularize and, thereby, solve the reconstruction problem (which as such is under-determined). For so-called Tikhonov regularization the recovery problem can be solved analytically, and, moreover, the well-known Gauss-Seidel iterative algorithm can be used to solve the resulting system of linear equations efficiently (without LU-decomposition, Gaussian elimination or a matrix inversion). Hence, graph signal recovery with Tikhonov regularization is feasible even for very large signal dimension. A particularly interesting problem is how to sample a graph signal with a small number of samples such that the reconstruction with Tikhonov regularization works well (measured by the mean squared error between the original graph signal and its reconstruction). Of course the choice of samples from the graph signal depends on the weight matrix, and it is a main goal of the thesis to analyze and numerically investigate specific sampling schemes. The most simple one is random sampling,