Algorithms for topological data analysis

We are living in a time in which huge amounts of data are constantly generated. For instance around 300 hours of video material are uploaded to YouTube every minute. This mass of data calls for intelligent methods to extract the relevant information from a data collection; this task is called data analysis. Application areas include recommendation systems for users of audio or video streaming services or the automatic detection of anomalies on surveillance cameras. In the past 15 years, a novel and perhaps surprising approach of data analysis has been developed: the qualitative properties of a data set are studied with the mathematical theory of algebraic topology. The rough idea is that the data is transformed into a geometric shape and it is studied in what way this shape is connected. As an example, a ball and a doughnut are connected differently because the latter has a hole in its center. Such a topological analysis often reveals valuable information about the data set, as demonstrated by a multitude of applications to realistic scenarios, for instance, in biology, physics, or computer graphics. However, the computation of topological properties on a computer requires a lot of time for large data sets, restricting current uses of the technique to rather small data. The goal of project is to change that: we want to develop computer programs that are able to process data sizes which are out-of-reach with current technology. In this way, we significantly expand the range of applications for which topological data analysis can provide new insights. Such an advancement, however, requires novel ways to compute the relevant topological information from data. To prove the advantages of our novel methods, we will analyze them in the framework of theoretical computer science, but also compare them with existing approaches on realistic data sets. While the latter seems to be the natural measure of quality, the former is equally important because it allows the comparison of computational methods over all possible future inputs, while experiments can only measure the performance of currently available inputs. Designing solutions efficient in both way yields to long-lasting contributions to the research field. This project has a remarkably interdisciplinary character, bringing together algebraic topology, data analysis, geometry, theoretical computer science, and software engineering. It establishes efficient computations as the bridge between abstract mathematics and real-world applications and paves the way of using topological methods as a standard tool in the context of data analytics.

In this project, we have set the goal to examine algorithmic questions in the area of topological data analysis and extend the borders of computational feasibility. For that, we both used methods of theoretical computer science as well as algorithm engineering in order to tackle questions from different points of view. We introduce some of our main results: (1) A main problem of topological data analysis is the computation of persistent barcodes. In there, we face a discrepancy between the theoretical complexity of the problem (the algorithm requires cubic time in the size of the input in the worst case) and the practically observed complexity (linear and therefore, fortunately, very fast). We could show that the complexity of barcode computation for realistic models is better than cubic in expectation. That means, we were able to formalize and prove the folklore statement that worst-case instances are ``rare'', using methods from probabilistic topology. (2) Multi-parameter persistence is a sub-area of topological data analysis with increasing importance. An unsolved problem in that context was the efficient computation of the interleaving distance between two instances. The significance of the question stems from the fact that the interleaving distance is, in a mathematically provable sense, the ``best'' distance measure. We could show that the computation of that distance is NP-hard, as well as the approximation of the distance up to a factor of 3. This implies that the existence of an efficient algorithm is very unlikely. A positive effect of this result is that researchers can now focus on other distance measures. Our project also has proposed several efficient algorithms for the computation of the alternative matching distance of multi-parameter persistence. (3) An important ingredient for the fast computation with data is compression: how can we describe the essence of a data set as efficient as possible? For multi-parameterized data sets, we have developed an algorithm for that: it compresses data in the size of gigabytes within a few seconds without changing the topological properties. This significantly facilitates the analysis of a dataset. Our software is publicly available. The discovery of many significant results confirms our comprehensive approach to the problem. We expect that both our theoretical and practical results will further advance the research field in the next future and will render further applications of persistent homology possible. Because topological data analysis is used in many different fields (in practically all natural sciences and beyond), our results have indirect impact far beyond the field of computational topology.