Title: Optimized sampling of graph signals
Language: English
Authors: Miklausic, Valerija 
Qualification level: Diploma
Keywords: Signalverabreitung; Graph-Signale; Rekonstruktion; Abtastung
Signal processing; Graph signals; reconstruction; Sampling
Advisor: Görtz, Norbert 
Assisting Advisor: Hannak, Gabor 
Issue Date: 2017
Number of Pages: 71
Qualification level: Diploma
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,
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-93046
http://hdl.handle.net/20.500.12708/4808
Library ID: AC13428021
Organisation: E389 - Institute of Telecommunications 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

21
checked on Apr 2, 2021

Download(s)

108
checked on Apr 2, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.