Computing the persistence homology of the sublevel sets of a function

Question

I have a question somewhat in line with the one asked here. That is, I am interested in how the persistent homology for a sublevel set of a function ($\{x \: : \: f(x) \leq c\}$) is computed. For finite point clouds it is my understanding that a filtration of complexes is constructed directly from the point cloud, which is then used to construct the persistent homology.

But a sublevel set may not be finite, so how do you compute it's persistent homology? In the aforementioned post, someone describes a strategy where a grid is placed over the entire input space, and grid points lying inside the sublevel set are used to construct a filtration of complexes, from which the persistent homology can be computed (if I am understanding correctly).

First of all, this method seems like it would depend exponentially on the dimension of the input space.
Are there faster approaches for high dimensional spaces?

Second of all, how is this approach theoretically justified? I can see intuitively why such an approximation would work once the grid is fine enough, but wondered if there is a rigorous explanation. For example, is there a theorem that says once the grid is fine enough that some complex in the filtration will be homeomorphic to the sublevel set?

Answer 1

1. Sometimes the function $f$ is naturally already defined on a simplicial complex on which it is "monotone". This bypasses the need for fitting a grid. More generally, if $f$ has some nice properties such as piecewise-linearity, then you may be able to find a more efficient grid that scales better with dimension. Or, if you could somehow find the critical points of $f$, then there are simpler filtered complexes available. However, if you don't know anything about $f$ a priori, then it's hard to do better than finding a discrete approximation since a function - even if continuous - can be arbitrarily complex.
2. It's probably too much to ask for equivalent filtered complexes. Instead, if we look at homology and allow for small errors in approximation (measured in the bottleneck distance for persistence diagrams, say), then your second question can be answered by the well-known stability theorem of Cohen-Steiner, Edelsbrunner, and Harer. More precisely, given some bound on the local oscillations of $f$, a fine mesh size translates to a bound on the difference between $f$ and its discrete approximation, which implies that the resulting bottleneck distance between the corresponding diagrams is small.