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 present a new algorithm for computing zigzag persistent homology, an algebraic structure which encodes changes to homology groups of a simplicial complex over a sequence of simplex additions and deletions. Provided that there is an algorithm that multiplies two n×n matrices in M(n) time, our algorithm runs in O(M(n) + n2 log2 n) time for a sequence of n additions and deletions. In particular, the running time is O(n2.376), by result of Coppersmith and Winograd. The fastest previously known algorithm for this problem takes O(n3) time in the worst case. In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any @C>0, it returns only those homology classes with persistence at least @C. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant @[email protected]?(0,1), the running time is O(C"("1"-"@d")"@CR"d(n)logn), where C"("1"-"@d")"@C is the number of homology classes with persistence at least ([email protected])@C, n is the total number of simplices in the complex, d its dimension, and R"d(n) is the complexity of computing the rank of an nxn matrix with O(dn) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C"("1"-"@d")"@Cn^2^.^3^7^6) algorithm, an O(C"("1"-"@d")"@Cn^2^.^2^8) Las-Vegas algorithm, or an O(C"("1"-"@d")"@Cn^2^+^@e) Monte-Carlo algorithm for an arbitrary @e>0. The space complexity of the Monte-Carlo version is bounded by O(dn)=O(nlogn).