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, Hannah Schreiber: Barcodes of Towers and a Streaming Algorithm for Persistent Homology. Accepted for the 33rd International Symposium on Computational Geometry (SoCG 2017). Available at arXiv:1701.02208.
  • 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).
  • Aruni Choudhary, Michael Kerber, Sharath Raghvendra: Polynomial-Sized Topological Approximations Using The Permutahedron. 32nd International Symposium on Computational Geometry (SoCG 2016), pp.31:1-31:16, 2016 (link). A more complete version is available at arXiv:1601.02732.
  • Michael Kerber, Dmitriy Morozov, Arnur Nigmetov: Geometry helps to Compare Persistence Diagrams. Algorithm Engineering and Experiments (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.