Search

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., Comment: Extended journal version

Multidimensional persistence has been proposed to study the persistence of topological features in data indexed by multiple parameters. In this work, we further explore its algebraic complications from the point of view of higher dimensional indecomposable persistence modules containing lower dimensional ones as hyperplane restrictions. Our previous work constructively showed that any finite rectangle-decomposable $n$D persistence module is the hyperplane restriction of some indecomposable $(n+1)$D persistence module, as a corollary of the result for $n=1$. Here, we extend this by dropping the requirement of rectangle-decomposability. Furthermore, in the case that the underlying field is countable, we construct an indecomposable $(n+1)$D persistence module containing all $n$D persistence modules, up to isomorphism, as hyperplane restrictions. Finally, in the case $n=1$, we present a minimal construction that improves our previous construction.

A recent work by Lesnick and Wright proposed a visualisation of $2$D persistence modules by using their restrictions onto lines, giving a family of $1$D persistence modules. We give a constructive proof that any $1$D persistence module with finite support can be found as a restriction of some indecomposable $2$D persistence module with finite support. As consequences of our construction, we are able to exhibit indecomposable $2$D persistence modules whose support has holes as well as an indecomposable $2$D persistence module containing all $1$D persistence modules with finite support as line restrictions. Finally, we also show that any finite-rectangle-decomposable $n$D persistence module can be found as a restriction of some indecomposable $(n+1)$D persistence module., Comment: 38 pages

In the persistent homology of filtrations, the indecomposable decompositions provide the persistence diagrams. However, in almost all cases of multidimensional persistence, the classification of all indecomposable modules is known to be a wild problem. One direction is to consider the subclass of interval-decomposable persistence modules, which are direct sums of interval representations. We introduce the definition of pre-interval representations, a more natural algebraic definition, and study the relationships between pre-interval, interval, and indecomposable thin representations. We show that over the ``equioriented'' commutative $2$D grid, these concepts are equivalent. Moreover, we provide a criterion for determining whether or not an $n$D persistence module is interval/pre-interval/thin-decomposable without having to explicitly compute decompositions. For $2$D persistence modules, we provide an algorithm together with a worst-case complexity analysis that uses the total number of intervals in an equioriented commutative $2$D grid. We also propose several heuristics to speed up the computation., Comment: 37 pages

While persistent homology has taken strides towards becoming a wide-spread tool for data analysis, multidimensional persistence has proven more difficult to apply. One reason is the serious drawback of no longer having a concise and complete descriptor analogous to the persistence diagrams of the former. We propose a simple algebraic construction to illustrate the existence of infinite families of indecomposable persistence modules over regular grids of sufficient size. On top of providing a constructive proof of representation infinite type, we also provide realizations by topological spaces and Vietoris-Rips filtrations, showing that they can actually appear in real data and are not the product of degeneracies., Comment: 18 pages. Expanded version of the conference paper that appeared in SoCG 2018

In many data analysis applications the following scenario is commonplace: we are given a point set that is supposed to sample a hidden ground truth $K$ in a metric space, but it got corrupted with noise so that some of the data points lie far away from $K$ creating outliers also termed as {\em ambient noise}. One of the main goals of denoising algorithms is to eliminate such noise so that the curated data lie within a bounded Hausdorff distance of $K$. Popular denoising approaches such as deconvolution and thresholding often require the user to set several parameters and/or to choose an appropriate noise model while guaranteeing only asymptotic convergence. Our goal is to lighten this burden as much as possible while ensuring theoretical guarantees in all cases. Specifically, first, we propose a simple denoising algorithm that requires only a single parameter but provides a theoretical guarantee on the quality of the output on general input points. We argue that this single parameter cannot be avoided. We next present a simple algorithm that avoids even this parameter by paying for it with a slight strengthening of the sampling condition on the input points which is not unrealistic. We also provide some preliminary empirical evidence that our algorithms are effective in practice.

Given a real-valued function $f$ defined over a manifold $M$ embedded in $\mathbb{R}^d$, we are interested in recovering structural information about $f$ from the sole information of its values on a finite sample $P$. Existing methods provide approximation to the persistence diagram of $f$ when geometric noise and functional noise are bounded. However, they fail in the presence of aberrant values, also called outliers, both in theory and practice. We propose a new algorithm that deals with outliers. We handle aberrant functional values with a method inspired from the k-nearest neighbors regression and the local median filtering, while the geometric outliers are handled using the distance to a measure. Combined with topological results on nested filtrations, our algorithm performs robust topological analysis of scalar fields in a wider range of noise models than handled by current methods. We provide theoretical guarantees and experimental results on the quality of our approximation of the sampled scalar field.

We extend the notion of the distance to a measure from Euclidean space to probability measures on general metric spaces as a way to do topological data analysis in a way that is robust to noise and outliers. We then give an efficient way to approximate the sub-level sets of this function by a union of metric balls and extend previous results on sparse Rips filtrations to this setting. This robust and efficient approach to topological data analysis is illustrated with several examples from an implementation., Comment: This is the full version of the paper with the same title in Proceedings of SODA 2015