A higher-dimensional homologically persistent skeleton. (English) Zbl 1423.55008
Summary: Real data is often given as a point cloud, i.e. a finite set of points with pairwise distances between them. An important problem is to detect the topological shape of data – for example, to approximate a point cloud by a low-dimensional non-linear subspace such as an embedded graph or a simplicial complex. Classical clustering methods and principal component analysis work well when data points split into good clusters or lie near linear subspaces of a Euclidean space.
Methods from topological data analysis in general metric spaces detect more complicated patterns such as holes and voids that persist for a large interval in a 1-parameter family of shapes associated to a cloud. These features can be visualized in the form of a 1-dimensional homologically persistent skeleton, which optimally extends a minimum spanning tree of a point cloud to a graph with cycles. We generalize this skeleton to higher dimensions and prove its optimality among all complexes that preserve topological features of data at any scale.
Methods from topological data analysis in general metric spaces detect more complicated patterns such as holes and voids that persist for a large interval in a 1-parameter family of shapes associated to a cloud. These features can be visualized in the form of a 1-dimensional homologically persistent skeleton, which optimally extends a minimum spanning tree of a point cloud to a graph with cycles. We generalize this skeleton to higher dimensions and prove its optimality among all complexes that preserve topological features of data at any scale.
MSC:
| 55N35 | Other homology theories in algebraic topology |
| 18G99 | Homological algebra in category theory, derived categories and functors |
| 05E45 | Combinatorial aspects of simplicial complexes |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Björner, A., Topological methods, (Handbook of Combinatorics, vol. 2, (1995), MIT Press), 1819-1872 · Zbl 0851.52016 |
| [2] | Bolker, E. D., Simplicial geometry and transportation polytopes, Trans. Amer. Math. Soc., 217, 121-142, (1976) · Zbl 0322.55033 |
| [3] | Carlsson, G., Topology and data, Bull. Amer. Math. Soc., 46, 255-308, (2009) · Zbl 1172.62002 |
| [4] | Carlsson, G., Topological pattern recognition for point cloud data, Acta Numer., 23, 289-368, (2013) · Zbl 1398.68615 |
| [5] | Carlsson, G., On the local behavior of spaces of natural images, Int. J. Comput. Vis., 76, 1-12, (2008) · Zbl 1477.68463 |
| [6] | Chazal, F.; Huang, R.; Sun, J., Gromov-Hausdorff approximation of filament structure using Reeb-type graph, Discrete Comput. Geom., 53, 621-649, (2015) · Zbl 1315.68252 |
| [7] | Chen, C.; Freedman, D., Hardness results for homology localization, Discrete Comput. Geom., 45, 425-448, (2011) · Zbl 1218.68084 |
| [8] | Chernov, A.; Kurlin, V., Reconstructing persistent graph structures from noisy images, Image-A, 3, 19-22, (2013) |
| [9] | Delfinado, C. J.A.; Edelsbrunner, H., An incremental algorithm for Betti numbers of simplicial complexes, (Proceedings of the Symposium on Computational Geometry, (1993), ACM), 232-239 |
| [10] | Dey, T. K.; Fan, F.; Wang, Y., Graph induced complex on data points, (Proceedings of SoCG, (2013)), 107-116 · Zbl 1305.68227 |
| [11] | Duval, A. M.; Klivans, C. J.; Martin, J. L., Simplicial and cellular trees, (Recent Trends in Combinatorics, (2016)), 713-752 · Zbl 1354.05151 |
| [12] | Edelsbrunner, H.; Harer, J., Computational topology: an introduction, (2010), American Mathematical Society · Zbl 1193.55001 |
| [13] | Edelsbrunner, H.; Letscher, L.; Zomorodian, Z., Topological persistence and simplification, Discrete Comput. Geom., 28, 511-533, (2002) · Zbl 1011.68152 |
| [14] | Erickson, E., Combinatorial optimization of cycles and bases, (Zomorodian, Afra, Advances in Applied and Computational Topology, Proceedings of Symposia in Applied Mathematics, vol. 70, (2012), American Mathematical Society), 195-228 · Zbl 1255.68284 |
| [15] | Ge, X., Data skeletonization via Reeb graphs, (Proceedings of NIPS, (2011)) |
| [16] | Ghrist, R., Barcodes: the persistent topology of data, Bull. Amer. Math. Soc., 45, 61-75, (2008) · Zbl 1391.55005 |
| [17] | Hiraoka, Yasuaki; Shirai, Tomoyuki, Minimum spanning acycle and lifetime of persistent homology in the linial-Meshulam process, Random Structures Algorithms, 51, 2, 315-340, (2017) · Zbl 1370.05190 |
| [18] | Kalai, G., Enumeration of q-acyclic simplicial complexes, Israel J. Math., 45, 4, 337-351, (1983) · Zbl 0535.57011 |
| [19] | Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc., 7, 1, 48-50, (1956) · Zbl 0070.18404 |
| [20] | Kurlin, V., A fast and robust algorithm to count topologically persistent holes in noisy clouds, (Proc. CVPR, (2014)), 1458-1463 |
| [21] | Kurlin, V., Auto-completion of contours in sketches, maps and sparse 2D images based on topological persistence, (Proceedings of CTIC, (2014)), 594-601 |
| [22] | Kurlin, V., A homologically persistent skeleton is a fast descriptor of interest points in 2D images, (LNCS, vol. 9256, (2015)), 606-617 |
| [23] | Kurlin, V., A one-dimensional homologically persistent skeleton of an unstructured point cloud in any metric space, Comput. Graph. Forum, 34, 5, 253-262, (2015) |
| [24] | Kurlin, V., A fast persistence-based segmentation of 2D clouds with provable guarantees, Pattern Recogn. Lett., 83, 3-12, (2016) |
| [25] | Lewiner, T.; Lopes, H.; Tavares, G., Applications of Forman’s discrete Morse theory to topology visualization and mesh compression, IEEE Trans. Vis. Comput. Graph., 10, 499-508, (2004) |
| [26] | Scott, D., Outline of a mathematical theory of computation, 30, (1970), OUCL, Tech. rep. PRG02 |
| [27] | Skraba, P.; Thoppe, G.; Yogeshwaran, D., Randomly weighted d-complexes: minimal spanning acycles and persistence diagrams, (2017) |
| [28] | Spanier, E. H., Algebraic topology, (1966), McGraw-Hill Book Co. · Zbl 0145.43303 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
