Bibliographic Metadata

Efficient iterative reconstruction of sampled graph signals / von Sara Abbasi
AuthorAbbasi, Sara
CensorGörtz, Norbert
PublishedWien, 2018
Description65 Seiten : Illustrationen, Diagramme
Institutional NoteTechnische Universität Wien, Diplomarbeit, 2018
Document typeThesis (Diplom)
Keywords (DE)Sampled Graph Signals / Recovery / Efficient Iterative Algorithms
Keywords (EN)Sampled Graph Signals / Recovery / Efficient Iterative Algorithms
URNurn:nbn:at:at-ubtuw:1-111049 Persistent Identifier (URN)
 The work is publicly available
Efficient iterative reconstruction of sampled graph signals [1.18 mb]
Abstract (English)

Graph signal processing is an emerging field of large-scale data analysis that aims to provide useful algebraic signal processing tools to process data defined on graph domains. We use the algebraic approach of graph signal processing to introduce basic concepts, such as graph filters, graph Fourier transform, sampling on graphs and the perfect recovery of sampled graph signals. In this thesis, we investigate the performance of an iterative recovery algorithm. The considered method is universally applicable to general graph weight matrices and has an analytic upper error bound that allows to predict the number of iterations as a function of the desired accuracy. The performance of the iterative algorithm for different weight matrices with entries taken from different random distributions (either uniform, Gaussian or discrete distribution) is compared. Moreover, the impact of multiple factors, such as the signal dimension, the size of the frequency support set, the number of measured signal components, and the sparsity factor of the weight matrices is analyzed for different desired accuracies. The simulations show that the iterative algorithm performs considerably better in terms of complexity than the classical matrix inversion used in the perfect recovery theorem, when a proper proportion between the signal dimension, frequency support set and number of measured signal components is chosen. Moreover, a significant reduction of the required number of iterations can be achieved, when a lower accuracy of the recovered signal is allowed. Furthermore, the analysis of the results suggested an approach to avoid the computation of the largest and smallest eigenvalue of each realization of the weight matrix, that allows further complexity reduction of the iterative algorithm.

The PDF-Document has been downloaded 17 times.