Geometric Conditions for the Recovery of Sparse Signals on Graphs from Measurements Generated with Heat Kernels

This 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.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Houston

Year dc:date.issued

2023

Author dc:creator

• May, Jennifer J.

Advisor dc:contributor.advisor

• Bodmann, Bernhard G.

Committee members dc:contributor.committeemember

• Labate, Demetrio
• Mang, Andreas
• Bittner, Eric R.

• signal processing on graphs
• linear programming
• dual certificates

Statement dc:rights

• The 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).

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/10657/15927

OAI identifier oai:identifier

oai:uh-ir.tdl.org:10657/15927