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

Vitaliy Kurlin

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^2\log^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\times 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$.
BibTeX
@misc{kurlin2013approximating,
  author = {Vitaliy Kurlin},
  title = {{Approximating persistent homology for a cloud of $n$ points in a subquadratic time}},
  year = {2013},
  eprint = {1312.1494},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1312.1494},
}

Loading related content...

Figure