Is there an upper bound on the number of points in point cloud for which we compute the persistent homology?

Question

I am interested in the topic of persistent homology (topological data analysis). According to what I read, there is some roadblock in the analysis of "big data" using persistent homology as it is considered rather computationally intensive. Computation of the simplicial complexes of a large point cloud often relies on extracting a sample. For example we use a witness complex.

My main question is, what is the current maximum or upper bound on the number of points in the point cloud for computing persistent homology?

Or in other words, what is the "world-record" in the number of points allowed by state-of-the-art persistent homology algorithms? Is it in the range of thousands of points, or millions of points?

Answer 1

It depends very much on the type of simplicial complex you're using. If you have points in 3d then doing Cech/Delaunay complex is feasible with millions of points. If you have high dimensional data, complexes will generally blow up in size and millions of points will be too much. Finding ways to decrease the size of complexes, possibly using approximations (eg witness complexes), is an active research area. It is hard to formulate a precise answer because it depends too much on how nice the data is and how much error is tolerated.

Answer 2

Possibly of interest to you is this paper, A roadmap for the computation of persistent homology by Otter, Porter, Tillmann, Grindrod, and Harrington. They compare different pieces of software for computing persistent homology, and list off the maximum sizes of simplicial complexes that each software could handle under their constraints.

It looks like in the paper that they were mostly working with either $2$- or $3$-dimensional data sets. Anyways, to answer your question, we can compute the persistent homology of data sets consisting of at least $10^9$ points. The above table is from this presentation by Nina Otter.