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 输入过滤, 证明输出确实有意义。 在算法前, 常规化使我们能够将吸附的加权精度提取精度提取法进行新的图形重度云层云层数据重组算法。 在理论前, 新的算法中, 提供了各种输入结果的稳健性, 和不强度的实验性背景。

0
下载
关闭预览

相关内容

专知会员服务
42+阅读 · 2020年12月18日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Jointly Improving Summarization and Sentiment Classification
黑龙江大学自然语言处理实验室
3+阅读 · 2018年6月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
1+阅读 · 2022年2月17日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Arxiv
4+阅读 · 2017年1月2日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Jointly Improving Summarization and Sentiment Classification
黑龙江大学自然语言处理实验室
3+阅读 · 2018年6月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员