Bodmann, Bernhard G.2024-01-20August 2022023-08https://hdl.handle.net/10657/15927This dissertation establishes results on signal recovery for graphs, when the signals are functions with small support and what is observed is a noisy version of the signal smoothed by evolving it under the heat equation governed by the graph Laplacian. The results discussed here are in close analogy to the mathematical theory of super-resolution developed by Cand`es and Fernandez-Granda for finitely supported measures on Euclidean spaces. As in the Euclidean case, recovery guarantees depend on the size of the support, a distance separation for elements in the support and a time limit for the heat kernels appearing in the measured signal. This dissertation includes a comparison of linear recovery strategies, results of an exhaustive search, and a concrete recovery algorithm. The main emphasis is on the accuracy of estimates for noisy signal recovery based on minimizing the 1-norm, which is a strategy central to compressed sensing. In contrast to the Euclidean case, the graph setting does not have a straightforward implementation of a Fourier transform with its convenient properties. Instead, the results discussed here depend on bounds for the heat kernel and diagonally dominant matrices. The combination of 1-norm minimization with conditions for the existence of a dual certificate offers the widest range of validity in the interplay between sparsity, separation and time limit for the heat kernels that permit noisy recovery guarantees.application/pdfengThe author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).signal processing on graphslinear programmingdual certificates2024-01-20Thesisborn digital