tutorial

Computing Topological Persistence for Simplicial Maps

Authors:

Yusu WangAuthors Info & Claims

SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

Pages 345 - 354

https://doi.org/10.1145/2582112.2582165

Published: 08 June 2014 Publication History

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.

References

[1]

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.

Digital Library

[2]

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.

[3]

D. Burghelea and T. K. Dey. Topological persistence for circle-valued maps. Discrete Comput. Geom., 50(1):69--98, 2013.

Digital Library

[4]

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.

Digital Library

[5]

G. Carlsson. Topology and data. Bull. Amer. Math. Soc., 46:255--308, 2009.

[6]

G. Carlsson and V. de Silva. Zigzag persistence. Foundations of Computational Mathematics, 10(4):367--405, 2010.

Digital Library

[7]

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.

Digital Library

[8]

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.

Digital Library

[9]

C. Chen and M. Kerber. An output-sensitive algorithm for persistent homology. Comput. Geom. Theory Appl., 46(4):435--447, 2013.

Digital Library

[10]

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.

[11]

D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103--120, 2007.

Digital Library

[12]

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.

Digital Library

[13]

V. de Silva, D. Morozov, and M. Vejdemo-Johansson. Dualities in persistent (co)homology. Inverse Problems, 27(12):124003, 2011.

[14]

V. de Silva, D. Morozov, and M. Vejdemo-Johansson. Persistent cohomology and circular coordinates. Discrete & Computational Geometry, 45(4):737--759, 2011.

Digital Library

[15]

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.

[16]

T. K. Dey, F. Fan, and Y. Wang. Computing topological persistence for simplicial maps, 2012. arXiv:1208.5018v3.

[17]

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.

Digital Library

[18]

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.

[19]

H. Edelsbrunner and J. Harer. Computational Topology. American Mathematical Society, 2009.

[20]

H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry, 28(4):511--533, 2002.

Digital Library

[21]

R. Ghrist. Barcodes: The persistent topology of data. Bull. Amer. Math. Soc., 45:61--75, 2008.

[22]

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.

Digital Library

[23]

A. Hatcher. Algebraic Topology. Cambridge U. Press, New York, 2002.

[24]

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.

Digital Library

[25]

D. R. Sheehy. Linear-size approximations to the vietoris-rips filtration. Discrete & Computational Geometry, 49(4):778--796, 2013.

Digital Library

[26]

A. Zomorodian and G. Carlsson. Computing persistent homology. Discrete Comput. Geom, 33:249--274, 2005.

Digital Library

Cited By

Yoshizawa SMichikawa TYokota H(2024)Topological Delaunay Graph for Efficient 3D Binary Image AnalysisInternational Journal of Automation Technology10.20965/ijat.2024.p063218:5(632-650)Online publication date: 5-Sep-2024
https://doi.org/10.20965/ijat.2024.p0632
Buchet MB Dornelas BKerber M(2024)Sparse Higher Order Čech FiltrationsJournal of the ACM10.1145/366608571:4(1-23)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1145/3666085
Ramamurthi YChattopadhyay A(2024)A Topological Distance Between Multi-Fields Based on Multi-Dimensional Persistence DiagramsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.331476330:9(5939-5952)Online publication date: Sep-2024
https://doi.org/10.1109/TVCG.2023.3314763
Show More Cited By

Index Terms

Computing Topological Persistence for Simplicial Maps
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

June 2014

588 pages

ISBN:9781450325943

DOI:10.1145/2582112

Program Chairs:
Siu-Wing Cheng
HKUST
,
Olivier Devillers
INRIA

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed limited

Conference

SOCG'14

SOCG'14: Annual Symposium on Computational Geometry

June 8 - 11, 2014

Kyoto, Japan

Acceptance Rates

SOCG'14 Paper Acceptance Rate 60 of 175 submissions, 34%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
364
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)5

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yoshizawa SMichikawa TYokota H(2024)Topological Delaunay Graph for Efficient 3D Binary Image AnalysisInternational Journal of Automation Technology10.20965/ijat.2024.p063218:5(632-650)Online publication date: 5-Sep-2024
https://doi.org/10.20965/ijat.2024.p0632
Buchet MB Dornelas BKerber M(2024)Sparse Higher Order Čech FiltrationsJournal of the ACM10.1145/366608571:4(1-23)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1145/3666085
Ramamurthi YChattopadhyay A(2024)A Topological Distance Between Multi-Fields Based on Multi-Dimensional Persistence DiagramsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.331476330:9(5939-5952)Online publication date: Sep-2024
https://doi.org/10.1109/TVCG.2023.3314763
Guillou PVidal JTierny J(2024)Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data – An Algorithm and a BenchmarkIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.323800830:4(1897-1915)Online publication date: Apr-2024
https://doi.org/10.1109/TVCG.2023.3238008
Herick MJoachim MVahrenhold J(2024)Adaptive approximation of persistent homologyJournal of Applied and Computational Topology10.1007/s41468-024-00192-7Online publication date: 8-Oct-2024
https://doi.org/10.1007/s41468-024-00192-7
Bertrand GNajman L(2024)Morse FramesDiscrete Geometry and Mathematical Morphology10.1007/978-3-031-57793-2_28(364-376)Online publication date: 2024
https://doi.org/10.1007/978-3-031-57793-2_28
Blumberg ALesnick M(2023)Universality of the homotopy interleaving distanceTransactions of the American Mathematical Society10.1090/tran/8738Online publication date: 14-Sep-2023
https://doi.org/10.1090/tran/8738
Fugacci UKerber MRolle A(2023)Compression for 2-parameter persistent homologyComputational Geometry: Theory and Applications10.1016/j.comgeo.2022.101940109:COnline publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.comgeo.2022.101940
Kindelan RFrías JCerda MHitschfeld N(2023)A topological data analysis based classifierAdvances in Data Analysis and Classification10.1007/s11634-023-00548-418:2(493-538)Online publication date: 1-Jul-2023
https://doi.org/10.1007/s11634-023-00548-4
Dey TMandal SMukherjee S(2022)Gene expression data classification using topology and machine learning modelsBMC Bioinformatics10.1186/s12859-022-04704-z22:S10Online publication date: 20-May-2022
https://doi.org/10.1186/s12859-022-04704-z
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents