Pepijn Roos Hoefgeest: Robust topological features and homological min cuts

Abstract

Persistent homology is a popular method to compute topological features of metric data. Standard approaches based on the \v{C}ech or Vietoris-Rips filtration are stable under small perturbations of the data, but highly sensitive to outliers. Several alternative filtrations have been suggested to address this issue. However, these are only provably robust under relatively tame noise models. In this paper, we take a different perspective and consider the following question: Given metric data \(Y = X \cup W\) consisting of uncorrupted data \(X\) and a fixed fraction \(\alpha \in (0, 1)\) of arbitrary outliers \(W\), which persistent features of \(Y\) can be guaranteed to reflect persistent features of \(X\)?

We formalize this question by introducing the notion of \(\alpha\)-robustness, and study the question of deciding whether a given bar in a barcode of \(Y\) is \(\alpha\)-robust. We give a global heuristic based on the Hausdorff distance which guarantees any bar exceeding a certain length is \(\alpha\)-robust. We show that deciding \(\alpha\)-robustness of a bar can be reduced to a homological variant of the minimum cut problem in a simplicial complex.

This allows us to give a simple algorithm which decides \(\alpha\)-robustness for any given bar in \(H_0\). Finally, we study this homological min-cut problem in \(H_1\), where it is closely related to the (classical) min-cut problem in graphs. This leads us to a corresponding homological analogue of the max-flow problem. However, it turns out that a min-cut max-flow theorem does not hold in our setting, meaning we cannot solve homological min-cut directly via linear programming.