Document Open Access Logo

Topological Data Analysis in Information Space

Authors Herbert Edelsbrunner, Žiga Virk, Hubert Wagner

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.31.pdf
  • Filesize: 1.29 MB
  • 14 pages

Document Identifiers

Author Details

Herbert Edelsbrunner
  • IST Austria (Institute of Science and Technology Austria) , Am Campus 1, 3400 Klosterneuburg, Austria
Žiga Virk
  • Faculty of Computer and Information Science, University of Ljubljana , Vecna pot 113, 1000 Ljubljana, Slovenia
Hubert Wagner
  • IST Austria (Institute of Science and Technology Austria) , Am Campus 1, 3400 Klosterneuburg, Austria

Funding

This research is partially supported by the Office of Naval Research, through grant no. N62909-18-1-2038, and the DFG Collaborative Research Center TRR 109, "Discretization in Geometry and Dynamics", through grant no. I02979-N35 of the Austrian Science Fund (FWF).

Cite As Get BibTex

Herbert Edelsbrunner, Žiga Virk, and Hubert Wagner. Topological Data Analysis in Information Space. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.31

Abstract

Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Computational topology
  • persistent homology
  • information theory
  • entropy

Metrics

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

Related Versions

References

  1. R. Adler. TOPOS, and why we should care about it. IMS Bulletin, 43, 2014. Google Scholar
  2. E. Akin. The Geometry of Population Genetics. Springer, Berlin, 1979. Google Scholar
  3. S. Amari and H. Nagaoka. Methods of Information Geometry. Amer. Math. Soc., Providence, Rhode Island, 2000. Google Scholar
  4. P.L. Antonelli et al. The geometry of random drift I-VI. Adv. Appl. Prob., 9-12, 1977-80. Google Scholar
  5. A. Banerjee, S. Merugu, I.S. Dhillon, and J. Ghosh. Clustering with Bregman divergences. J. Mach. Learn. Res., 6:1705-1749, 2005. Google Scholar
  6. U. Bauer. Fast Rips in the browser, 2016. URL: https://www.ctralie.com/Software/jsTDA.
  7. U. Bauer and M. Lesnick. Induced matchings and the algebraic stability of persistence barcodes. J. Comput. Geom., 6:162-191, 2015. Google Scholar
  8. J.-D. Boissonnat, F. Nielsen, and R. Nock. Bregman Voronoi diagrams. Discrete Comput. Geom., 44:281-307, 2010. Google Scholar
  9. K. Borsuk. On the imbedding of systems of compacta in simplicial complexes. Fund. Math., 35:217-234, 1948. Google Scholar
  10. L.M. Bregman. The relaxation method of finding the common point of convex sets and its applications to the solution of problems in convex programming. USSR Comput. Math. Math. Phys., 7:200-217, 1967. Google Scholar
  11. G. Carlsson. Topology and data. Bull. Amer. Math. Soc., 46:255-308, 2009. Google Scholar
  12. F. Chazal, de Silva, V., M. Glisse, and S. Oudot. The Structure and Stability of Persistence Modules. SpringerBriefs in Mathematics, Springer, 2016. Google Scholar
  13. D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discrete Comput. Geom., 37:103-120, 2007. Google Scholar
  14. I. Csiszár and J. Körner. Coding Theory for Discrete Memoryless Systems. Cambridge Univ. Press, Cambridge, England,, 2011. Google Scholar
  15. Edelsbrunner, H., and J.L. Harer. Computational Topology. An Introduction. Amer. Math. Soc., Providence, Rhode Island, 2010. Google Scholar
  16. H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete Comput. Geom., 28:511-533, 2002. Google Scholar
  17. H. Edelsbrunner and A. Nikitenko. Random inscribed polytopes have similar radius functions as Poisson-Delaunay mosaics,, 2016. URL: http://arxiv.org/abs/1705.02870.
  18. H. Edelsbrunner and H. Wagner. Topological data analysis with Bregman divergences. In "Proc. 33rd Ann. Symp. Comput. Geom., 2017", 1-16, pages 1-16, 2017. Google Scholar
  19. D.M. Endres and J.E. Schindelin. A new metric for probability distributions. IEEE Trans. Inform. Theory, 49:1858-1860, 2003. Google Scholar
  20. Edelsbrunner H., Ž Virk, and H. Wagner. Smallest Enclosing Spheres and Chernoff Points in Bregman Geometry. In "Proc. 34rd Ann. Symp. Comput. Geom., 2018", 2018. Google Scholar
  21. A. Hatcher. Algebraic Topology. Cambridge University Press, 2002. Google Scholar
  22. A. Huang. Similarity measures for text document clustering. In "Proc. 6th New Zealand Computer Science Research Student Conference", 49-56, pages 49-56, 2008. Google Scholar
  23. S. Kullback and R.A. Leibler. On information and sufficiency. Ann. Math. Stat., 22:79-86, 1951. Google Scholar
  24. J. Leray. Sur la forme des espaces topologiques et sur les points fixes des représentations. J. Math. Pure Appl., 24:95-167, 1945. Google Scholar
  25. E. Merelli, M. Rucco, P. Sloot, and L. Tesei. Topological characterization of complex systems: using persistent entropy. Entropy, 17:6872-6892, 2015. Google Scholar
  26. M. Morse. Rank and span in functional topology. Ann. Math., 41:419-454, 1940. Google Scholar
  27. F. Nielsen and R. Nock. On the smallest enclosing information disk. In "Proc. 18th Canad. Conf. Comput. Geom., 2006. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact