Wasserstein convergence of Cech persistence diagrams for samplings of submanifolds

Dear reviewer,

Thank you very much for your interest in our work. We address the issue of noisy data in our response to all reviewers, and we agree that similar guarantees for the Vietoris-Rips complex would be valuable; in fact, we are already working towards proving such results.

Regarding experiments in particular, preliminary investigations suggest that comparable results should hold for the Vietoris-Rips persistence, and also seem to support what we explain regarding noisy data in our general response.

Dear reviewer,

Thank you for your appreciation of the overall quality of our work.
We discuss the soundness and importance of our noiseless data hypothesis, as well as the relevance of our work for the ML community, in our response to all reviewers.
Regarding specifically the question Why NeurIPS rather than a journal specialized in TDA?, our understanding is that any high-quality contribution to a subfield of Machine Learning (e.g. TDA, bandits, causality, fairness, etc.) is welcome at NeurIPS, though such a contribution could also be submitted to a more specialized journal or conference.

Dear reviewer,

Thank you for your appreciation of our work and your interesting questions. We discuss noisy data in general in our response to all reviewers. To answer your questions more specifically:

Is there any hope that (at least part of) the main probabilistic result (Corollary 4.3) still holds for non-generic manifolds? :

No, one can build strong counter-examples (e.g. with a well-chosen union of circles in a high-dimensional space). In fact, such configurations will be studied at length in our next work on persistent homology dimension.

Could the genericity assumption be removed if we instead assume that the data is sampled from a manifold plus noise?

This is a very interesting question, whose answer seems to depend on the kind of noise considered. See also our discussion of noisy data in our answer to all reviewers.

Theorem 3.3 fails for non-generic manifolds. Is it possible to quantify (say, with a number or function) how generic a manifold is, in such a way that the constants of Theorem 3.3 only depend on the level of genericity of the manifold?

It might be doable, but it would require a lot of additional (and somewhat tedious) work. Indeed, the proofs of [ACSD 23] rely on nonquantitative compactness arguments; quantitative versions of these arguments would need to be developed to achieve such a result.

In your summary of Corollary 4.3, in the introduction, why don't you say that optimal transport convergence occurs if and only if $p>m$?

Convergence also occurs if $i\geq m$ and $p=m$. Furthermore, we do not know under which precise conditions it occurs when $p<m$ and $i\geq m$.

The manifold being generic also seems like a limitation to me. It seems genericity could fail in highly structured scenarios (data sampled from a configuration space or a simulation of a dynamical system). Please correct me if I am wrong.

You are right to point out that we cannot expect all submanifolds to be generic. However, one can easily build counter-examples to most of our results if the genericity assumption is dropped - as such, the need for genericity is not really a limitation of our work in itself, but rather an unavoidable constraint. Note also that not all highly structured scenarios are hopeless: in particular, it has been shown that among real algebraic submanifolds (a highly non-generic and structured subset of all submanifolds), a generic subset satisfies conditions similar to ours (see e.g. https://arxiv.org/abs/2402.08639).

Dear reviewer,

Thank you for your feedback. We address your concerns and your question in our response to all reviewers.

We thank the AC for taking the time to write a detailed comment. To summarize, the AC is not specifically criticizing our work, but rather the use of persistent homology (PH) as a method in data analysis in general.
Their criticisms focus on two arguments: (1) PH is a weak isometry invariant, in particular when compared to the distribution of pairwise distances and (2) when used with the Cech filtration, it is too slow to compute PH for time-critical applications. Before addressing these two concerns, let us remark that it is true that we did not compare PH to other methods in our work, nor discussed about computational concerns of PH-based methods. This is due to a very simple reason: this is not the topic of our paper, which is focused on providing an extensive theoretical study of a basic method in Topological Data Analysis (computing the Cech persistence diagram of a set of points) under the manifold hypothesis. Other papers that compare PH-based methods to other methods in machine learning already exist, and have even been published at NeurIPS, see e.g. [1]. They show that PH achieve state-of-the-art performance on a variety of tasks, which explains its use by an active community of researchers, see e.g. the various applied papers we cite in the introduction. Let us now respond to the two concerns:

• PH is a weak isometry invariant. This is true! We thoroughly agree with the AC: PH should not be used for isometry detection. The problem of testing whether two sets of points are (approximately) isometric is a delicate question topic, which has been addressed from several different perspectives. Beyond the papers cited by the AC, one could also consider other approaches, such as the one proposed by Brécheteau, who builds isometry tests with prescribed asymptotic levels, see [2].

  In applications, PH is typically not used for isometry detection, but as a complementary tool to other methods. As explained by Turkes & al. in [1], PH is useful to detect geometric or topological quantities such as the number of holes, the presence of curvature, or convexity, and has the advantage of producing easily interpretable features. This argument is the general argument used in works on persistence and not something specific to this (theoretical) paper, which is why we did not repeat it.

  To summarize, building complete isometric invariants is an interesting research topic, but it is not related to PH, and it is not the subject of our work.

• Cech persistence diagrams are ``too slow for real data''. Known upper bounds for the time complexity for computing \v Cech persistence diagrams for a set of $n$ points in dimension $d$ are of order $O(n^{3d/2})$. Note that this is only a rough upper bound in a worst case scenario. In practice, computing the Cech persistence diagram of a set of $n=10^4$ points for $d=3$ takes only a couple of seconds on a standard laptop. Still, as the AC rightfully indicates, the computation of Cech persistence diagrams notoriously suffers from the curse of dimensionality, and Cech persistence diagrams are used for low-dimensional problems in practice (say $d\leq 4$). In higher dimensional settings, a variant of Cech persistence diagrams, called Rips persistence diagrams are used. Rips persistence diagrams are only based on the distance matrix of the data points, and can therefore be computed in high-dimensional settings. Moreover, several research teams have designed fast algorithms to compute them, see [3,4,5]. To give an order of magnitude, the Rips PD of a point cloud of size $10^4$ in dimension $100$ can be computed in roughly $10$ seconds on a 2017 Macbook Pro. Rips persistence diagrams are generally believed to behave in a qualitatively similar way to Cech persistence diagrams in most situations. Still, we choose to focus on Cech persistence diagrams in this article, their connections to critical points of the distance function to a set making them tailored to our study. We ran additional numerical experiments with Rips PDs instead of Cech PDs, with similar behaviors observed. Proving the corresponding asymptotics for Rips PDs constitutes an exciting open problem.

Regarding the AC's specific question Do all experiments considered only uniformly sampled points on a square and a 2-dimensional torus?: We consider non-uniform samplings on ``deformed’’ two-dimensional tori such as the one displayed in Figure 3.

[1] https://proceedings.neurips.cc/paper_files/paper/2022/file/e637029c42aa593850eeebf46616444d-Paper-Conference.pdf

[2] https://inria.hal.science/hal-01426331v3/document

[3] GUDHI

[4] Ripser

[5] Ripser++