BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ulrich Bauer

Ulrich Bauer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational Geometrymath.ATmath.GTComputer VisionMachine LearningComputational ComplexityDistributed, Parallel, and Cluster Computingeess.IVmath.ACmath.COmath.DGmath.FAmath.MGmath.STStatistics Theory

Catalog footprint

What is connected

16works
15topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2022arXiv

clDice -- A Novel Topology-Preserving Loss Function for Tubular Structure Segmentation

Accurate segmentation of tubular, network-like structures, such as vessels, neurons, or roads, is relevant to many fields of research. For such structures, the topology is their most important characteristic; particularly preserving connectedness: in the case of vascular networks, missing a connected vessel entirely alters the blood-flow dynamics. We introduce a novel similarity measure termed centerlineDice (short clDice), which is calculated on the intersection of the segmentation masks and their (morphological) skeleta. We theoretically prove that clDice guarantees topology preservation up to homotopy equivalence for binary 2D and 3D segmentation. Extending this, we propose a computationally efficient, differentiable loss function (soft-clDice) for training arbitrary neural segmentation networks. We benchmark the soft-clDice loss on five public datasets, including vessels, roads and neurons (2D and 3D). Training on soft-clDice leads to segmentation with more accurate connectivity information, higher graph similarity, and better volumetric scores.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient Computation of Image Persistence

We present an algorithm for computing the barcode of the image of a morphisms in persistent homology induced by an inclusion of filtered finite-dimensional chain complexes. These algorithms make use of the clearing optimization and can be applied to inclusion-induced maps in persistent absolute homology and persistent relative cohomology for filtrations of pairs of simplicial complexes. They form the basis for our implementation for Vietoris-Rips complexes in the framework of the software Ripser.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Gromov Hyperbolicity, Geodesic Defect, and Apparent Pairs in Vietoris-Rips Filtrations

Motivated by computational aspects of persistent homology for Vietoris-Rips filtrations, we generalize a result of Eliyahu Rips on the contractibility of Vietoris-Rips complexes of geodesic spaces for a suitable parameter depending on the hyperbolicity of the space. We consider the notion of geodesic defect to extend this result to general metric spaces in a way that is also compatible with the filtration. We further show that for finite tree metrics the Vietoris-Rips complexes collapse to their corresponding subforests. We relate our result to modern computational methods by showing that these collapses are induced by the apparent pairs gradient, which is used as an algorithmic optimization in Ripser, explaining its particularly strong performance on tree-like metric data.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Parameterized inapproximability of Morse matching

We study the problem of minimizing the number of critical simplices from the point of view of inapproximability and parameterized complexity. We first show inapproximability of Min-Morse Matching within a factor of $2^{\log^{(1-ε)}n}$. Our second result shows that Min-Morse Matching is ${\bf W{[P]}}$-hard with respect to the standard parameter. Next, we show that Min-Morse Matching with standard parameterization has no FPT approximation algorithm for any approximation factor $ρ$. The above hardness results are applicable to complexes of dimension $\ge 2$. On the positive side, we provide a factor $O(\frac{n}{\log n})$ approximation algorithm for Min-Morse Matching on $2$-complexes, noting that no such algorithm is known for higher dimensional complexes. Finally, we devise discrete gradients with very few critical simplices for typical instances drawn from a fairly wide range of parameter values of the Costa-Farber model of random complexes.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Persistent homology for functionals

We introduce topological conditions on a broad class of functionals that ensure that the persistent homology modules of their associated sublevel set filtration admit persistence diagrams, which, in particular, implies that they satisfy generalized Morse inequalities. We illustrate the applicability of these results by recasting the original proof of the Unstable Minimal Surface Theorem given by Morse and Tompkins in a modern and rigorous framework.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Structure and Interleavings of Relative Interlevel Set Cohomology

The relative interlevel set cohomology (RISC) is an invariant of real-valued continuous functions closely related to the Mayer--Vietoris pyramid introduced by Carlsson, de Silva, and Morozov. As such, the relative interlevel set cohomology is a parametrization of the cohomology vector spaces of all open interlevel sets relative complements of closed interlevel sets. We provide a structure theorem, which applies to the RISC of real-valued continuous functions whose open interlevel sets have finite-dimensional cohomology in each degree. Moreover, we show this tameness assumption is in some sense equivalent to $q$-tameness as introduced by Chazal, de Silva, Glisse, and Oudot. Furthermore, we provide the notion of an interleaving for RISC and we show that it is stable in the sense that any space with two functions that are $δ$-close induces a $δ$-interleaving of the corresponding relative interlevel set cohomologies. Finally, we provide an elementary form of quantitative homotopy invariance for RISC.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

The Reeb Graph Edit Distance is Universal

We consider the setting of Reeb graphs of piecewise linear functions and study distances between them that are stable, meaning that functions which are similar in the supremum norm ought to have similar Reeb graphs. We define an edit distance for Reeb graphs and prove that it is stable and universal, meaning that it provides an upper bound to any other stable distance. In contrast, via a specific construction, we show that the interleaving distance and the functional distortion distance on Reeb graphs are not universal.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Induced Matchings and the Algebraic Stability of Persistence Barcodes

We define a simple, explicit map sending a morphism $f:M \rightarrow N$ of pointwise finite dimensional persistence modules to a matching between the barcodes of $M$ and $N$. Our main result is that, in a precise sense, the quality of this matching is tightly controlled by the lengths of the longest intervals in the barcodes of $\ker f$ and $\mathop{\mathrm{coker}} f$. As an immediate corollary, we obtain a new proof of the algebraic stability of persistence, a fundamental result in the theory of persistent homology. In contrast to previous proofs, ours shows explicitly how a $δ$-interleaving morphism between two persistence modules induces a $δ$-matching between the barcodes of the two modules. Our main result also specializes to a structure theorem for submodules and quotients of persistence modules, and yields a novel "single-morphism" characterization of the interleaving relation on persistence modules.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Measuring Distance between Reeb Graphs

One of the prevailing ideas in geometric and topological data analysis is to provide descriptors that encode useful information about hidden objects from observed data. The Reeb graph is one such descriptor for a given scalar function. The Reeb graph provides a simple yet meaningful abstraction of the input domain, and can also be computed efficiently. Given the popularity of the Reeb graph in applications, it is important to understand its stability and robustness with respect to changes in the input function, as well as to be able to compare the Reeb graphs resulting from different functions. In this paper, we propose a metric for Reeb graphs, called the functional distortion distance. Under this distance measure, the Reeb graph is stable against small changes of input functions. At the same time, it remains discriminative at differentiating input functions. In particular, the main result is that the functional distortion distance between two Reeb graphs is bounded from below by (and thus more discriminative than) the bottleneck distance between both the ordinary and extended persistence diagrams for appropriate dimensions. As an application of our results, we analyze a natural simplification scheme for Reeb graphs, and show that persistent features in Reeb graph remains persistent under simplification. Understanding the stability of important features of the Reeb graph under simplification is an interesting problem on its own right, and critical to the practical usage of Reeb graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Persistence Barcodes versus Kolmogorov Signatures: Detecting Modes of One-Dimensional Signals

We investigate the problem of estimating the number of modes (i.e., local maxima) - a well known question in statistical inference - and we show how to do so without presmoothing the data. To this end, we modify the ideas of persistence barcodes by first relating persistence values in dimension one to distances (with respect to the supremum norm) to the sets of functions with a given number of modes, and subsequently working with norms different from the supremum norm. As a particular case we investigate the Kolmogorov norm. We argue that this modification has certain statistical advantages. We offer confidence bands for the attendant Kolmogorov signatures, thereby allowing for the selection of relevant signatures with a statistically controllable error. As a result of independent interest, we show that taut strings minimize the number of critical points for a very general class of functions. We illustrate our results by several numerical examples.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Stable Multi-Scale Kernel for Topological Machine Learning

Topological data analysis offers a rich source of valuable information to study vision problems. Yet, so far we lack a theoretically sound connection to popular kernel-based learning techniques, such as kernel SVMs or kernel PCA. In this work, we establish such a connection by designing a multi-scale kernel for persistence diagrams, a stable summary representation of topological features in data. We show that this kernel is positive definite and prove its stability with respect to the 1-Wasserstein distance. Experiments on two benchmark datasets for 3D shape classification/retrieval and texture recognition show considerable performance gains of the proposed method compared to an alternative approach that is based on the recently introduced persistence landscapes.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs

The Reeb graph is a construction that studies a topological space through the lens of a real valued function. It has widely been used in applications, however its use on real data means that it is desirable and increasingly necessary to have methods for comparison of Reeb graphs. Recently, several methods to define metrics on the space of Reeb graphs have been presented. In this paper, we focus on two: the functional distortion distance and the interleaving distance. The former is based on the Gromov--Hausdorff distance, while the latter utilizes the equivalence between Reeb graphs and a particular class of cosheaves. However, both are defined by constructing a near-isomorphism between the two graphs of study. In this paper, we show that the two metrics are strongly equivalent on the space of Reeb graphs. In particular, this gives an immediate proof of bottleneck stability for persistence diagrams in terms of the Reeb graph interleaving distance.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Clear and Compress: Computing Persistent Homology in Chunks

We present a parallelizable algorithm for computing the persistent homology of a filtered chain complex. Our approach differs from the commonly used reduction algorithm by first computing persistence pairs within local chunks, then simplifying the unpaired columns, and finally applying standard reduction on the simplified matrix. The approach generalizes a technique by Günther et al., which uses discrete Morse Theory to compute persistence; we derive the same worst-case complexity bound in a more general context. The algorithm employs several practical optimization techniques which are of independent interest. Our sequential implementation of the algorithm is competitive with state-of-the-art methods, and we improve the performance through parallelized computation.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Distributed computation of persistent homology

Persistent homology is a popular and powerful tool for capturing topological features of data. Advances in algorithms for computing persistent homology have reduced the computation time drastically -- as long as the algorithm does not exhaust the available memory. Following up on a recently presented parallel method for persistence computation on shared memory systems, we demonstrate that a simple adaption of the standard reduction algorithm leads to a variant for distributed systems. Our algorithmic design ensures that the data is distributed over the nodes without redundancy; this permits the computation of much larger instances than on a single machine. Moreover, we observe that the parallelism at least compensates for the overhead caused by communication between nodes, and often even speeds up the computation compared to sequential and even parallel shared memory algorithms. In our experiments, we were able to compute the persistent homology of filtrations with more than a billion (10^9) elements within seconds on a cluster with 32 nodes using less than 10GB of memory per node.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Optimal topological simplification of discrete functions on surfaces

We solve the problem of minimizing the number of critical points among all functions on a surface within a prescribed distance δ from a given input function. The result is achieved by establishing a connection between discrete Morse theory and persistent homology. Our method completely removes homological noise with persistence less than 2δ, constructively proving the tightness of a lower bound on the number of critical points given by the stability theorem of persistent homology in dimension two for any input function. We also show that an optimal solution can be computed in linear time after persistence pairs have been computed.

0 citations0 reviewsNo code linkedOpen access