TU Graz Logo

Institute of Geometry
Contact   People   Courses & Exams   Events   Research   Lehramtsstudium  
Research project: Algorithms for Topological Data Analysis

This project is funded by the Austrian Science Fund (FWF) under grant P 29984-N35 (2017-21).

The last 15 years have witnessed an increasing research activity on the interface of topological invariants from algebraic topology and the qualitative analysis of data. This has led to the new and rapidly evolving field of topological data analysis (tda). Due to the ever-increasing size and complexity of real data, the key question for the success of the discipline is: how can this mathematically sophisticated theory be applied on large scale data sets?

Bild

This project will contribute novel algorithmic approaches into the major steps of the computational pipeline of tda. In particular, it introduces new techniques into the popular field of approximating filtrations of simplicial complexes, it extends previous successes for the computation of persistent homology to more general and challenging scenarios, and it provides fast algorithms for the comparison of persistence diagrams and related topological invariants. The goal is to advance the pioneer works in these fields to the first mature algorithmic solutions usable for large scale data sets as they occur in application scenarios. Besides these application-driven goals, the project also aims for an improved theoretical understanding of the potentials and the limitations of currently existing and newly developed algorithmic approaches.

We focus on algorithms with provable formal guarantees through asymptotic worst-case analysis and quality bounds for approximation algorithms. At the same time, we aim for practical solutions and investigate the quality of our solution through careful implementation work. We will release successful implementation in the form of publicly available software packages. We expect from this comprehensive point of view to create a far more substantial impact on the field of computational topology than by concentrating solely on a single aspect.

The list of publications below also includes work performed before the runtime of the grant.

Publications
  • Michael Kerber, Alexander Rolle: Fast Minimal Presentations of Bi-Graded Persistence Modules. SIAM Symposium on Algorithm Engineering and Experiments (ALENEX 2021). Available at arXiv:2010.15623.
  • Michael Kerber, Arnur Nigmetov: Metric Spaces with Expensive Distances. Accepted at International Journal of Computational Geometry & Applications. Available at arXiv:1901.08805.
  • Ulderico Fugacci, Michael Kerber, Hugo Manet: Topology-Preserving Terrain Simplification. Proceedings of the 28th International Conference on Advances in Geographic Information Systems (SIGSPATIAL 2020), pp.36-47. Available at arXiv:1912.03032.
  • Michael Kerber, Hannah Schreiber: On the expected complexity of matrix reduction for random complexes. Extended abstract presented at Computer Algebra in Scientific Computing (CASC 2020).
  • Michael Kerber, Arnur Nigmetov: Efficient Approximation of the Matching Distance for 2-parameter persistence. Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020), pp. 53:1-53:16. Available at arXiv:1912.05826.
  • Michael Kerber, Michael Lesnick, Steve Oudot: Exact computation of the matching distance on 2-parameter persistence modules. Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019), pp. 46:1-46:15. Available at arXiv:1812.09085.
  • Ulderico Fugacci, Michael Kerber: Chunk Reduction for Multi-Parameter Persistent Homology. Proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019), pp.37:1-37:14. Available at arXiv:1812.08580.
  • Clement Maria, Hannah Schreiber: Discrete Morse Theory for Computing Zigzag Persistence. WADS 2019: 16th International Symposium on Algorithms and Data Structures, 2019. Available at arXiv:1807.05172.
  • Havard Bjerkevik, Magnus Botnan, Michael Kerber: Computing the interleaving distance is NP-hard. Foundations of Computational Mathematics 20, pp.1237-1271, 2020. (link).
  • Aruni Choudhary, Michael Kerber, Sharath Raghvendra: Improved Topological Approximations by Digitization. ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pp.2675-2688. Available at arXiv:1812.04966
  • Michael Kerber, Hannah Schreiber: Barcodes of Towers and a Streaming Algorithm for Persistent Homology. Discrete and Computational Geometry 61, pp. 852-879, 2019. (link). The conference version appeared at the 33rd International Symposium on Computational Geometry (SoCG 2017).
  • Rene Corbet, Ulderico Fugacci, Michael Kerber, Claudia Landi, Bei Wang: A Kernel for Multi-Parameter Persistent Homology. Computer and Graphics X (2), 2019. Special Section on SMI 2019 (link) (Best paper award).
  • Rene Corbet, Michael Kerber: The Representation Theorem of Persistent Homology Revisited and Generalized. Journal of Applied and Computational Topology 2, pp. 1-31, 2018. (link) Available at arXiv:1707.08864.
  • Aruni Choudhary, Michael Kerber, Sharath Raghvendra: Improved Approximate Rips Filtrations with Shifted Integer Lattices. European Symposium on Algorithms (ESA 2017), pp. 28:1-28:13. Available at arXiv:1706.07399.
  • Aruni Choudhary, Michael Kerber, Sharath Raghvendra: Polynomial-Sized Topological Approximations Using The Permutahedron. Discrete and Computational Geometry (link). The conference version appeared at the 32nd International Symposium on Computational Geometry (SoCG 2016), pp.31:1-31:16, 2016 (link). Also available at arXiv:1601.02732.
  • Ulrich Bauer, Michael Kerber, Jan Reininghaus, Hubert Wagner: PHAT - Persistent Homology Algorithms Toolbox. Journal of Symbolic Computation - Special Issue on Algorithms and Software for Computational Topology (In Press). (pdf)
    © Elsevier 2016. The website of the article is http://dx.doi.org/10.1016/j.jsc.2016.03.008. A short version appeared at the 4th International Congress of Mathematical Software (ICMS 2014).
  • Michael Kerber, Dmitriy Morozov, Arnur Nigmetov: Geometry helps to Compare Persistence Diagrams. Journal of Experimental Algorithms 22, 2017 (link). A conference version appeared at ALENEX 2016, pp.103-112 (pdf) © SIAM 2016.
  • Michael Kerber, Don Sheehy, Primoz Skraba: Persistent Homology and Nested Dissection. ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp.1234-1245. (pdf) © SIAM 2016.