|
|
|
“Scalable Sampling and Reconstruction for Graph Signals”
by Ajinkya Jayawant
August 2023
Processing data such as spatially scattered weather measurements or point clouds generated from 3D scans is a challenge due to the lack of an inherent structure to the data. Graphs are convenient tools to analyze and process such unstructured data with algorithms analogous to those in traditional signal processing, which treat the data as a graph signal. However, measuring the whole graph signal can be expensive. Observing a limited subset of graph nodes may be better in such cases, i.e., sampling the graph signal and inferring information at the remaining nodes using reconstruction algorithms.
Although graph signal sampling and reconstruction algorithms exist in the literature, making them practical enough to be used in real-life applications requires numerous theoretical and fundamental improvements. One such requirement is that the algorithm should not require substantially more execution time as the number of vertices and edges in the graph increases. Even if the algorithm execution time scales well with the graph size, some samples may get corrupted. Reconstruction of such data is challenging and requires knowledge of the signal model or its parameters, which are commonly assumed to be known in the literature but in practice have to be estimated.
In this thesis, we propose algorithms to minimize the reconstruction error when sampling in the presence of signal corruption, estimate reconstruction error as a function of the signal bandwidth and develop scalable graph sampling algorithms, in particular algorithms amenable to parallelization. This makes the graph signal reconstruction algorithms more flexible and increases the capabilities of the graph sampling algorithms. Through these improvements, we push the limits of graph signal sampling and reconstruction even further.