Doctor of Philosophy, The Ohio State University, 2020, Computer Science and Engineering

Removing noise and recovering signals is a fundamental task in the area of data analysis. Noise is everywhere: In supervised learning, samples in the training set can be mislabeled. In road network reconstruction, wrong trajectories could come from the low sampling rate and bad GPS signals. Despite the fact that much work has been done in this area, the problem remains challenging because real-life noise is complicated to model and usually little knowledge of the ground truth is available. On the other hand, in many situations, assuming that the data presumably samples from a hidden space called ground truth, different types of noise such as Gaussian and/or ambient noise can be associated with it. For all types of noise, signals should prevail in density, which means that the data density should be higher near the ground truth. My work deals with such noisy data in two contexts. In the first scenario, we consider eliminating noise from a point cloud data sampled from a hidden ground truth K in a metric space. General denoising methods such as deconvolution and thresholding require the user to choose parameters and noise models. We first give a denoising algorithm with one parameter and assume a very general sampling condition. We provide the theoretical guarantee for this algorithm and argue that the one parameter cannot be avoided. We then propose a parameter-free denoising algorithm with a sampling condition that is slightly stronger. We show our method performs well on noisy uniform/adaptive point clouds by experiments on a 2D density field, 3D models, and handwritten digits. In the second scenario, we consider reconstructing a hidden graph from a noisy sample. Recently, a method based on Discrete Morse theory and persistent homology finds its applications in multiple areas, for example, reconstructing road networks from GPS trajectories and extracting filamentary structures from cosmology data. However, little theoretical analysis exists for the Discrete (open full item for complete abstract)

Committee: Tamal Dey (Advisor); Yusu Wang (Advisor); Han-Wei Shen (Committee Member) Subjects: Computer Science