Geometric graphs form an important family of hidden structures behind data. In this paper, we develop an efficient and robust algorithm to infer a graph skeleton of a high-dimensional point cloud dataset (PCD). Previously, there has been much work to recover a hidden graph from a low-dimensional density field, or from a relatively clean high-dimensional PCD. Our proposed approach builds upon the recent line of work on using a persistence-guided discrete Morse (DM) theory based approach to reconstruct a geometric graph from a density field defined over a low-dimensional triangulation. In particular, we first give a very simple generalization of this DM-based algorithm from a density-function perspective to a general filtration perspective. On the theoretical front, we show that the output of the generalized algorithm contains a so-called lexicographic-optimal persistent cycle basis w.r.t the input filtration, justifying that the output is indeed meaningful. On the algorithmic front, the generalization allows us to combine sparsified weighted Rips filtration to develop a new graph reconstruction algorithm for noisy point cloud data. The new algorithm is robust to background noise and non-uniform distribution of input points, and we provide various experimental results to show its effectiveness.
翻译:几何图形形成了数据背后隐藏结构的重要组合。 在本文中, 我们开发了一个高效和强大的算法, 以推断高维点云数据集( PCD) 的图形骨架。 以前, 从低维密度场或相对清洁的高维 PCD 中, 已经做了很多工作来回收隐藏的图形。 我们建议的方法基于最近关于使用持久性- 制导离散 Morse (DM) 理论的工作线, 以从低维三角测量定义的密度字段中重建一个几何图形。 特别是, 我们首先从密度- 功能角度将DM 基算法简单化为一般过滤角度。 在理论前, 我们显示通用算法的输出含有所谓的词法- 优化- 持久性循环基础 w. r. t 输入过滤, 证明输出确实有意义。 在算法前, 常规化使我们能够将吸附的加权精度提取精度提取法进行新的图形重度云层云层数据重组算法。 在理论前, 新的算法中, 提供了各种输入结果的稳健性, 和不强度的实验性背景。