On the Metric Distortion of Embedding Persistence Diagrams into Separable Hilbert Spaces

Authors Mathieu Carrière, Ulrich Bauer



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.21.pdf
  • Filesize: 0.63 MB
  • 15 pages

Document Identifiers

Author Details

Mathieu Carrière
  • Department of Systems Biology, Columbia University, New York, USA
Ulrich Bauer
  • Department of Mathematics, Technical University of Munich (TUM), Germany

Cite As Get BibTex

Mathieu Carrière and Ulrich Bauer. On the Metric Distortion of Embedding Persistence Diagrams into Separable Hilbert Spaces. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.21

Abstract

Persistence diagrams are important descriptors in Topological Data Analysis. Due to the nonlinearity of the space of persistence diagrams equipped with their diagram distances, most of the recent attempts at using persistence diagrams in machine learning have been done through kernel methods, i.e., embeddings of persistence diagrams into Reproducing Kernel Hilbert Spaces, in which all computations can be performed easily. Since persistence diagrams enjoy theoretical stability guarantees for the diagram distances, the metric properties of the feature map, i.e., the relationship between the Hilbert distance and the diagram distances, are of central interest for understanding if the persistence diagram guarantees carry over to the embedding. In this article, we study the possibility of embedding persistence diagrams into separable Hilbert spaces with bi-Lipschitz maps. In particular, we show that for several stable embeddings into infinite-dimensional Hilbert spaces defined in the literature, any lower bound must depend on the cardinalities of the persistence diagrams, and that when the Hilbert space is finite dimensional, finding a bi-Lipschitz embedding is impossible, even when restricting the persistence diagrams to have bounded cardinalities.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
Keywords
  • Topological Data Analysis
  • Persistence Diagrams
  • Hilbert space embedding

Metrics

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

References

  1. Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence Images: A Stable Vector Representation of Persistent Homology. Journal of Machine Learning Research, 18(8):1-35, 2017. Google Scholar
  2. Ulrich Bauer and Michael Lesnick. Induced matchings and the algebraic stability of persistence barcodes. Journal of Computational Geometry, 6(2):162-191, 2015. Google Scholar
  3. Christian Berg, Jens Christensen, and Paul Ressel. Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions. Springer, 1984. Google Scholar
  4. Peter Bubenik. Statistical Topological Data Analysis using Persistence Landscapes. Journal of Machine Learning Research, 16:77-102, 2015. Google Scholar
  5. Gunnar Carlsson. Topology and Data. Bulletin of the American Mathematical Society, 46:255-308, 2009. Google Scholar
  6. Mathieu Carrière, Marco Cuturi, and Steve Oudot. Sliced Wasserstein Kernel for Persistence Diagrams. In Proceedings of the 34th International Conference on Machine Learning, 2017. Google Scholar
  7. Mathieu Carrière, Steve Oudot, and Maks Ovsjanikov. Stable Topological Signatures for Points on 3D Shapes. Computer Graphics Forum, 34, 2015. Google Scholar
  8. Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot. The Structure and Stability of Persistence Modules. Springer, 2016. Google Scholar
  9. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of Persistence Diagrams. Discrete and Computational Geometry, 37(1):103-120, 2007. Google Scholar
  10. Barbara Di Fabio and Massimo Ferri. Comparing Persistence Diagrams Through Complex Vectors. In Image Analysis and Processing - ICIAP 2015, pages 294-305, 2015. Google Scholar
  11. Herbert Edelsbrunner and John Harer. Computational Topology: an introduction. AMS Bookstore, 2010. Google Scholar
  12. Juha Heinonen. Lectures on Analysis on Metric Spaces. Springer, 2001. Google Scholar
  13. Christoph Hofer, Roland Kwitt, Marc Niethammer, and Andreas Uhl. Deep Learning with Topological Signatures. In Advances in Neural Information Processing Systems 30, pages 1633-1643. Curran Associates, Inc., 2017. Google Scholar
  14. Sara Kališnik. Tropical Coordinates on the Space of Persistence Barcodes. Foundations of Computational Mathematics, 2018. Google Scholar
  15. Michael Kerber, Dmitriy Morozov, and Arnur Nigmetov. Geometry Helps to Compare Persistence Diagrams. Journal of Experimental Algorithmics, 22:1.4:1-1.4:20, September 2017. Google Scholar
  16. Genki Kusano, Kenji Fukumizu, and Yasuaki Hiraoka. Persistence Weighted Gaussian Kernel for Topological Data Analysis. In Proceedings of the 33rd International Conference on Machine Learning, pages 2004-2013, 2016. Google Scholar
  17. Genki Kusano, Kenji Fukumizu, and Yasuaki Hiraoka. Kernel Method for Persistence Diagrams via Kernel Embedding and Weight Factor. Journal of Machine Learning Research, 18(189):1-41, 2018. Google Scholar
  18. Yuriy Mileyko, Sayan Mukherjee, and John Harer. Probability measures on the space of persistence diagrams. Inverse Problems, 27(12):124007, 2011. Google Scholar
  19. Steve Oudot. Persistence Theory: From Quiver Representations to Data Analysis. Number 209 in Mathematical Surveys and Monographs. American Mathematical Society, 2015. Google Scholar
  20. Jan Reininghaus, Stefan Huber, Ulrich Bauer, and Roland Kwitt. A Stable Multi-Scale Kernel for Topological Machine Learning. CoRR, abs/1412.6821, 2014. URL: http://arxiv.org/abs/1412.6821.
  21. Jan Reininghaus, Stefan Huber, Ulrich Bauer, and Roland Kwitt. A Stable Multi-Scale Kernel for Topological Machine Learning. In IEEE Conference on Computer Vision and Pattern Recognition, 2015. Google Scholar
  22. James C. Robinson. Dimensions, Embeddings, and Attractors, volume 186 of Cambridge Tracts in Mathematics. Cambridge University Press, 2010. Google Scholar
  23. Katharine Turner, Yuriy Mileyko, Sayan Mukherjee, and John Harer. Fréchet Means for Distributions of Persistence Diagrams. Discrete and Computational Geometry, 52(1):44-70, 2014. 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