Approximating persistent homology for a cloud of n points in a subquadratic time
share
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^2^2 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^2), which is subquadratic in n.
READ FULL TEXT