Approximating persistent homology for a cloud of n points in a subquadratic time

2013/12/05 by Kurlin, Vitaliy
#68U05 (Primary) 65D18 #68U10 (Secondary) #Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1312.1494

Abstract

The Vietoris-Rips filtration for an n-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 O(M(u)+u²log² u), where u is the number of updates (additions or deletions of simplices), M(u)=O(u^2.376) is the time for multiplication of u× u matrices. For a space of n points given by their pairwise distances, we approximate the Vietoris-Rips filtration by a zigzag filtration consisting of u=o(n) updates, which is sublinear in n. 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 o(n²), which is subquadratic in n.

Related

• The distilled Vietoris Rips filtration for persistent homology and a new memory efficient algorithm
• Linear-Size Approximations to the Vietoris-Rips Filtration
• Faster computation of degree-1 persistent homology using the reduced Vietoris-Rips filtration
• Stability of 0-dimensional persistent homology in enriched and sparsified point clouds
• Parameterized Vietoris-Rips Filtrations via Covers