Document Open Access Logo

Elder-Rule-Staircodes for Augmented Metric Spaces

Authors Chen Cai, Woojin Kim, Facundo Mémoli, Yusu Wang

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2020.26.pdf
  • Filesize: 0.97 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Topology
  • Theory of computation → Computational geometry
Keywords
  • Persistent homology
  • Multiparameter persistence
  • Barcodes
  • Elder rule
  • Hierarchical clustering
  • Graded Betti numbers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

An augmented metric space (X, d_X, f_X) is a metric space (X, d_X) equipped with a function f_X: X → ℝ. It arises commonly in practice, e.g, a point cloud X in ℝ^d where each point x∈ X has a density function value f_X(x) associated to it. Such an augmented metric space naturally gives rise to a 2-parameter filtration. However, the resulting 2-parameter persistence module could still be of wild representation type, and may not have simple indecomposables. 
In this paper, motivated by the elder-rule for the zeroth homology of a 1-parameter filtration, we propose a barcode-like summary, called the elder-rule-staircode, as a way to encode the zeroth homology of the 2-parameter filtration induced by a finite augmented metric space. Specifically, given a finite (X, d_X, f_X), its elder-rule-staircode consists of n = |X| number of staircase-like blocks in the plane. We show that the fibered barcode, the fibered merge tree, and the graded Betti numbers associated to the zeroth homology of the 2-parameter filtration induced by (X, d_X, f_X) can all be efficiently computed once the elder-rule-staircode is given. Furthermore, for certain special cases, this staircode corresponds exactly to the set of indecomposables of the zeroth homology of the 2-parameter filtration. Finally, we develop and implement an efficient algorithm to compute the elder-rule-staircode in O(n²log n) time, which can be improved to O(n²α(n)) if X is from a fixed dimensional Euclidean space ℝ^d, where α(n) is the inverse Ackermann function.

Cite As Get BibTex

Chen Cai, Woojin Kim, Facundo Mémoli, and Yusu Wang. Elder-Rule-Staircodes for Augmented Metric Spaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.26

Author Details

Chen Cai
  • Department of Computer Science and Engineering, The Ohio State University, Columbus, OH, USA
Woojin Kim
  • Department of Mathematics, The Ohio State University, Columbus, OH, USA
Facundo Mémoli
  • Department of Mathematics and Department of Computer Science and Engineering, The Ohio State University, Columbus, OH, USA
Yusu Wang
  • Department of Computer Science and Engineering, The Ohio State University, Columbus, OH, USA

Funding

This work is supported by NSF grants DMS-1723003, CCF-1740761, DMS-1547357, and IIS-1815697.

Acknowledgements

The authors thank to the anonymous reviewers who made a number of helpful comments to improve the paper. Also, CC and WK thank Cheng Xin for helpful discussions.

References

  1. Gorô Azumaya et al. Corrections and supplementaries to my paper concerning krull-remak-schmidt’s theorem. Nagoya Mathematical Journal, 1:117-124, 1950. Google Scholar
  2. Ulrich Bauer, Magnus B Botnan, Steffen Oppermann, and Johan Steen. Cotorsion torsion triples and the representation theory of filtered hierarchical clustering. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.07322.
  3. Magnus Botnan and Michael Lesnick. Algebraic stability of zigzag persistence modules. Algebraic & geometric topology, 18(6):3133-3204, 2018. Google Scholar
  4. Chen Cai, Woojin Kim, Mémoli Facundo, and Yusu Wang. Elder-rule-staircodes for augmented metric spaces. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.04523.
  5. Chen Cai and Yusu Wang. Understanding the power of persistence pairing via permutation test. arXiv preprint, 2020. URL: http://arxiv.org/abs/2001.06058.
  6. G. Carlsson and A. Zomorodian. The theory of multidimensional persistence. Discrete & Computational Geometry, 42(1):71-93, 2009. URL: https://doi.org/doi:10.1007/s00454-009-9176-0.
  7. Gunnar Carlsson and Facundo Mémoli. Characterization, stability and convergence of hierarchical clustering methods. Journal of machine learning research, 11(Apr):1425-1470, 2010. Google Scholar
  8. Gunnar Carlsson and Facundo Mémoli. Multiparameter hierarchical clustering methods. In Classification as a Tool for Research, pages 63-70. Springer, 2010. Google Scholar
  9. Mathieu Carriere, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. A general neural network architecture for persistence diagrams and graph classification. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.09378.
  10. Andrea Cerri, Barbara Di Fabio, Massimo Ferri, Patrizio Frosini, and Claudia Landi. Betti numbers in multidimensional persistent homology are stable functions. Mathematical Methods in the Applied Sciences, 36(12):1543-1557, 2013. Google Scholar
  11. Frédéric Chazal, David Cohen-Steiner, Leonidas J Guibas, Facundo Mémoli, and Steve Y Oudot. Gromov-Hausdorff stable signatures for shapes using persistence. In Computer Graphics Forum, volume 28 (5), pages 1393-1403. Wiley Online Library, 2009. Google Scholar
  12. Francis Chin and David Houck. Algorithms for updating minimal spanning trees. Journal of Computer and System Sciences, 16(3):333-344, 1978. Google Scholar
  13. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103-120, 2007. Google Scholar
  14. Justin Curry. The fiber of the persistence map for functions on the interval. Journal of Applied and Computational Topology, 2(3-4):301-321, 2018. Google Scholar
  15. Tamal K Dey and Cheng Xin. Generalized persistence algorithm for decomposing multi-parameter persistence modules. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.03766.
  16. Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathematical Soc., 2010. Google Scholar
  17. David Eisenbud. Commutative Algebra: with a view toward algebraic geometry, volume 150. Springer Science & Business Media, 2013. Google Scholar
  18. Christoph Hofer, Roland Kwitt, Marc Niethammer, and Andreas Uhl. Deep learning with topological signatures. In Advances in Neural Information Processing Systems, pages 1634-1644, 2017. Google Scholar
  19. Woojin Kim and Facundo Mémoli. Generalized persistence diagrams for persistence modules over posets. arXiv preprint, 2018. URL: http://arxiv.org/abs/1810.11517.
  20. Woojin Kim and Facundo Mémoli. Discrete & Computational Geometry, pages 1-45, 2020. URL: https://doi.org/10.1007/s00454-019-00168-w.
  21. Kevin P. Knudson. A refinement of multi-dimensional persistence. Homology, Homotopy and Applications, 10(1):259-281, 2008. Google Scholar
  22. Claudia Landi. The rank invariant stability via interleavings. In Research in Computational Topology, pages 1-10. Springer, 2018. Google Scholar
  23. Michael Lesnick. The theory of the interleaving distance on multidimensional persistence modules. Found. Comput. Math., 15(3):613-650, June 2015. URL: https://doi.org/10.1007/s10208-015-9255-y.
  24. Michael Lesnick and Matthew Wright. Interactive visualization of 2-d persistence modules. arXiv preprint, 2015. URL: http://arxiv.org/abs/1512.00180.
  25. Michael Lesnick and Matthew Wright. Computing minimal presentations and betti numbers of 2-parameter persistent homology. arXiv preprint, 2019. URL: http://arxiv.org/abs/1902.05708.
  26. Alex McCleary and Amit Patel. Multiparameter persistence diagrams. arXiv preprint, 2019. URL: http://arxiv.org/abs/1905.13220v3.
  27. Amit Patel. Generalized persistence diagrams. Journal of Applied and Computational Topology, 1(3-4):397-419, 2018. Google Scholar
  28. Irena Peeva. Graded syzygies, volume 14. Springer Science & Business Media, 2010. Google Scholar
  29. Zane Smith, Samir Chowdhury, and Facundo Mémoli. Hierarchical representations of network data with optimal distortion bounds. In Signals, Systems and Computers, 2016 50th Asilomar Conference on, pages 1834-1838. IEEE, 2016. Google Scholar
  30. Qi Zhao and Yusu Wang. Learning metrics for persistence-based summaries and applications for graph classification. In 33rd Annu. Conf. Neural Inf. Processing Systems (NeuRIPS), 2019. to appear. Google Scholar
  31. Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. Discrete & Computational Geometry, 33(2):249-274, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact
OSZAR »