Tamal K. Dey
ABSTRACT
Algorithms for persistent homology are well-studied where homomorphisms are induced by inclusion maps. In this paper, we propose a practical algorithm for computing persistence under Z2 coefficients for a (monotone) sequence of general simplicial maps and show how these maps arise naturally in some applications of topological data analysis.
A simplicial map can be decomposed into a set of elementary inclusions and vertex collapses--two atomic operations that can be supported efficiently with the notion of simplex annotations for computing persistent homology. A consistent annotation through these atomic operations implies the maintenance of a consistent cohomology basis, hence a homology basis by duality. While the idea of maintaining a cohomology basis through an inclusion is not new, maintaining them through a vertex collapse is new, which constitutes an important atomic operation for simulating simplicial maps. Annotations support the vertex collapse in addition to the usual inclusion quite naturally.
Finally, we exhibit an application of this new tool in which we approximate the persistence diagram of a filtration of Rips complexes where vertex collapses are used to tame the blow-up in size.
- D. Attali, A. Lieutier, and D. Salinas. Efficient data structure for representing and simplifying simplicial complexes in high dimensions. In Proceedings of the Twenty-seventh Annual Symposium on Computational Geometry, SoCG '11, pages 501--509, 2011. Google Scholar
Digital Library
- J.-D. Boissonnat, T. K. Dey, and C. Maria. The compressed annotation matrix: An efficient data structure for computing persistent cohomology. In European Symposium on Algorithms 2013, volume 8125 of Lecture Notes in Computer Science, pages 695--706, 2013.Google ScholarCross Ref
- D. Burghelea and T. K. Dey. Topological persistence for circle-valued maps. Discrete Comput. Geom., 50(1):69--98, 2013.Google ScholarDigital Library
- O. Busaryev, S. Cabello, C. Chen, T. K. Dey, and Y. Wang. Annotating simplices with a homology basis and its applications. In Proceedings of the 13th Scandinavian Conference on Algorithm Theory, SWAT'12, pages 189--200, 2012. Google ScholarDigital Library
- G. Carlsson. Topology and data. Bull. Amer. Math. Soc., 46:255--308, 2009.Google ScholarCross Ref
- G. Carlsson and V. de Silva. Zigzag persistence. Foundations of Computational Mathematics, 10(4):367--405, 2010. Google ScholarDigital Library
- G. Carlsson, V. de Silva, and D. Morozov. Zigzag persistent homology and real-valued functions. In Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, SCG '09, pages 247--256, 2009. Google ScholarDigital Library
- F. Chazal, D. Cohen-Steiner, M. Glisse, L. J. Guibas, and S. Y. Oudot. Proximity of persistence modules and their diagrams. In Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, SCG '09, pages 237--246, 2009. Google ScholarDigital Library
- C. Chen and M. Kerber. An output-sensitive algorithm for persistent homology. Comput. Geom. Theory Appl., 46(4):435--447, 2013. Google ScholarDigital Library
- K. L. Clarkson. Nearest-neighbor searching and metric space dimensions. In In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pages 15--59, 2006.Google Scholar
- D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103--120, 2007. Google ScholarDigital Library
- D. Cohen-Steiner, H. Edelsbrunner, and D. Morozov. Vines and vineyards by updating persistence in linear time. In Proceedings of the Twenty-second Annual Symposium on Computational Geometry, SCG '06, pages 119--126, 2006. Google ScholarDigital Library
- V. de Silva, D. Morozov, and M. Vejdemo-Johansson. Dualities in persistent (co)homology. Inverse Problems, 27(12):124003, 2011.Google ScholarCross Ref
- V. de Silva, D. Morozov, and M. Vejdemo-Johansson. Persistent cohomology and circular coordinates. Discrete & Computational Geometry, 45(4):737--759, 2011. Google ScholarDigital Library
- T. K. Dey, H. Edelsbrunner, S. Guha, and D. V. Nekhayev. Topology preserving edge contraction. Publ. Inst. Math. (Beograd) (N.S, 66:23--45, 1999.Google Scholar
- T. K. Dey, F. Fan, and Y. Wang. Computing topological persistence for simplicial maps, 2012. arXiv:1208.5018v3.Google Scholar
- T. K. Dey, F. Fan, and Y. Wang. Graph induced complex on point data. In Proceedings of the Twenty-ninth Annual Symposium on Computational Geometry, SoCG '13, pages 107--116, 2013. Google ScholarDigital Library
- T. K. Dey, J. Sun, and Y. Wang. Approximating cycles in a shortest basis of the first homology group from point data. Inverse Problems, 27(12):124004, 2011.Google ScholarCross Ref
- H. Edelsbrunner and J. Harer. Computational Topology. American Mathematical Society, 2009.Google ScholarCross Ref
- H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry, 28(4):511--533, 2002.Google ScholarDigital Library
- R. Ghrist. Barcodes: The persistent topology of data. Bull. Amer. Math. Soc., 45:61--75, 2008.Google ScholarCross Ref
- S. Har-Peled and M. Mendel. Fast construction of nets in low dimensional metrics, and their applications. In Proceedings of the Twenty-first Annual Symposium on Computational Geometry, SCG '05, pages 150--158, 2005. Google ScholarDigital Library
- A. Hatcher. Algebraic Topology. Cambridge U. Press, New York, 2002.Google Scholar
- N. Milosavljević, D. Morozov, and P. Skraba. Zigzag persistent homology in matrix multiplication time. In Proceedings of the Twenty-seventh Annual Symposium on Computational Geometry, SoCG '11, pages 216--225, 2011. Google ScholarDigital Library
- D. R. Sheehy. Linear-size approximations to the vietoris-rips filtration. Discrete & Computational Geometry, 49(4):778--796, 2013.Google ScholarDigital Library
- A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete Comput. Geom, 33:249--274, 2005. Google ScholarDigital Library
Index Terms
- Computing Topological Persistence for Simplicial Maps
Recommendations
Note: Combinatorial Alexander Duality—A Short and Elementary Proof
Let X be a simplicial complex with ground set V. Define its Alexander dual as the simplicial complex X *={σ⊆V∣V∖σ ∉ X}. The combinatorial Alexander duality states that the ith reduced homology group of X is isomorphic to the (|V|−i−3)th reduced ...
Note: Combinatorial Alexander Duality--A Short and Elementary Proof
Let X be a simplicial complex with ground set V. Define its Alexander dual as the simplicial complex X*={ź⊆VźVźźźX}. The combinatorial Alexander duality states that the ith reduced homology group of X is isomorphic to the (|V|źiź3)th reduced cohomology ...
Homology of Multi-Parameter Random Simplicial Complexes
We consider a multi-parameter model for randomly constructing simplicial complexes that interpolates between random clique complexes and Linial---Meshulam random k-dimensional complexes. Unlike these models, multi-parameter complexes exhibit nontrivial ...
Comments