MKMichael Kerber

Michael Kerber

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Michael Kerber has a total of 29 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Expected Complexity of Barcode Reduction

    by Barbara Giunti, Guillaume Houry, Michael Kerber, Matthias Söls

    We study the algorithmic complexity of computing the persistence barcode of a randomly generated filtration. We provide a general technique to bound the expected complexity of reducing the boundary matrix in terms of the density of its reduced form. We apply this technique finding upper bounds for the average fill-in (number of non-zero entries) of the boundary matrix on Čech, Vietoris–Rips and Erdős–Rényi filtrations after matrix reduction, thus obtaining bounds on the expected complexity of the barcode computation. Our method is based on previous results on the expected Betti numbers of the corresponding complexes. Our fill-in bounds for Čech and Vietoris–Rips complexes are asymptotically tight up to a logarithmic factor. In particular, both our fill-in and computation bounds are better than the worst-case estimates. We also provide an Erdős–Rényi filtration realizing the worst-case fill-in and computation.

  • Open Access

    Decomposition of Zero-Dimensional Persistence Modules via Rooted Subsets

    by Ángel Javier Alonso, Michael Kerber

    We study the decomposition of zero-dimensional persistence modules, viewed as functors valued in the category of vector spaces factorizing through sets. Instead of working directly at the level of vector spaces, we take a step back and first study the decomposition problem at the level of sets. This approach allows us to define the combinatorial notion of rooted subsets . In the case of a filtered metric space M , rooted subsets relate the clustering behavior of the points of M with the decomposition of the associated persistence module. In particular, we can identify intervals in such a decomposition quickly. In addition, rooted subsets can be understood as a generalization of the elder rule, and are also related to the notion of constant conqueror of Cai, Kim, Mémoli and Wang. As an application, we give a lower bound on the number of intervals that we can expect in the decomposition of zero-dimensional persistence modules of a density-Rips filtration in Euclidean space: in the limit, and under very general circumstances, we can expect that at least 25% of the indecomposable summands are interval modules.


  • Open Access

    Sparse Higher Order Čech Filtrations

    by Mickaël Buchet, Bianca B Dornelas, Michael Kerber

    For a finite set of balls of radius r , the k -fold cover is the space covered by at least k balls. Fixing the ball centers and varying the radius, we obtain a nested sequence of spaces that is called the k -fold filtration of the centers. For k =1, the construction is the union-of-balls filtration that is popular in topological data analysis. For larger k , it yields a cleaner shape reconstruction in the presence of outliers. We contribute a sparsification algorithm to approximate the topology of the k -fold filtration. Our method is a combination and adaptation of several techniques from the well-studied case k =1, resulting in a sparsification of linear size that can be computed in expected near-linear time with respect to the number of input points. Our method also extends to the multicover bifiltration, composed of the k -fold filtrations for several values of k , with the same size and complexity bounds.


  • Open Access

    Graphcode: Learning from multiparameter persistent homology using graph neural networks

    by Michael Kerber, Florian Russold

    We introduce graphcodes, a novel multi-scale summary of the topological properties of a dataset that is based on the well-established theory of persistent homology. Graphcodes handle datasets that are filtered along two real-valued scale parameters. Such multi-parameter topological summaries are usually based on complicated theoretical foundations and difficult to compute; in contrast, graphcodes yield an informative and interpretable summary and can be computed as efficient as one-parameter summaries. Moreover, a graphcode is simply an embedded graph and can therefore be readily integrated in machine learning pipelines using graph neural networks. We describe such a pipeline and demonstrate that graphcodes achieve better classification accuracy than state-of-the-art approaches on various datasets.


  • Open Access

    Probabilistic Analysis of Multiparameter Persistence Decompositions

    by Ángel Javier Alonso, Michael Kerber, Primoz Skraba

    Multiparameter persistence modules can be uniquely decomposed into indecomposable summands. Among these indecomposables, intervals stand out for their simplicity, making them preferable for their ease of interpretation in practical applications and their computational efficiency. Empirical observations indicate that modules that decompose into only intervals are rare. To support this observation, we show that for numerous common multiparameter constructions, such as density- or degree-Rips bifiltrations, and across a general category of point samples, the probability of the homology-induced persistence module decomposing into intervals goes to zero as the sample size goes to infinity.

  • Open Access

    Expected Complexity of Persistent Homology Computation via Matrix Reduction

    by Barbara Giunti, Guillaume Houry, Michael Kerber, Matthias Söls

    We study the algorithmic complexity of computing persistent homology of a randomly generated filtration. Specifically, we prove upper bounds for the average fill-in (number of non-zero entries) of the boundary matrix on \v{C}ech, Vietoris--Rips and Erd\H{o}s--R\'enyi filtrations after matrix reduction. Our bounds show that the reduced matrix is expected to be significantly sparser than what the general worst-case predicts. Our method is based on previous results on the expected Betti numbers of the corresponding complexes. We establish a link between these results and the fill-in of the boundary matrix. In the $1$-dimensional case, our bound for \v{C}ech and Vietoris--Rips complexes is asymptotically tight up to a logarithmic factor. We also provide an Erd\H{o}s--R\'enyi filtration realising the worst-case.

  • Open Access

    Asymptotic Improvements on the Exact Matching Distance for 2-parameter Persistence

    by Håvard Bakke Bjerkevik, Michael Kerber

    In the field of topological data analysis, persistence modules are used to express geometrical features of data sets. The matching distance $d_\mathcal{M}$ measures the difference between $2$-parameter persistence modules by taking the maximum bottleneck distance between $1$-parameter slices of the modules. The previous best algorithm to compute $d_\mathcal{M}$ exactly runs in $O(n^{8+\omega})$ time using $O(n^4)$ space, where $n$ is the number of generators and relations of the modules and $\omega$ is the matrix multiplication constant. We improve significantly on this by describing an algorithm with expected running time $O(n^5 \log^3 n)$ and using $O(n^2)$ space. We first solve the decision problem $d_\mathcal{M}\leq \lambda$ for a constant $\lambda$ in $O(n^5\log n)$ time by traversing a line arrangement in the dual plane, where each point represents a slice. Then we lift the line arrangement to a plane arrangement in $\mathbb{R}^3$ whose vertices represent possible values for $d_\mathcal{M}$, and use a randomized incremental method to search through the vertices and find $d_\mathcal{M}$. The expected running time of this algorithm is $O((n^4+T(n))\log^2 n)$, where $T(n)$ is an upper bound for the complexity of deciding if $d_\mathcal{M}\leq \lambda$. Moreover, we show how to compute the matching distance using only linear space, to the price of a much worse time complexity.

  • Open Access

    Guest Editors’ Foreword

    by Xavier Goaoc, Michael Kerber

  • Open Access

    Delaunay Bifiltrations of Functions on Point Clouds

    by Ángel Javier Alonso, Michael Kerber, Tung Lam, Michael Lesnick

    The Delaunay filtration $\mathcal{D}_{\bullet}(X)$ of a point cloud $X\subset \mathbb{R}^d$ is a central tool of computational topology. Its use is justified by the topological equivalence of $\mathcal{D}_{\bullet}(X)$ and the offset (i.e., union-of-balls) filtration of $X$. Given a function $γ: X \to \mathbb{R}$, we introduce a Delaunay bifiltration $\mathcal{DC}_{\bullet}(γ)$ that satisfies an analogous topological equivalence, ensuring that $\mathcal{DC}_{\bullet}(γ)$ topologically encodes the offset filtrations of all sublevel sets of $γ$, as well as the topological relations between them. $\mathcal{DC}_{\bullet}(γ)$ is of size $O(|X|^{\lceil\frac{d+1}{2}\rceil})$, which for $d$ odd matches the worst-case size of $\mathcal{D}_{\bullet}(X)$. Adapting the Bowyer-Watson algorithm for computing Delaunay triangulations, we give a simple, practical algorithm to compute $\mathcal{DC}_{\bullet}(γ)$ in time $O(|X|^{\lceil \frac{d}{2}\rceil +1})$. Our implementation, based on CGAL, computes $\mathcal{DC}_{\bullet}(γ)$ with modest overhead compared to computing $\mathcal{D}_{\bullet}(X)$, and handles tens of thousands of points in $\mathbb{R}^3$ within seconds.

  • Open Access

    Topological Data Analysis in smart manufacturing processes -- A survey on the state of the art

    by Martin Uray, Barbara Giunti, Michael Kerber, Stefan Huber

    Topological Data Analysis (TDA) is a mathematical method using techniques from topology for the analysis of complex, multi-dimensional data that has been widely and successfully applied in several fields such as medicine, material science, biology, and others. This survey summarizes the state of the art of TDA in yet another application area: industrial manufacturing and production in the context of Industry 4.0. We perform a rigorous and reproducible literature search of applications of TDA on the setting of industrial production and manufacturing. The resulting works are clustered and analyzed based on their application area within the manufacturing process and their input data type. We highlight the key benefits of TDA and their tools in this area and describe its challenges, as well as future potential. Finally, we discuss which TDA methods are underutilized in (the specific area of) industry and the identified types of application, with the goal of prompting more research in this profitable area of application.