A k-points-based distance for robust geometric inference
A k-points-based distance for robust geometric inference
复制标题
DOI：
10.3150/20-bej1214
复制
发表时间：
2020-11-01
期刊：
影响因子：
1.5
通讯作者：
Levrard, Clement
中科院分区：
文献类型：
--
作者：
Brecheteau, Claire;Levrard, Clement
分析R-d的紧子流形的距离的子水平集是拓扑数据分析中常用的一种方法，以了解其拓扑结构。因此，拓扑推理过程通常依赖于基于n个样本点的距离估计（离散计算）。地质，33(2005)249-274。在样本点被噪声破坏的情况下，距离测量函数（DTM）第一版。Math. 11(2011) 733-751)是距离到紧集函数的替代。在实践中，近似其子水平集的同调性需要计算n个球的并集的同调性（离散计算）。地球科学，49 (2013)22-45；在第26届ACM-SIAM离散算法研讨会论文集（2015）168-180 SIAM)中，当n很大时，这可能变得棘手。为了同时面对大量点和噪声这两个问题，我们引入了k-power-distance-to-measure函数（k-PDTM）。这个新的紧凑距离替代物是DTM的基于k点的近似值。这k个点是经典k-均值准则的鲁棒化版本的最小值（在第五伯克利研讨会中）。数学。中央集权。和概率（伯克利，加州，1965/66）（1967）281-297加州大学出版社)。k- pdtm的子水平集由k个球的并组成，并且证明了该距离对噪声具有鲁棒性。我们评估了k可能大大小于n的这种近似的质量，并提供了一种从样本中计算这种k- pdtm的算法。数值实验证明了这种k点近似在噪声拓扑推理框架中的良好性能。
Analyzing the sub-level sets of the distance to a compact submanifold of R-d is a common method in topological data analysis, to understand its topology. Therefore, topological inference procedures usually rely on a distance estimate based on n sample points (Discrete Comput. Geom. 33 (2005) 249-274). In the case where sample points are corrupted by noise, the distance-to-measure function (DTM, Found. Comput. Math. 11 (2011) 733-751) is a surrogate for the distance-to-compact-set function. In practice, approximating the homology of its sub-level sets requires to compute the homology of unions of n balls (Discrete Comput. Geom. 49 (2013) 22-45; In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (2015) 168-180 SIAM), that might become intractable whenever n is large. To simultaneously face the two problems of a large number of points and noise, we introduce the k-power-distance-to-measure function (k-PDTM). This new surrogate for the distance-to-compact is a k-points-based approximation of the DTM. These k points are minimizers of a robustified version of the classical k-means criterion (In Proc. Fifth Berkeley Sympos. Math. Statist. and Probability (Berkeley, Calif., 1965/66) (1967) 281-297 Univ. California Press). The sublevel sets of the k-PDTM consist in unions of k balls, and this distance is also proved robust to noise. We assess the quality of this approximation for k possibly drastically smaller than n, and provide an algorithm to compute this k-PDTM from a sample. Numerical experiments illustrate the good behavior of this k-points approximation in a noisy topological inference framework.