Ulrich Bauer

I am an assistant professor in the Geometry & Visualization group at TUM. I did my PhD with Max Wardetzky in the research group Discrete Differential Geometry at the University of Göttingen, and a postdoc in Herbert Edelsbrunner's research group at IST Austria.



Research interests:

Discrete/Computational Geometry/Topology, Algorithms, Combinatorics.



Contact:

Prof. Dr. Ulrich Bauer
Geometrie & Visualisierung (M10)
Fakultät für Mathematik
Technische Universität München
Boltzmannstraße 3
D-85747 Garching bei München
Vox: +49 89 289 18361
Net: mail (at) ulrich-bauer.org


Preprints
kolmogorov
The Reeb Graph Edit Distance is Universal
Ulrich Bauer, Claudia Landi, and Facundo Mémoli.
Abstract: 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.
[arXiv]

kolmogorov
Hardness of Approximation for Morse Matching
Ulrich Bauer and Abhishek Rathod.
Abstract: We consider the approximability of maximization and minimization variants of the Morse matching problem, posed as open problems by Joswig and Pfetsch. We establish hardness results for Max-Morse matching and Min-Morse matching. In particular, we show that, for a simplicial complex with n simplices and dimension $ d\leq 3$, it is NP-hard to approximate Min-Morse matching within a factor of $ O (n^{1-\epsilon}) $, for any $\epsilon> 0$. Moreover, using an L-reduction from Degree 3 Max-Acyclic Subgraph to Max-Morse matching, we show that it is both NP-hard and UGC-hard to approximate Max-Morse matching for simplicial complexes of dimension $ d\leq 2$ within certain explicit constant factors.
[arXiv]

kolmogorov
Persistent Betti numbers of random Čech complexes
Ulrich Bauer and Florian Pausinger.
Abstract: We study the persistent homology of random Čech complexes. Generalizing a method of Penrose for studying random geometric graphs, we first describe an appropriate theoretical framework in which we can state and address our main questions. Then we define the kth persistent Betti number of a random Čechcomplex and determine its asymptotic order in the subcritical regime. This extends a result of Kahle on the asymptotic order of the ordinary kth Betti number of such complexes to the persistent setting.
[arXiv]

kolmogorov
Persistence in sampled dynamical systems faster
Ulrich Bauer, Herbert Edelsbrunner, Grzegorz Jablonski, and Marian Mrozek.
Abstract: We call a continuous self-map that reveals itself through a discrete set of point-value pairs a sampled dynamical system. Capturing the available information with chain maps on Delaunay complexes, we use persistent homology to quantify the evidence of recurrent behavior, and to recover the eigenspaces of the endomorphism on homology induced by the self-map. The chain maps are constructed using discrete Morse theory for Cech and Delaunay complexes, representing the requisite discrete gradient field implicitly in order to get fast algorithms.
[arXiv]

matching
Persistence Diagrams as Diagrams: A Categorification of the Stability Theorem
Ulrich Bauer and Michael Lesnick.
Abstract: Persistent homology, a central tool of topological data analysis, provides invariants of data called barcodes (also known as persistence diagrams). A barcode is simply a multiset of real intervals. Recent work of Edelsbrunner, Jablonski, and Mrozek suggests an equivalent description of barcodes as functors R-> Mch, where R is the poset category of real numbers and Mch is the category whose objects are sets and whose morphisms are matchings (ie, partial injective functions). Such functors form a category Mch^ R whose morphisms are the natural transformations. Thus, this interpretation of barcodes gives us a hitherto unstudied categorical structure on barcodes. The aim of this note is to show that this categorical structure leads to surprisingly simple reformulations of both the well-known stability theorem for persistent homology and a recent generalization called the induced matching theorem.
[arXiv]



Software
delaunay
Ripser: a lean C++ code for the computation of Vietoris–Rips persistence barcodes
Ulrich Bauer (2015–2018). Licensed under LGPL.
Description: Ripser is a lean C++ code for the computation of Vietoris–Rips persistence barcodes. It can do just this one thing, but does it extremely well.

The implementation is based on an implicit algorithmic representation of the coboundary operator and of the filtration order, avoiding the explicit construction of the filtration boundary matrix. Our software shows significant improvements over existing software both in time and memory usage.

The source code consists of less than 1000 lines of C++ code. It supports for coefficients in prime finite fields and sparse distance matrices for computing the Vietoris–Rips persistence barcodes only up to a specified threshold. No external dependencies are required.

To see a live demo of Ripser's capabilities, go to live.ripser.org. The computation happens inside the browser (using PNaCl on Chrome and JavaScript via Emscripten on other browsers).
[live] [github]

delaunay
PHAT (Persistent Homology Algorithm Toolbox)
Ulrich Bauer, Michael Kerber, Jan Reininghaus. Copyright IST Austria (2013–2017). Licensed under LGPL.
Description: PHAT is an open-source C++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. PHAT provides numerous different reduction strategies as well as data types to store and manipulate the boundary matrix.
[bitbucket]



Publications
delaunay
The Morse theory of Čech and Delaunay complexes
Ulrich Bauer and Herbert Edelsbrunner. Transactions of the American Mathematical Society 369:5 (2017), 3741–3762.
Conference version: The Morse theory of Čech and Delaunay filtrations, SoCG '14 Proceedings of the twenty-ninth annual symposium on Computational geometry (2014), 484–490. [pdf] [doi]
Abstract: Given a finite set of points in ℝⁿ and a positive radius, we consider the Čech, Delaunay–Čech, alpha, and wrap complexes as examples of a generalized discrete Morse theory. We prove that the latter three are simple-homotopy equivalent, and the same is true for their weighted versions. Our results have applications in topological data analysis and in the reconstruction of shapes from sampled data.
[doi] [arXiv]

kolmogorov
Persistence Barcodes Versus Kolmogorov Signatures: Detecting Modes of One-Dimensional Signals
Ulrich Bauer, Axel Munk, Hannes Sieling, and Max Wardetzky. Foundations of Computational Mathematics 17:1 (2017), 1–33.
Abstract: 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.
[doi] [arXiv]

delaunay
PHAT–Persistent homology algorithms toolbox
Ulrich Bauer, Michael Kerber, Jan Reininghaus, Hubert Wagner. Journal of Symbolic Computation 78 (2017), 76–90.
Conference version: ICMS 2014: Mathematical Software – ICMS 2014, 137–143. [doi]
Abstract: Phat is an open-source C++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. We provide numerous different reduction strategies as well as data types to store and manipulate the boundary matrix. We compare the different combinations through extensive experimental evaluation and identify optimization techniques that work well in practical situations. We also compare our software with various other publicly available libraries for persistent homology.
[doi] [arXiv]

induced-matchings
An Edit Distance For Reeb Graphs
Ulrich Bauer, Barbara Di Fabio, and Claudia Landi. 3DOR '16 Proceedings of the Eurographics 2016 Workshop on 3D Object Retrieval (2016), 27–34
Abstract: We consider the problem of assessing the similarity of 3D shapes using Reeb graphs from the standpoint of robustness under perturbations. For this purpose, 3D objects are viewed as spaces endowed with real-valued functions, while the similarity between the resulting Reeb graphs is addressed through a graph edit distance. The cases of smooth functions on manifolds and piecewise linear functions on polyhedra stand out as the most interesting ones. The main contribution of this paper is the introduction of a general edit distance suitable for comparing Reeb graphs in these settings. This edit distance promises to be useful for applications in 3D object retrieval because of its stability properties in the presence of noise.
[doi]

induced-matchings
Induced Matchings of Barcodes and the Algebraic Stability of Persistence
Ulrich Bauer and Michael Lesnick. Journal of Computational Geometry 6:2 (2015), 162–191 (Invited to special issue for best papers of SoCG '14).
Conference version: SoCG '14 Proceedings of the twenty-ninth annual symposium on Computational geometry (2014), 355–364.
Abstract: We define a simple, explicit map sending a morphism f: M → 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 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.
[pdf] [doi] [arXiv]

Statistical topological data analysis-a kernel perspective
Roland Kwitt, Stefan Huber, Marc Niethammer, Weili Lin, and Ulrich Bauer. NIPS'15 Advances in neural information processing systems (2015), 3070–3078.
Abstract: 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 kernelbased 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.
[pdf]

reeb-graph
Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs
Ulrich Bauer, Elizabeth Munch, and Yusu Wang. SoCG '15 Proceedings of the 31st International Symposium on Computational Geometry (2015), 461–475.
Abstract: 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.
[pdf] [doi] [arXiv]

A stable multi-scale kernel for topological machine learning
Jan Reininghaus, Stefan Huber, Ulrich Bauer, and Roland Kwitt. CVPR'15 Proceedings of the IEEE conference on computer vision and pattern recognition (2015), 4741-4748.
Abstract: 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 kernelbased 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.
[pdf]

reeb-graph
Measuring Distance between Reeb Graphs
Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. SoCG '14 Proceedings of the twenty-ninth annual symposium on Computational geometry (2014), 464–473.
Abstract: 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.
[pdf] [doi] [arXiv]

chunks
Clear and Compress: Computing Persistent Homology in Chunks
Ulrich Bauer, Michael Kerber, and Jan Reininghaus, Topological Methods in Data Analysis and Visualization III Mathematics and Visualization 2014, 103–117.
Abstract: 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.
[doi] [arXiv]

distributed-persistence
Distributed computation of persistent homology
Ulrich Bauer, Michael Kerber, and Jan Reininghaus. Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX14), 31–38.
Abstract: 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⁹) elements within seconds on a cluster with 32 nodes using less than 10GB of memory per node.
[pdf] [doi]

tentacles
Homological reconstruction and simplification in R³
Dominique Attali, Ulrich Bauer, Olivier Devillers, Marc Glisse, and André Lieutier. Computational Geometry 48:8 (2015), 606–621 (Invited to special issue for best papers of SoCG '13).
Conference version: SoCG '13 Proceedings of the twenty-ninth annual symposium on Computational geometry (2013), 117–126. [pdf] [doi]

Abstract: We consider the problem of deciding whether the persistent homology group of a simplicial pair (K,L) can be realized as the homology H*(X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in R³. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S³ within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.
[pdf] [doi]

contours
Optimal topological simplification of discrete functions on surfaces
Ulrich Bauer, Carsten Lange, and Max Wardetzky. Discrete and Computational Geometry 47:2 (2012), 347–377.
Abstract: Given a function f on a surface and a tolerance δ > 0, we construct a function fδ subject to ‖fδ - f‖ ≤ δ such that fδ has a minimum number of critical points. Our construction relies on a connection between discrete Morse theory and persistent homology and completely removes homological noise with persistence ≤ 2δ from the input function f. The number of critical points of the resulting simplified function fδ achieves the lower bound dictated by the stability theorem of persistent homology. We show that the simplified function can be computed in linear time after persistence pairs have been computed.
[pdf] [doi]

contours
Persistence in discrete Morse Theory
PhD thesis, University of Göttingen, 2011.
Abstract: The goal of this thesis is to bring together two different theories about critical points of a scalar function and their relation to topology: Discrete Morse theory and Persistent homology. While the goals and fundamental techniques are different, there are certain themes appearing in both theories that closely resemble each other. In certain cases, the two threads can be joined, leading to new insights beyond the classical realm of one particular theory.

Discrete Morse theory provides combinatorial equivalents of several core concepts of classical Morse theory, such as discrete Morse functions, discrete gradient vector fields, critical points, and a cancelation theorem for the elimination of critical points of a vector field. Because of its simplicity, it not only maintains the intuition of the classical theory but allows to surpass it in a certain sense by providing explicit and canonical constructions that would become quite complicated in the smooth setting.

Persistent homology quantifies topological features of a function. It defines the birth and death of homology classes at critical points, identifies pairs of these (persistence pairs), and provides a quantitative notion of their stability (persistence).

Whereas (discrete) Morse theory makes statements about the homotopy type of the sublevel sets of a function, persistence is concerned with their homology. While homology is an invariant of homotopy equivalences, the converse is not true: not every map inducing an isomorphism in homology is a homotopy equivalence. In this thesis we establish a connection between both theories and use this combination to solve problems that are not easily accessibly by any single theory alone. In particular, we solve the problem of minimizing the number of critical points of a function on a surface within a certain tolerance from a given input function.
[pdf] [hdl]

Persistence
Total Variation Meets Topological Persistence: A First Encounter
Ulrich Bauer, Carola-Bibiane Schönlieb, and Max Wardetzky. Proceedings of ICNAAM 2010, 1022–1026.
Abstract: We present first insights into the relation between two popular yet apparently dissimilar approaches to denoising of one dimensional signals, based on (i) total variation (TV) minimization and (ii) ideas from topological persistence. While a close relation between (i) and (ii) might phenomenologically not be unexpected, our work appears to be the first to make this connection precise for one dimensional signals. We provide a link between (i) and (ii) that builds on the equivalence between TV-L2 regularization and taut strings and leads to a novel and efficient denoising algorithm that is contrast preserving and operates in O(nlogn) time, where n is the size of the input.
[pdf] [doi]

curvature lines
Uniform Convergence of Discrete Curvatures from Nets of Curvature Lines
Ulrich Bauer, Konrad Polthier, Max Wardetzky, Discrete and Computational Geometry 43:4 (2010), 798–823.
Abstract: We study “Steiner-type” discrete curvatures computed from nets of curvature lines on a given smooth surface, and prove their uniform pointwise convergence to smooth principal curvatures. We provide explicit error bounds, with constants depending only on the limit surface and the shape regularity of the discrete net.
[pdf] [doi]

tubes
Generating Parametric Models of Tubes from Laser Scans
Ulrich Bauer, Konrad Polthier, Computer-Aided Design 41 (2009), 719–729.
Conference version: Parametric Reconstruction of Bent Tube Surfaces, Proceedings NASAGEM/Cyberworlds 2007, 465–474. [pdf] [doi]
Abstract: We present a method for parametric reconstruction of a piecewise defined pipe surface, consisting of cylinder and torus segments, from an unorganized point set. Our main contributions are reconstruction of the spine curve of a pipe surface from surface samples, and approximation of the spine curve by continuous circular arcs and line segments. Our algorithm accurately outputs the parametric data required for bending machines to create the reconstructed tube.
[pdf] [doi]

plane detection
Detection of Planar Regions in Volume Data for Topology Optimization
Ulrich Bauer, Konrad Polthier, Proceedings of Geometry Modelling and Processing 2008, Lecture Notes in Computer Science vol. 4975 (2008), 119–126.
Abstract: We propose a method to identify planar regions in volume data using a specialized version of the discrete Radon transform operating on a structured or unstructured grid. The algorithm uses an efficient discretization scheme for the parameter space to obtain a running time of O(N(T log T)), where T is the number of cells and N is the number of plane normals in the discretized parameter space. We apply our algorithm in an industrial setting and perform experiments with real-world data generated by topology optimization algorithms, where the planar regions represent portions of a mechanical part that can be built using steel plate.
[pdf] [doi]



Undergraduate projects

hydra
Hydra: Collaborative Text Editor

Application development – TU München (01/2003 – 06/2003)

Hydra is an easy-to-use collaborative real-time text editor for Mac OS X. It uses operational transformations to synchronise text on the different participating computers and allows users to simultaneously edit a text file without locking.
Hydra has won several awards, among them the Apple Design Award and the O'Reilly Mac OS X Innovators Award. It is now a commercial product maintained by two of my co-authors under the name SubEthaEdit.
Apple Design Award O'Reilly Mac OS X Innovators Award

Music

That's me