The Vietoris-Rips filtration for an @math -point metric space is a sequence of large simplicial complexes adding a topological structure to the otherwise disconnected space. The persistent homology is a key tool in topological data analysis and studies topological features of data that persist over many scales. The fastest algorithm for computing persistent homology of a filtration has time @math , where @math is the number of updates (additions or deletions of simplices), @math is the time for multiplication of @math matrices. For a space of @math points given by their pairwise distances, we approximate the Vietoris-Rips filtration by a zigzag filtration consisting of @math updates, which is sublinear in @math . The constant depends on a given error of approximation and on the doubling dimension of the metric space. Then the persistent homology of this sublinear-size filtration can be computed in time @math , which is subquadratic in @math .
We solve Problem in Theorem by building a sublinear-size approximation to the Vietoris-Rips filtration on @math given points in a metric space and then running the best algorithm for computing the zigzag persistent homology. Due to stability of persistent homology @cite_0 , the error of approximation at the homology level can be controlled at the level of filtration.
@cite_0
2056761334
Topological persistence has proven to be a key concept for the study of real-valued functions defined over topological spaces. Its validity relies on the fundamental property that the persistence diagrams of nearby functions are close. However, existing stability results are restricted to the case of continuous functions defined over triangulable spaces. In this paper, we present new stability results that do not suffer from the above restrictions. Furthermore, by working at an algebraic level directly, we make it possible to compare the persistence diagrams of functions defined over different spaces, thus enabling a variety of new applications of the concept of persistence. Along the way, we extend the definition of persistence diagram to a larger setting, introduce the notions of discretization of a persistence module and associated pixelization map, define a proximity measure between persistence modules, and show how to interpolate between persistence modules, thereby lending a more analytic character to this otherwise algebraic setting. We believe these new theoretical concepts and tools shed new light on the theory of persistence, in addition to simplifying proofs and enabling new applications.