Reconstructing Riemannian Metrics From Random Geometric Graphs
Han Huang, Pakawut Jiradilok, and Elchanan Mossel
随机几何图形是在度量空间上定义的随机图形模型。 随机几何图由来自度量空间的先采样点生成,然后独立连接每对采样点,其概率取决于它们的距离。 在最近黄、Jidilok和Mossel <cit.>的实验中,作者研究重建嵌入式流形的问题,形成了一个从流形中取样的随机几何图形,其中边缘概率单调地依赖于嵌入点之间的欧几里得距离。 他们表明,在流形,采样量和连接概率函数的轻度规律性假设下,随着顶点数量的增长,可以恢复嵌入采样点的成对欧几里得距离,以减小误差。 在这项工作中,我们考虑了一个类似的,可以说是更自然的问题,其中指标是流形上的黎曼指标。 再次从流形中采样点,并生成一个随机图,其中连接概率在黎曼距离中是单调的。 也许令人惊讶的是,我们在这个设置中获得了更有力的结果。 与以前只考虑致密图的工作不同,我们提供具有平均度 n^1/2 polylog(n) 的稀疏图的重建算法,其中 n 表示顶点的数量。 我们的算法也是用于距离重建的更高效算法,具有改进的错误边界。 算法的运行时间为 O(n^2 polylog(n)),其高达 polylog 因子与输入图的大小相匹配。 我们的距离误差也几乎与距离估计的体积下限数相匹配。
Random geometric graphs are random graph models defined on metric measure spaces. A random geometric graph is generated by first sampling points from a metric space and then connecting each pair of sampled points independently with a probability that depends on their distance. In recent work of Huang, Jiradilok, and Mossel <cit.>, the authors study the problem of reconstructing an embedded manifold form a random geometric graph sampled from the manifold, where edge probabilities depend monotonic...
