Title: Optimized sampling of graph signals Language: English Authors: Miklausic, Valerija Qualification level: Diploma Keywords: Signalverabreitung; Graph-Signale; Rekonstruktion; AbtastungSignal 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-93046http://hdl.handle.net/20.500.12708/4808 Library ID: AC13428021 Organisation: E389 - Institute of Telecommunications Publication Type: ThesisHochschulschrift Appears in Collections: Thesis

#### Files in this item:

File Description SizeFormat
Miklausic Valerija - 2017 - Optimized sampling of graph signals.pdf3.18 MBAdobe PDF #### 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.