Outlier-robust subsampling techniques for persistent homology

Bernadette J. Stolz

Published 2021-03-26Version 1

In recent years, persistent homology (PH) has been successfully applied to real-world data in many different settings. When attempting to study large and noisy data sets, however, many of the currently available algorithms for PH fail due to computational complexity preventing interesting applications. One approach to address computational issues posed by PH is to select a set of landmarks by subsampling from the data. Currently, these landmark points are chosen either at random or using the so called maxmin algorithm. Neither is ideal as random selection tends to favour dense areas of the data while the maxmin algorithm is very sensitive to noise. We propose a novel approach to select landmarks specifically for PH that preserves topological properties of the original data set. Our method is motivated by the Mayer-Vietoris sequence and requires only local PH computation thus enabling efficient computation. We test our landmarks on artificial data sets which contain different levels of noise and compare them to standard landmark selection techniques. We demonstrate that our landmark selection outperforms standard methods as well as a subsampling technique based on an outlier-robust version of the $k$- means algorithm for low sampling densities in noisy data.