论文标题
素描持续图
Sketching Persistence Diagrams
论文作者
论文摘要
给定$ n $点的持久图，我们提供了一种算法，该算法产生了$ n $持久图的序列，以瓶颈距离汇聚到输入图，其中$ i $ th具有$ i $ i $ lixption（加权）的点，并且是$ 2 $ - $ 2 $ - 与最接近的持久性图相关图，并具有许多不同的点。对于每个近似值，我们预先计算$ i $ th和$（i+1）$ st之间的最佳匹配。也许令人惊讶的是，可以在$ o（n）$空间中表示整个图表以及匹配顺序。主要方法是使用持久图的贪婪排列的变化来给出良好的Hausdorff近似值并将权重分配给这些子集。尽管由于对角线的效果，但我们提供了一种新的算法来有效计算该排列，尽管持久图中点的隐含尺寸很高。草图也是构成的，以允许在图表之间的豪斯多夫距离（线性时间）快速（线性时间）近似值 - 瓶颈距离上的下限。为了近似瓶颈距离，草图也可以直接用于计算线性尺寸的邻域图，从而避免了用于瓶颈计算的最先进方法中使用的几何数据结构的需求。
Given a persistence diagram with $n$ points, we give an algorithm that produces a sequence of $n$ persistence diagrams converging in bottleneck distance to the input diagram, the $i$th of which has $i$ distinct (weighted) points and is a $2$-approximation to the closest persistence diagram with that many distinct points. For each approximation, we precompute the optimal matching between the $i$th and the $(i+1)$st. Perhaps surprisingly, the entire sequence of diagrams as well as the sequence of matchings can be represented in $O(n)$ space. The main approach is to use a variation of the greedy permutation of the persistence diagram to give good Hausdorff approximations and assign weights to these subsets. We give a new algorithm to efficiently compute this permutation, despite the high implicit dimension of points in a persistence diagram due to the effect of the diagonal. The sketches are also structured to permit fast (linear time) approximations to the Hausdorff distance between diagrams -- a lower bound on the bottleneck distance. For approximating the bottleneck distance, sketches can also be used to compute a linear-size neighborhood graph directly, obviating the need for geometric data structures used in state-of-the-art methods for bottleneck computation.
