Wasserstein convergence of Cech persistence diagrams for samplings of submanifolds

Authors: charles  arnal
david  cohen-steiner
vincent  divol
  crest
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 18:04:43

Abstract: Cech Persistence diagrams (PDs) are topological descriptors routinely used to capture the geometry of complex datasets. They are commonly compared using the Wasserstein distances $\mathrm{OT}_p$; however, the extent to which PDs are stable with respect to these metrics remains poorly understood. 
We partially close this gap by focusing on the case where datasets are sampled on an $m$-dimensional submanifold of $\mathbb{R}^d$. Under this manifold hypothesis, we show that convergence with respect to the $\mathrm{OT}_p$ metric happens exactly when $p>m$. We also provide improvements upon the bottleneck stability theorem in this case and prove new laws of large numbers for the total $\alpha$-persistence of PDs. Finally, we show how these theoretical findings shed new light on the behavior of the feature maps on the space of PDs that are used in ML-oriented applications of Topological Data Analysis.

Main paper: 
 introduction: 
 Topological Data Analysis (TDA) is a set of tools that aims at extracting relevant topological information from complex datasets, e.g. regarding connected components, loops, cavities, or higher dimensional features. These different notions are made formal through the use of homology theory, and in particular the i-th homology group H i (A) of a set A, which captures the i-dimensional topological features of A for i ≥ 0, see e.g. [46] or Appendix B. TDA has been successfully applied in a variety of domains, including material science [51, 63, 30, 17] , biology [21, 68, 8] , real algebraic geometry [29, 35, 28, 44] and neuroscience [67, 61, 18] , to name a few. When used in conjunction with more traditional approaches such as neural networks, TDA-based methods have outperformed state of the arts methods for tasks such as graph classifications [19, 50] .The most prominent techniques in TDA rely on multiscale approaches, in particular through the use of persistent homology [22] . Given a compact set A in R d , persistent homology tracks the evolution of the homology groups H i (A t ) of the t-offset A t = x∈A B(x, t) of A as t goes from 0 to +∞ (where B(x, t) is the closed ball of radius t centered at x). The process is summarized by the Čech persistence diagram (PD) of degree i of the set A: the PD dgm i (A) is a multiset2 of points in the half-plane Ω := {(u 1 , u 2 ) ∈ R 2 : u 1 < u 2 }, where each point (u 1 , u 2 ) in the PD corresponds to a i-dimensional topological feature that appeared in A t at scale t = u 1 (its birth time) and disappeared at scale t = u 2 (its death time), see Figure 1 . 3 Points close to the Figure 1 : The Čech PD of a point cloud A in R 2 for i = 1 and its t-offsets. The two points far from the diagonal ∂Ω in dgm i (A) correspond to the two large cycles in the set A.diagonal ∂Ω = {(u 1 , u 2 ) ∈ R 2 : u 1 = u 2 } correspond to topological features of small persistence pers(u) = u2-u1 2 , which have a short lifetime in the filtration (A t ) t≥0 .A key property of PDs is their robustness to small perturbation in the data, making them suitable for analyzing real-world datasets. This stability property is phrased in terms of the bottleneck distance between PDs [36] . Let a and b be two PDs. A partial matching between a and b is a bijection of multisets γ : a ∪ ∂Ω → b ∪ ∂Ω, where each point (u, u) of ∂Ω has infinite multiplicity. In other words, the points of a are either paired with a single point of b, or mapped to the diagonal ∂Ω (and similarly for the points of b). Let Γ(a, b) be the set of all partial matchings between a and b. The bottleneck distance is defined asEQUATIONThe Bottleneck Stability Theorem [26, 22] states that if A 1 and A 2 are two compact sets, then for anyEQUATIONwhere ε is the Hausdorff distance between the sets A 1 and A 2 , defined by d H (A 1 , A 2 ) = sup x∈R d |d A1 (x) -d A2 (x)| and where d A is the distance function to a set A. An important property of the bottleneck distance is that it is blind to small-persistence topological features: if OT ∞ (a, b) = ε, then one can arbitrarily modify the PDs a and b on a slab of width ε above the diagonal (for the ℓ ∞ -metric) without changing the bottleneck distance between the two PDs.Due to this phenomenon, the bottleneck distance turns out to be too weak in many situations of interest, where some topological features of small persistence can be as important as large-scale topological features in the PD (say, with a classification or a regression task in mind). For this reason, finer transport-like distances are often preferred to compare PDs. These distances, which we denote as OT p , are defined for 1 ≤ p < ∞ byEQUATIONwith OT p ≤ OT p ′ for 1 ≤ p ′ ≤ p < ∞. They can be seen as modified versions of the Wasserstein distances used in optimal transport, with the diagonal ∂Ω playing the role of a landfill of infinite mass, see e.g. [33] .The increased sensitivity to small perturbations of the OT p distances is of crucial importance in the standard TDA pipeline, which we briefly recall. Starting from a sample of sets A 1 , . . . , A n , one computes a sample of PDs a j = dgm i (A j ), j = 1, . . . , n. Statistical methods to analyze this sample of PDs are typically awkward to define, due to the nonlinear geometry of the space of PDs [16, 75] . To overcome this issue, the space of PDs is mapped to a vector space through some map Φ called a feature map. Statistical method are then applied in the feature space on the transformed sample Φ(a 1 ), . . . , Φ(a n ). Various feature maps have been designed [23, 60, 25, 54, 20, 70, 53, 48] , important examples including persistent images [4] , PersLay [19] , and PLLay [50] ; in the latter two, the feature map is parametrized by a neural network. A good feature map should preserve as much as possible the geometry of the space of PDs [57] ; in particular, Lipschitz (or Hölder) continuity of the feature map is a basic requirement. However, due to their (often desirable) sensitivity to small scale features, most common feature maps are not regular with respect to the OT ∞ distance on the space of diagrams. Instead, they enjoy Lipschitz regularity with respect to either the finer OT 1 distance (see e.g. [33, Proposition 5.2] ), or to the OT p distances (for p > 1) when restricted to diagrams a whose α-total persistence Pers α (a) = u∈a pers(u) αis bounded for some α > 0 large enough, see [34] and [53] . Boundedness assumptions on the α-total persistence also yield a version of the Bottleneck Stability Theorem with respect to the finer OT p distance: if A 1 and A 2 are such that Pers α (dgm i (A k )) ≤ M (k = 1, 2), then, for p ≥ α,EQUATIONwhere ε = d H (A 1 , A 2 ), see [27] . Hence, in addition to having intrinsic theoretical interest, controlling the total persistence and convergence with respect to the OT p distance of PDs is crucial to ensure the soundness of most methods commonly used in TDA. This is the subject of this article.Contributions. We provide a deeper understanding of the structure of Čech PDs in the specific case where the underlying set A is a compact subset of am m-dimensional manifold M in R d , focusing in particular on the total persistence of the PDs and their convergence to the PDs of M with respect to the OT p distances. The importance of this case is supported by the manifold hypothesis, which often serves as a fundamental principle guiding the development of algorithms and models for data analysis [41, 76, 15] . Specifically, our main contributions are the following:• Theorem 2.2: When A ⊂ M is a compact set satisfying d H (A, M) ≤ ε for ε small enough, we provide a quadratic improvement upon the standard Bottleneck Stability Theorem (2) . Namely, we show that there exists an optimal bottleneck matching γ such that the distance between a coordinate of a point u ∈ dgm i (A) and the coordinate of the matched point γ(u) ∈ dgm i (M) ∪ ∂Ω is of order O(ε 2 ) whenever the coordinate of u is larger than 2ε.• Theorem 3.3: In the case where the manifold M is generic and the set A is a δ-sparse point cloud (i.e. min x̸ =y∈A ∥x -y∥ ≥ δ), we provide a finer analysis by showing that the p-total persistence Pers p (dgm i (A)) remains bounded and the distance OT p (dgm i (A), dgm i (M)) converges to 0 for all p > m whenever the ratio ε/δ is upper bounded. • Corollary 4.3: We then focus on a random context, by assuming that A = A n is obtained by sampling n i.i.d. random variables with positive bounded density f on a generic manifold M. We prove that OT p (dgm i (A n ), dgm i (M)) converges in expectation to 0 for p > m. Furthermore, we obtain a law of large numbers for the α-total persistence of dgm i (A n ):EQUATIONfor all α > 0, where C i is a constant that depends explicitly on M and f . In particular, for 0 ≤ i < m, Pers α (dgm i (A n )) stays bounded if and only if α ≥ m.Our contributions are to be compared to one of the only preexisting results regarding the α-total persistence of a PD: in [27] , the authors proved that for all α strictly greater than the ambient dimension d, the α-total persistence of the Čech PD of a compact set A ⊂ B(0, R) ⊂ R d satisfiesEQUATIONfor some constant C α,d depending on α and d. In the two scenarios we considered (either δ-sparse or random samples), the ambient dimension d in the constraint α > d for the control of the α-total persistence in (7) has been replaced by the smaller intrinsic dimension m of the problem: the manifold hypothesis has been successfully exploited.To summarize, our work sheds light on the behaviour of PDs, provides new guarantees for commonly used ML methods (see e.g. Corollary 4.4), and suggests new heuristics (see Section 5) . We also perform various experiments to illustrate the validity of our results and their relevance to the classic TDA pipeline. All proofs are deferred to the Appendix.Related work. This work is part of a long ongoing effort to understand simplicial complexes and PDs in a random context [10, 12, 13, 11, 49, 32, 59, 14, 45] . Closest to our work, Hiraoka, Shirai and Trinh gave limit laws for Čech PDs for random points in the cube [0, 1] d [47] , while Goel, Trinh and Tsunoda gave similar asymptotics in the case of samples on manifolds [42] . Limit laws for the total persistence have been obtained by Divol and Polonik in the case of random samples in the cube [34] . Among other contributions, this work generalizes this result to submanifolds: unlike the cube, a manifold has a nontrivial topology; a fact which considerably complicates the situation, for we have to take into account the presence of large topological features in the Čech PDs in order to control the total persistence. Note also that tools other than persistent homology exist for studying the geometry of point clouds. For instance, the authors in [77, 52] consider complete isometric invariants for point clouds that are computable in polynomial time. 
čech persistence diagrams for subsets of submanifolds: 
 Recall that a fundamental result in TDA, the Bottleneck Stability Theorem (2), states that Čech PDs are stable with respect to Hausdorff perturbations. Consider the particular setting where one has access to a set A, obtained as an approximation of an unknown shape of interest S through some sampling procedure, with A ⊂ S and sup x∈S d A (x) ≤ ε. The Bottleneck Stability Theorem ensures that OT ∞ (dgm i (A), dgm i (S)) ≤ ε for any i ≥ 0, a bound which cannot be improved in general. However, it turns out that a finer understanding of the proximity between dgm i (A) and dgm i (S) can be obtained if more regularity is assumed on the shape of interest S, namely in the situation where S = M is a compact submanifold with positive reach.Let us first set some notation. Let M be an m-dimensional compact topological submanifold of R d ; we always assume that the boundary of M is empty. The orthogonal projection π M on M is defined for x close enough to M, and we define the reach τ (M) as the largest r > 0 such that the orthogonal projection π M is well (i.e. uniquely) defined for all x ∈ R d at distance strictly less than r from M.The reach is a key notion to quantify the regularity of a manifold, see e.g. [39] and [24] for more information.Let A ⊂ M be such that d EQUATION(1) We can build upon this basic remark to obtain a very precise control of the behavior of the Čech PD of the set A. Namely, we identify three regions in the upper halfplane Ω (displayed in Figure 2 ) which contain all points in the PD dgm i (A) (for some integer i ≥ 0). In the first region, corresponding to microscopic topological features disappearing at scales smaller than ε + ε 2 /τ (M), the Bottleneck Stability Theorem cannot be improved. However, there exists an optimal matching (i.e. a matching γ : dgm i (A) ∪ ∂Ω → dgm i (M) ∪ ∂Ω that realizes the bottleneck distance (1) ) such that at least one of the coordinates of any point in the other two regions is larger than τ (M) -ε 2 /τ (M), and the proximity between a large coordinate of a point u ∈ dgm i (A) and the coordinate of the matched point γ(u)Cε 2 Cε 2 Cε 2 ε ε∈ dgm i (M) ∪ ∂Ω is of order O(ε 2). This yields a quadratic improvement upon the Bottleneck Stability Theorem.Theorem 2.2 (Improved Bottleneck Stability Theorem). Let M ⊂ R d be a compact submanifold with positive reach and let A ⊂ M be a compact set such that d H (A, M) ≤ ε < τ (M)/4. Let i ≥ 0 be an integer. Then dgm i (A) is the union of three regions dgm(1) i (A) := dgm i (A) ∩ {u 1 , u 2 ≤ ε + ε 2 τ (M) }, dgm (2) i (A) := dgm i (A) ∩ {u 1 ≤ ε, u 2 ≥ τ (M) -ε 2 τ (M) } and dgm (3) i (A) := dgm i (A) ∩ {u 1 , u 2 ≥ τ (M) -ε 2 τ (M) }. Furthermore, let C = 2 τ (M) 1 + R(M) τ (M), where R(M) is the radius of the smallest ball that contains M. There exists an optimal matching γ : dgm i (A) ∪ ∂Ω → dgm i (M) ∪ ∂Ω for the bottleneck distance between dgm i (A) and dgm i (M) such that• Region (1): If u ∈ dgm (1) i (A), then γ(u) ∈ ∂Ω and ∥u -γ(u)∥ ∞ ≤ ε. • Region (2): If u ∈ dgm (2) i (A), then γ(u) is of the form (0, v 2 ) and |u 2 -v 2 | ≤ Cε 2 .The number of such points is finite and depends only on M.• Region (3): If u ∈ dgm (3) i (A), then ∥u -γ(u)∥ ∞ ≤ Cε 2 .Note that for any i ≥ d, the i-th PDs of M and A are actually trivial. 
čech persistence diagrams for subsets of generic submanifolds: 
 The improved Bottleneck Stability Theorem (Theorem 2.2) yields information relative to the location of points in the Čech PD of A, but not about their numbers. However, both the α-total persistence of dgm i (A) and the distance OT p (dgm i (A), dgm i (M)) for p < ∞ crucially depend on the number of points in dgm i (A) having small persistence.Unfortunately, no control on, say, the total persistence, can exist without additional assumptions. Indeed, in general, even the α-total persistence of the Čech PD of the submanifold M can be infinite. Example 3.1. Let f : x ∈ R → 1 + x 4 sin(1/x) 2 . Consider the C 2 curve M in R 2 defined as the union of the graphs of the functions f and -f on [-2, 2]. Being C 2 , the curve has a positive reach [39] . For i = 1, the Čech PD of M contains a sequence of points (1, ℓ n ) for n ≥ 1, where ℓ n = 1 + Θ(n -4 ). In particular, as n≥1 (ℓ n -1) α = +∞ for α < 1/4, the α-total persistence of dgm 1 (M) is infinite for such a value of α. By considering the product M m ⊂ R 2m , one can also build an m-dimensional C 2 compact submanifold without boundary such that dgm 1 (M) has an infinite α-total persistence for α < m/4. In what follows, we will simply refer to a C 2 compact submanifold M such that d M satisfies the regularity condition described in Appendix C as generic. See Figure 3 for an example. Proposition 3.2 ( Čech PDs of generic submanifolds). Let M be a generic submanifold of R d . Then, for any integer i ≥ 0, the PD dgm i (M) contains finitely many points. In particular, Pers α (dgm i (M)) < +∞ for all α > 0.When M is a generic submanifold, it becomes a reasonable task to control the number of points in dgm i (A) where A ⊂ M is an approximation of M with d H (A, M) ≤ ε. The Bottleneck Stability Theorem implies that when ε is small enough (compared to the smallest persistence of a point in dgm i (M)), every point of dgm i (M) is mapped to a point in dgm i (A) by the optimal bottleneck matching, leaving the points of dgm i (A) at ℓ ∞ -distance to ∂Ω less than ε unmatched; those will be mapped to the diagonal ∂Ω. The Improved Bottleneck Stability Theorem 2.2 (see Figure 2 ) shows that these points are of two kinds: those in Region (1), corresponding to small topological features in the set A (of size of order O(ε)), and those in Region (3), corresponding to large topological features. There are many points in Region (1) (in fact, our proofs show that when A = A n is a random sample of n points, the number of points in Region (1) is of order O(n)). In contrast, the genericity hypothesis allows us to show that the number of points in Region (3) is small under reasonable sampling assumptions.We say that a point cloud A ⊂ M is (δ, ε)-dense in M if d H (A, M) ≤ ε and min x̸ =y∈A ∥x -y∥ ≥ δ. Such point clouds naturally occur, e.g. as products of the farthest point sampling algorithm [2] . Theorem 3.3. Let M ⊂ R d be a generic compact submanifold and A ⊂ M be a (δ, ε)-dense set in M for some ε, δ > 0. Let a ≥ ε/δ and let i ≥ 0 be an integer. There exist ε 0 > 0 depending only on M and C 0 , C 1 , C 2 , C 3 depending only on M and a such that if ε ≤ ε 0 , then dgm EQUATIONIn particular, as long as the ratio ε/δ is larger than some constant a > 0, the OT p distance between dgm i (A) and dgm i (M) converges to 0 for all p > m as ε → 0, while the p-total persistence Pers p (dgm i (A)) stays bounded.Example 3.4. Consider two parallel line segments M in R 2 , and a finite set A consisting of two parallel grids of step 2ε: the set A is (2ε, ε)-dense in M. Then, there are O(ε -1 ) points in dgm 1 (A) with birth coordinates u 1 equal to 1/2 and persistence of order O(ε 2 ); they all belong to dgm(3) 1 (A), whose cardinality is thus not bounded by some C 0 = C 0 (M). This example can be easily modified to make M a compact C 2 1-dimensional manifold. This shows that the first conclusion of Theorem 3.3 cannot hold without a genericity assumption on M. 
random samplings of submanifolds: 
 We now turn to the case of random samplings of (non-generic and generic) submanifolds. They tend to adopt configurations that are more regular than what can be expected from e.g. a general ε-dense sampling, yet their randomness gives rise to new technical difficulties. Let P be a probability measure having a density f (with respect to the volume measure) on a compact submanifold M of dimension m ≥ 1. Let A = A n = {X 1 , . . . , X n }, where X 1 , . . . , X n is an i.i.d. sample from distribution P . Let i ≥ 0 be an integer; we consider the three regions described in Figure 2 and in the statement of Theorem 2.2, and write again dgmEQUATIONi (A n ) and dgm (3) i (A n ) for the three corresponding PDs. This section is devoted to the study of the probabilistic asymptotic behaviour of these three random PDs, which can be decomposed into two almost independent questions: dgm (1) i (A n ) only depends on small-scale phenomena and can essentially be reduced to the case of a cube, even if M is non-generic, while dgm (2) i (A n ) and dgm (3) i (A n ) are tightly connected to the macroscopic geometry of the submanifold and can be further controlled using genericity assumptions on M.Describing the limit behavior of the random PD dgm (1) i (A n ) requires extending the metric OT p between PDs to more general Radon measures. Indeed, a PD can equivalently be seen as an integervalued discrete Radon measure on Ω, by identifying a multiset a with the Radon measure u∈a δ u . Let M denote the space of Radon measures on Ω, that is the space of Borel measures on Ω which give finite mass to every compact set K ⊂ Ω. 4 The space of Radon measures is endowed with the vague topology, where a sequence (µ n ) n of measures in M is said to converge vaguely to µ ∈ M if Ω ϕdµ n → Ω ϕdµ as n → ∞ for all continuous functions ϕ : Ω → R with compact support. The α-total persistence is defined for µ ∈ M by Pers α (µ) = Ω pers(u) α dµ(u). For p ≥ 1, we let M p = {µ ∈ M : Pers p (µ) < +∞}. The distance OT p , defined between PDs in (3), can be extended to the set M p , see [33] . The distance OT p between Radon measures is a variation of the Wasserstein distance, with the important difference that the standard Wasserstein distance is only defined for measures having the same mass, while the distance OT p is defined for measures having different (and even infinite) masses. We refer to Appendix F for the precise definition and the main properties of the OT p distance on the space M p . For q > 0, given a function f : N → R and a sequence of (nonnecessarily measurable) real maps (Y n ) n defined on some probabilisitic space, the notationY n = O L q (f (n)) means that E * [|Y n | q ] = O(f (n) q ), where E * denotes the outer expectation [73, p.6] (and similarly for the little o notation).Consider the rescaled Radon measure µ n,i = 1 n u∈dgmi (An) δ n 1/m u , and note that µ n,i is a random measure, owing to the randomness of the set A n . Goel, Trinh and Tsunoda studied the vague convergence of the sequence (µ n,i ) n [42, Remark 4.2] . Namely, assuming that the density f satisfies M f j < ∞ for all j ≥ 0, they show that with probability 1 the sequence (µ n,i ) n converges vaguely to some (non-random) Radon measure µ f,i . The limit measure µ f,i has support {0} × R + if i = 0 and Ω if 0 < i < m; it is the zero measure if i ≥ m. We can further describe it as follows: let µ ∞,i,m be the limit of the sequence (µ n,i ) in the case where the sample A n is uniform on the unit cube [0, 1] m (see [34] ). Then, for any continuous function ϕ : Ω → R with compact support,EQUATIONNote that the vague convergence of Radon measures is only defined with respect to compactly supported functions; as such, it is blind to phenomena located increasingly close to the diagonal ∂Ω as n goes to infinity. In particular, and except in the case of the uniform distribution on the unit cube [0, 1] m (see [34] ), it was not known whether µ n,i converges to µ f,i for the OT p distance as well, nor whether the sequences of total persistence (Pers α (µ n,i )) converge. We close this gap with the following result. Theorem 4.1 (Law of large numbers). Assume that P has a density f on M bounded away from 0 and ∞. Let i ≥ 0 be an integer and let1 ≤ p < ∞. Then µ f,i ∈ M p and E[OT p p (µ n,i , µ f,i )] ----→ n→∞ 0.Furthermore, for all α > 0, Pers α (dgmEQUATION.It is a well-known fact that the Hausdorff distance ε = d H (A n , M) between a random sample and M is of order (log n/n) 1/m whenever the underlying density f is bounded away from zero and ∞ on M, see e.g. [38] . Hence the PDs dgmi (A n ) and dgmi (A n ) can be described using Theorem 2.2. However, in the case where M is a generic submanifold, one can actually obtain tighter results. We let #E denote the cardinality of a multiset E. Proposition 4.2. Let M be a generic m-dimensional submanifold. Assume that P has a density f on M bounded away from 0 and ∞. Let i ≥ 0 be an integer. There exists an optimal matching γ n : dgm i (A n )∪∂Ω → dgm i (M)∪∂Ω for the bottleneck distance between dgm i (A n ) and dgm i (M) such that for any q ≥ 1:• Region (2): It holds that max u∈dgm (2) i (An) |u 2 -γ n (u) 2 | = O L q (n -2/m ). • Region (3): It holds that max u∈dgm (3) i (An) ∥u -γ n (u)∥ ∞ = O L q (n -2/m) and #(dgm(3) i (A n )) = O L q (1).We remark that the same bounds can be obtained almost surely (e.g. "a.s. there exists C > 0 such that max u∈dgm (3) i (An) ∥u -γ n (u)∥ ∞ ≤ Cn -2/m "), rather than in expectation, using similar arguments. Proposition 4.2 yields two distinct improvements upon direct applications of Theorem 2.2 and Theorem 3.3 to the random case. First, we obtain bounds of order n -2/m instead of bounds of order (log n/n) 2/m . Second, the random sample A n is in general only δ-sparse for δ of order n -2/m . Hence, A n is (δ, ε)-dense in M, but with a diverging ratio ε/δ. Therefore, Theorem 3.3 cannot be applied to control the total number of points in dgm i (A n ) in Region (3).As a simple consequence of Theorem 4.1 and Proposition 4.2, we obtain that for i < m, the p-Wasserstein convergence of (dgm i (A n )) to dgm i (M) holds if and only if p > m, as well as precise asymptotics for the total persistence of (dgm i (A n )). • If p > m, then E[OT p p (dgm i (A n ), dgm i (M))] → 0 as n → ∞. • If p = m, E[OT p p (dgm i (A n ), dgm i (M))] → Pers p (µ ∞,i,m )Vol(M) as n → ∞, where Vol(M) is the volume of M. • If p < m and i < m, then E[OT p p (dgm i (A n ), dgm i (M))] → +∞ as n → ∞. Furthermore, for all α > 0, Pers α (dgm i (A n )) is equal to Pers α (dgm i (M)) + n 1-α m Pers α (µ ∞,i,m ) M f (x) 1-α m dx + o L 1 (n 1-α m ) + O L 1 log n n 1 m . As noted earlier, both dgm i (A n ) and dgm i (M) are trivial if i ≥ d.This corollary gives a precise answer to the questions raised in the introduction. First, when A n is a random subset of a m-dimensional generic manifold in R d , the α-total persistence of dgm i (A n ) is not only bounded for α > d (as was shown by Cohen-Steiner & al. [27] ), but for all α ≥ m. Moreover, the sequence dgm i (A n ) converges for the OT p distance if p > m. A curious phenomenon can be observed in the case p = m: the sequence does not converge to dgm i (M) as one would expect, but its distance to the power p to dgm i (M) converges to some constant-in that case, the cost to the power p of matching all the points in Region (1) to the diagonal ∂Ω neither converges to 0 nor diverges, but is asymptotically equal to this constant.Using these bounds on the total persistence, we obtain regularity guarantees for a large family of feature maps, called linear feature maps, which includes feature maps introduced in [23, 4, 60, 25, 54, 70, 19] . Let (V, ∥ • ∥) be a normed vector space, and let ϕ : Ω → V be a continuous bounded map.For α ≥ 0, the linear feature map Φ α associated to ϕ and defined on the space D f of PDs having a finite number of points is defined for all a ∈ D f by Φ α (a) = u∈a pers(u) α ϕ(u) ∈ V . Corollary 4.4. Let α ≥ 1 and let 0 ≤ i < d be an integer. Under the same assumptions as in Proposition 4.2, it holds thatΦ α (dgm i (A n )) converges in probability to Φ α (dgm i (M)) whenever α > m.Remark that other weighting schemes are possible. For instance, [53] argued for using linear feature maps of the form Φ α (a) = u∈a arctan(pers(u) α )ϕ(u). Similar results would hold for such feature maps, as the map u → arctan(pers(u) α )ϕ(u)/pers(u) α is continuous and bounded whenever ϕ is. 
numerical experiments: 
 We illustrate our results with synthetic experiments, full details are given in Appendix H. We create a generic submanifold of dimension m by applying a random diffeomorphism Ψ to a given mdimensional submanifold M 0 (e.g. a torus). We then draw a sample of n i.i.d. observations sampled according to the pushforward P of the uniform distribution on M by Ψ. i (A n )) as a function of n for points sampled on a circle, i = 0 (left), points sampled on a torus, i = 0 (center), points sampled on a torus, i = 1 (right). Dashed lines have slopes equal to 1 -p/m. Continuity of feature maps. As a first experiment, we test the continuity of a feature map, the persistence image [4] . In Figure 4 , we plot the persistence image of dgm 1 (A n ) where A n is a sample of n = 10 4 points on a generic torus. We observe that the map is discontinuous for p < 2: the two points with large persistence corresponding to the PD of the underlying torus are nonapparent in the image. For p > 2, the two points are apparent, and the contribution of points with small persistence (close to the lower edge) has vanished. In the limit situation p = 2, we see the contribution of both points with large and small persistence. This phenomenon suggests the following heuristics: when in presence of multiple datasets on m-dimensional objects whose global geometries need to be distinguished, feature maps with weights pers p with p > m should be used; when the relevant information is the underlying density of the datasets, the choice p < m should be preferred.Convergence of total persistences. We verify the rate of convergence of the total persistence predicted by Theorem 4.1. For values of n ranging from 10 2 to 10 4 , we compute Pers p (dgm(1) i (A n ))in three scenarios: points sampled on a circle for i = 0, and points sampled on a torus for i = 0 and i = 1. The correct rates of convergence are observed on a log-log plot, see Figure 5 . For i = 1, we remark that the asymptotic regime starts at larger values of n, above n = 10 3 . Convergence of µ n,i . We sample n points on a torus by uniformly sampling the two angles (θ, ϕ) parametrizing the torus. We obtain a (nonnuniform) probability measure, having density f . We then compute, for various values of n, the measure µ n,1 . The measure is approximated by kernel density estimation (see Figure 6 ). We approximate in a similar manner the measure µ ∞,1,2 by sampling n = 10 5 points on a square. We then apply the change of variable formula (9) to compute the theoretical limit µ f,1 . The distance OT 2 (µ n,1 , µ f,1 ) is then computed by approximating the measures on a grid: the distance converges to 0 as predicted by Theorem 4.1. See also Figure 6 .  
conclusion: 
 Under the manifold hypothesis, we have greatly refined earlier work regarding the persistent homology of subsamples of compact sets, with especially strong results when the sampling is either random or well-behaved. In particular, we have precisely described the PDs of such samplings, and provided new convergence guarantees w.r.t. the p-Wassertein distances, as well as detailed asymptotics for their total α-persistence. This results in a deeper understanding of these objects, which play an important role in ML techniques applied to TDA. The main limitations of our work were the assumptions that the data is sampled from a submanifold, and without any noise. Relaxing those assumptions, as well as establishing similar guarantees for Vietoris-Rips complexes, could be the subject of future research. We also plan on exploring the consequences of our findings regarding the persistent homology dimension [3, 66, 9, 65] of submanifolds.[76] Jonathan Weed and Francis Bach. Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli, 25(4A):2620-2648, 2019.[ Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: All the hyperparameters needed to produce the figures in Section 5 are given in Appendix H. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: The two numerical experiments exhibiting rates of convergence (Figure 5 and Figure 6 ) were conducted over multiple runs, with orders of magnitude of the fluctuations presented in Appendix H. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: As stated in the appendix, we only ran small to medium-scale experiments, which each took no more than an hour on a standard office laptop.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? 
 
 Appendix: We recall some basic definitions regarding persistent homology in Appendix B. In Appendix C, we define topological Morse functions and discuss some of the properties of distance functions to compact sets. We also detail the genericity conditions from [6] , and prove Proposition 3.2. We prove Lemma 2.1 and Theorem 2. Although this work is only concerned with PDs with respect to the Čech filtration, it is more natural to define PDs for the sublevel sets of proper continuous functions that are bounded below. We refer to [22] for a thorough introduction to persistent homology and PDs in an even more general context.Let f : R d → R be a proper continuous function that is bounded below-e.g., the distance function to a compact set. For t ∈ R, let X t = f -1 (-∞, t] be the sublevel set of f at level t. The collection (X t ) t∈R is called a filtration. Let i ≥ 0 be an integer. We let H i (X t ) be the homology group of degree i with coefficients in any fixed field F (e.g. F = Z/2Z is a popular choice) of X t . For r < s, the inclusion between the sublevel sets at levels r and s induces a map ι i,r,s at the homology level. We define the persistent Betti numberEQUATION) As shown in [22, Corollary 3.34] , this number is finite. Informally, it represents the number of ith dimensional topological features present in the sublevel set at level r that are still present at level s.Ω ∞ = {u = (u 1 , u 2 ) ∈ (R ∪ {-∞, +∞}) 2 : -∞ ≤ u 1 < u 2 ≤ +∞} and Ω = {u = (u 1 , u 2 ) ∈ R 2 : u 1 < u 2 }.The collection of persistent Betti numbers (β i,r,s (f )) r<s defines a multiset of points in Ω ∞ , called the persistence diagram dgm i (f ) of degree i of f . See e.g. [22] for its precise definition.Though persistence diagrams can have points with infinite coordinates, these will be of little interest in the cases considered in this article 5 . To simplify our notation and definitions, we let from now on dgm i (f ) denote the finite part (i.e. the points whose coordinates are finite) of the diagram of degree i of f , and we assume that every diagram considered henceforth has no point with infinite coordinates. In particular, they are all multisets of the half-plane Ω := {u = (u 1 , u 2 ) ∈ R 2 : u 1 < u 2 }, which leads to the following definition: the space D of persistence diagrams is the set of all multisets a in Ω that contain a finite number of points 6 in every quadrant Q u , u ∈ Ω.Note that while persistence diagrams capture key topological features in an interpretable fashion, they are not complete metric invariants: different sets can have equal persistence diagrams, see e.g. [69] . As such, they can be seen as a form of topology-centered dimensionality reduction technique. Other topological invariants have been proposed, some of which are complete, such as those from [77, 52] .In this section, we consider a special class of PDs -those yielded by the distance function to a compact set A ⊂ R d . We give a detailed description of such a PD when A = M is a generic submanifold.The theory of persistent homology was historically developed for Morse functions f : R d → R. A Morse function f is a C 2 function whose critical points x (points for which d x f = 0) are nondegenerate (meaning that the Hessian of f at x is non-degenerate). The index of the critical point x is equal to the number of negative eigenvalues of the corresponding Hessian. The changes of topology of the sublevel sets of such a function are perfectly understood. First, the isotopy lemma states that two sublevel setsf -1 (-∞, u 1 ] and f -1 (-∞, u 2 ] are isotopic if no critical values are found in the interval [u 1 , u 2 ] and if f -1 [u 1 , u 2 ] is compact. Second, if f -1 [u 1 , u 2 ] is compact and contains the critical points x 1 , . . . , x K , then f -1 (-∞, u 2 ] has the homotopy type of f -1 (-∞, u 1 ]with cells e k of dimension equal to the index of x k attached along their boundaries (see e.g. [56] for a much more in-depth treatment).In such a situation, the PD dgm i (f ) has a clear interpretation: the coordinates (u 1 , u 2 ) of a point u ∈ dgm i (f ) correspond to the critical value of a critical point of index i and i + 1 respectively. Informally, the corresponding i-dimensional topological feature appears with the attachment of a i-dimensional cell at value u 1 , and is "killed" by the attachment of a (i + 1)-dimensional cell at value u 2 .The notion of Morse function extends to continuous functions with the following definition.Definition C.1 (Topological Morse functions [58] ). Let U ⊂ R d be an open set and let f : U → R be a continuous function.EQUATION• A point z ∈ U is said to be a topological critical point of f if it is not a topological regular point of f .EQUATION• The function f is said to be a topological Morse function if all its topological critical points are non-degenerate.For topological Morse functions, both the isotopy lemma and the handle attachment lemma stay valid:Lemma C.2 (Isotopy Lemma). Let f : R d → R be a proper topological Morse function. Let a < b be such that f -1 [a, b] contains no topological critical point. Then f -1 (-∞, a] is a deformation retract of f -1 (-∞, b]. Lemma C.3 (Handle Attachment Lemma). Let f : R d → R be a proper topological Morse function. Let c ∈ R and ε > 0 be such that f -1 [c -ε, c + ε] contains no topological critical point except for z 1 , . . . , z k ∈ f -1 (c), with z j of index i j . Then f -1 (-∞, c + ε] is homotopically equivalent to f -1 (-∞, c -ε] with cells B i1 , . . . , B i k of dimension i 1 , . . . , i k attached, i.e. f -1 (-∞, c + ε] ≃ f -1 (-∞, c -ε] ∪ B i1 ∪ . . . ∪ B i k .Their proofs are roughly the same as for smooth Morse functions -see [71, Theorems 4 and 5] for details. As a consequence, the description of PDs for Morse functions also stays valid for topological Morse functions.In this paper, we are interested in the PDs of the distance function d A to various compact sets A, called the Čech persistence diagram 7 of A and denoted by dgm i (A). In general, such a function is not a topological Morse function. Instead, changes in the topology of its sublevels can be partially (though less completely than for a Morse function) described in terms of zeros of its generalized gradient, which is defined at y ∈ R d \A asEQUATIONwhere σ A (y) = {x ∈ A : ∥x -y∥ = d A (y)} is the set of projections of y on A and c(τ ) represents the center of the smallest enclosing ball of a set τ . When y ∈ R d \A satisfies ∇d A (y) = 0, y is called a differential critical point of d A . We let Crit(A) denote the set of differential critical points of d A .An adapted version of the Isotopy Lemma remains true, as shown in [43] :Lemma C.4 (Isotopy Lemma for Distance Functions). If 0 < a < b are such that d -1 A [a, b] contains no differential critical point of d A , then d -1 A (-∞, a] is a deformation retract of d -1 A (-∞, b]. Consequently, any (u 1 , u 2 ) ∈ dgm i (A) is such that u 1 , u 2 ̸ ∈ [a, b].Without further assumptions, little else can be said regarding the topology of the sublevels of d A ; in particular, there is no equivalent to the Handle Attachment Lemma to control the changes occurring at critical values.However, the distance function d M to a compact C 2 submanifold M ⊂ R d turns out to be a topological Morse function in a "generic" sense, as was proven by Arnal, Cohen-Steiner and Divol. Theorem C.5 (Genericity Theorem [6] ). Let M be a compact C 2 (abstract) manifold. Then the set of C 2 embeddings i :M → R d such that 1. the distance function d i(M ) : R d \i(M ) → R is a topological Morse function,2. for every z ∈ Crit(M), the projections σ M (z) are the vertices of a non-degenerate simplex of R d and z belongs to its relative interior, 3. the set Crit(M) is finite, 4. for every z ∈ Crit(M) and every x ∈ σ M (z), the sphere S(z, d M (z)) is non-osculating M at x, in the sense that there exist δ > 0 and α > 0 such that for all y ∈ M ∩ B(x, δ),EQUATION5. there exist constants C > 0 and µ 0 ∈ (0, 1) such that for every µ ∈ [0, µ 0 ), any pointx such that ∥∇d M (x)∥ ≤ µ is at distance at most Cµ from Crit(M),is open and dense in the set of C 2 embeddings M → R d for the Whitney C 2 -topology.When M is generic, the topological critical points of d M coincide with its differential critical points (see [6, Theorem 1.8] ), and the Čech PD dgm i (M) can be related to the critical points of d M in the same way as for smooth Morse function. We are now in position to prove Proposition 3.2, which we restate for the reader's convenience: Proposition 3.2 ( Čech PDs of generic submanifolds). Let M be a generic submanifold of R d . Then, for any integer i ≥ 0, the PD dgm i (M) contains finitely many points. In particular, Pers α (dgm i (M)) < +∞ for all α > 0.Proof. The proof is similar to that used in the case of smooth Morse functions, with the Isotopy Lemma and the Handle Attachment Lemma playing the same role; we briefly summarize it for completeness nonetheless. We do not distinguish between differential and topological critical values and points, as they coincide.The set Crit(M) is finite: this is simply Condition 3. from the Genericity Theorem. The Isotopy Lemma shows that there is no change in homotopy type between M a and M b if 0 < a < b and [a, b] contains no critical value. Similarly, M has the same homotopy type as M a if a > 0 is small enough. Hence changes in homology in the offsets can only occur at 0, when the entire submanifold appears in the filtration, and at critical values of d M , and there can be no birth or death of interval between them.Let us now consider a critical value c > 0 and 0< ε < c such that d -1 M [c -ε, c + ε] contains no critical point except for z 1 , . . . , z k ∈ d -1 M (c), where z j is of index i j . Then the Handle Attachment Lemma states that M c+ε is homotopically equivalent to M c-ε with cells B i1 , . . . , B i k of dimension i 1 , . . . , i k attached, i.e.M c+ε ≃ M c-ε ∪ B i1 ∪ . . . ∪ B i k .Let i ≥ 1, and let D i,b be the dimension of the cokernel of H i (M c-ε ) → H i (M c+ε ) (where the map is induced by the inclusion): it is precisely the number of births of intervals between c -ε and c + ε (hence precisely at c) in the persistence module of degree i of the filtration. Similarly, the dimensionD i-1,d of the kernel of H i-1 (M c-ε ) → H i-1 (M c+ε) is the number of deaths of intervals at c in the persistence module of degree i -1 of the filtration. A straightforward application of the Mayer-Vietoris exact sequence yields that D i,b + D i-1,d is exactly equal to the number of i-dimensional cells among B i1 , . . . , B i k , meaning that each i-cell corresponds exactly either to the birth of an interval for the homology of degree i, or to the death of an interval for the homology of degree i -1 (in particular, an i -1-cell and an i-cell cannot "cancel each other out"). This proves that for any i ≥ 1, the multiset of critical values d M (z) of critical points z of M of index i is equal to the multisetEQUATIONThis fact proves in turn that dgm i (M) is finite for any i ≥ 0, which immediately implies that Pers α (dgm i (M)) < +∞ for all α > 0.For M a m-dimensional differential submanifold of R d and x ∈ M, we let T x M be the tangent space of M at x, which is identified with a linear subspace of R d . We denote by π x : R d → T x M the orthogonal projection on this subspace and let π ⊥ x = id -π x be the orthogonal projection on the normal space at x. A key property, that we will repeatedly used, is that the reach of M controls the deviation of the manifold M from its tangent space. Namely, [39, Theorem 4.18] states that for all y ∈ M,EQUATION)We also define the weak feature size of M, denoted by wfs(M), as the minimal distance between a critical point of M and M. As by definition, the projection is not unique at a critical point, we must have wfs(M) ≥ τ (M).We first prove Lemma 2.1:Lemma 2.1. Let M ⊂ R d be a compact submanifold with positive reach and let A ⊂ M be a compact set with dH (A, M) ≤ ε for some ε > 0. Let z ∈ R d \M. Then, |d M (z) -d A (z)| ≤ ε 2 2d M (z) 1 + d M (z) τ (M) .Proof. As A ⊂ M, we have d M (z) ≤ d A (z). Let x be a projection of z onto M, and let y ∈ A be a point at distance less than ε from x. Then, using (16) and the fact that z -x is orthogonal to T x M, we obtain thatd A (z) 2 ≤ ∥z -y∥ 2 = ∥z -x∥ 2 + ∥x -y∥ 2 + 2⟨z -x, x -y⟩ ≤ d M (z) 2 + ε 2 + 2⟨z -x, π ⊥ x (x -y)⟩ ≤ d M (z) 2 + ε 2 + d M (z)ε 2 τ (M) .Hence,d A (z) -d M (z) = d A (z) 2 -d M (z) 2 d A (z) + d M (z) ≤ ε 2 2d M (z) 1 + d M (z) τ (M) .We can now prove Theorem 2.2: Theorem 2.2 (Improved Bottleneck Stability Theorem). Let M ⊂ R d be a compact submanifold with positive reach and let A ⊂ M be a compact set such that d H (A, M) ≤ ε < τ (M)/4. Let i ≥ 0 be an integer. Then dgm i (A) is the union of three regions dgm(1)i (A) := dgm i (A) ∩ {u 1 , u 2 ≤ ε + ε 2 τ (M) }, dgm (2) i (A) := dgm i (A) ∩ {u 1 ≤ ε, u 2 ≥ τ (M) -ε 2 τ (M) } and dgm (3) i (A) := dgm i (A) ∩ {u 1 , u 2 ≥ τ (M) -ε 2 τ (M) }. Furthermore, let C = 2 τ (M) 1 + R(M) τ (M), where R(M) is the radius of the smallest ball that contains M. There exists an optimal matching γ : dgm i (A) ∪ ∂Ω → dgm i (M) ∪ ∂Ω for the bottleneck distance between dgm i (A) and dgm i (M) such that• Region (1): If u ∈ dgm (1) i (A), then γ(u) ∈ ∂Ω and ∥u -γ(u)∥ ∞ ≤ ε. • Region (2): If u ∈ dgm (2) i (A), then γ(u) is of the form (0, v 2 ) and |u 2 -v 2 | ≤ Cε 2 .The number of such points is finite and depends only on M.• Region (3): If u ∈ dgm (3) i (A), then ∥u -γ(u)∥ ∞ ≤ Cε 2 .Proof. Proposition 5 from [7] states that if ε = d H (A, M) < ( √ 2 -1)τ (M), then the offset A r deformation-retracts onto M for any r ∈ 1 2 (τ (M) + ε - √ ∆), 1 2 (τ (M) + ε + √ ∆) and ∆ = τ (M) 2 -2ετ (M) -ε 2 .Under the stronger assumption that d H (A, M) < τ (M)/4, and using elementary calculus, we find that the offset A r deformation-retracts onto M for anyr ∈ ε + ε 2 τ (M) , τ (M) - ε 2 τ (M) .This means in particular that the homology type, hence the homology, of A r does not change in that interval; as a result, there can be no birth or death of intervals in the Čech persistence diagrams of A between ε + ε 2 τ (M) and τ (M) -ε 2 τ (M) , and all (u 1 , u 2 ) ∈ dgm i (A) must either be such thatu 1 , u 2 ≤ ε + ε 2 τ (M) , or u 1 ≤ ε + ε 2 τ (M) , u 2 ≥ τ (M) -ε 2 τ (M) , or u 1 , u 2 ≥ τ (M) -ε 2 τ (M). This almost proves that the partition of dgm i (A) into dgm i (A) requires that u 1 ≤ ε, whereas we only have obtained that u 1 ≤ ε + ε 2 τ (M) . Let γ : dgm i (A) ∪ ∂Ω → dgm i (M) ∪ ∂Ω be any optimal matching for the bottleneck distance: then the Bottleneck Stability Theorem states that any point u= (u 1 , u 2 ) ∈ dgm i (A) is such that ∥u -γ(u)∥ ∞ ≤ d H (A, M) ≤ ε. Suppose that u is such that u 1 ≤ ε + ε 2 τ (M) and u 2 ≥ τ (M) -ε 2 τ (M) .Its distance in the infinity norm to the diagonal ∂Ω is equal to(u 2 -u 1 )/2 ≥ (τ (M) -ε - 2ε 2 /τ (M))/2 ≥ 5 16 τ (M) > ε,where we use the fact that ε < τ (M)/4. Hence γ(u) must belong to dgm i (M). Let (v 1 , v 2 ) denote γ(u). As in the proof of Proposition 3.2, the Isotopy Lemma shows that dgm i (M) only contains two types of points: points of the shape (0, w 2 ), which correspond to the homology of M itself, and points of the shape (w 1 , w 2 ), where in both cases w 1 , w 2 are critical values of d M . In particular, both w 1 and w 2 must be greater than wfs(M). Let dgm i (M) denote the multiset of all points of the second type. If v 1 was non-zero, it would have to be greater than wfs(M) ≥ τ (M), and we would have ∥u -γ(u)∥ ∞ ≥ |u 1 -v 1 | ≥ τ (M) -ε -ε 2 τ (M) ≥ τ (M)/2 > ε,which would be a contradiction (we once again use that ε < τ (M)/4). Hence v 1 must be 0 (i.e. γ(u) ∈ dgm (2) i (M)), andu 1 = |u 1 -v 1 | ≤ ∥u -γ(u)∥ ∞ ≤ ε.This proves the correctness of the partition into regions from the statement.Consider now u = (u 1 , u 2 ) ∈ dgm (1) i (A). All v = (v 1 , v 2 ) ∈ dgm i (M) are such that ∥u -v∥ ∞ ≥ v 2 -u 2 ≥ wfs(M) -ε - ε 2 τ (M) ≥ τ (M) 1 - 1 4 - 1 16 > ε ≥ ∥u -γ(u)∥ ∞ ,hence γ(u) must belong to ∂Ω. This completes the proof of the first bullet point of the statement.We have already shown that if γ is an optimal matching and u ∈ dgm(2) i (A), then γ(u) ∈ dgm i (M) is of the form (0, v 2 ).As γ maps at most a single point of dgm (2) i (A) to each point of dgm i (M), the number of such points is upper bounded by the number of points of the form (0, v 2 ) with v 2 ≥ wfs(M) in dgm i (M). Though dgm i (M) need not be finite (M is not assumed to be generic), applying Corollary 3.34 from [22] to d M shows that dgm i (M) is q-tame, and in particular that it contains only a finite number N of points (v 1 , v 2 ) with v 1 ≤ wfs(M)/4 and v 2 ≥ wfs(M)/2. Hence the cardinality of dgm = (u 1 , u 2 ) ∈ dgm (2) i (A), respectively u ′ ∈ dgm (3) i (A), then |u 2 -γ(u) 2 | ≤ Cε 2 , respectively ∥u ′ -γ(u ′ )∥ ∞ ≤ Cε 2 .To that end, remember first that as shown above, our starting optimal matching γ must be such that points in dgm EQUATIONi (M) ∪ ∂Ω. Now let R(M) be the radius of the smallest ball that contains M, and consider the functionsa : R d → R, x → min(max(d A (x), τ (M)/2), R(M)) and m : R d → R, x → min(max(d M (x), τ (M)/2), R(M)).Let us compare the persistence diagrams dgm i (a) and dgm i (m) of the sublevel sets filtration of a and m and the Čech persistence diagrams dgm i (A) and dgm i (M) respectively (which are by definition the persistence diagrams of the sublevel sets filtration of d A and d M ).Note first that d A and d M can have no critical values strictly greater than R(M), as a critical point must belong to the convex hull of its projections. Note also that for any t ∈ [τ (M)/2, R(M)], the sublevel set a -1 (-∞, t] is exactly equal to d -1 A (-∞, t] = A t . Consequently, dgm i (a) contains exactly two disjoint types of points. The first type are points of the form (τ (M)/2, u 2 ), which are in bijection with the points (u 1 , u 2 ) ∈ dgm i (A) with u 1 ≤ τ (M)/2 (the bijection maps (u 1 , u 2 ) → (τ (M)/2, u 2 )); those are exactly the points in dgm (2) i (A). The second type are points of the form (u 1 , u 2 ) with u 1 ≥ τ (M)/2, which are in trivial bijection (the bijection is the identity) with the points in dgm i (A) that satisfy the same condition; those are exactly the points of dgm i (A) cannot be "seen" in dgm i (a). We will call dgm Similarly, dgm i (m) contains two types of points: the first type are points of the form (τ (M)/2, v 2 ), which are in bijection with the points (0, v 2 ) ∈ dgm i (M) (the bijection maps (0, v 2 ) → (τ (M)/2, v 2 )); those are exactly the points in dgm (2) i (M). The second type are points of the form (v 1 , v 2 ) with v 1 ≥ τ (M)/2, which are in trivial bijection (the bijection is the identity) with the points in dgm i (M) that satisfy the same condition; those are exactly the points of dgm M (z) -d A (z)| ≤ ε 2 2d M (z) 1 + d M (z) τ (M) for any z ∈ R d \M. If z ∈ R d is such that d A (z) ≤ τ (M)/2, then a(z) = m(z) = τ (M)/2; if it is such that d M (z) ≥ R(M), then a(z) = m(z) = R(M). Otherwise, d M (z) ≥ d A (z)-d H (A, M) ≥ τ (M)/4 and d M (z) ≤ R(M), hence |d M (z) -d A (z)| ≤ ε 2 2d M (z) 1 + d M (z) τ (M) ≤ 2ε 2 τ (M) 1 + R(M) τ (M) = Cε 2 ,where C is as defined in the proposition. This means that ∥m -a∥ ∞ ≤ Cε 2 . Due to the Bottleneck Stability Theorem, the diagrams dgm i (a) and dgm i (m) must be at bottleneck distance less than Cε 2 . Furthermore, let δ denote max u∈dgm i (A)∪∂Ω ∥u -γ(u)∥ ∞ . The matching γ (and in particular the submatchings γ (2) and γ (3) ) also induces (through the correspondence detailed above between the points of dgm i (a) and a subset of the points of dgm i (A)) a matching γ ′ between dgm i (a) and dgm i (m) such that max u∈dgm i (a)∪∂Ω ∥u -γ ′ (u)∥ ∞ ≤ δ. Hence the bottleneck distance between dgm i (a) and dgm i (m) is at most min(δ, Cε 2 ).Let β : dgm i (a) ∪ ∂Ω → dgm i (m) ∪ ∂Ω be an optimal matching for the bottleneck distance. For similar reasons as for γ, the matching β can also be decomposed into two disjoint submatchings β (2) : dgm i (m) ∪ ∂Ω. We can use the two matchings β (2) and β (3) to define a new optimal matching γ : dgm i (A) ∪ ∂Ω → dgm i (M) ∪ ∂Ω as follows:• The points in dgm (1) i (A) are matched by γ to ∂Ω as with γ.• Given u = (u 1 , u 2 ) ∈ dgm (2) i (A), let u ′ = (τ (M)/2, u 2 ) be the point of dgm (2) i (a) with which u is in bijection. We let γ match u with the point v = (0, v 2 ) ∈ dgm (2) i (M) which is in bijection with β (2) (u ′ ) = (τ (M)/2, v 2 ) ∈ dgm (2) i (m). Then |u 2 -v 2 | ≤ min δ, Cε 2due to the optimality of β, and this defines a bijective matching γ(2) : dgm(2) i (A) → dgm (2) i (M). Note also that max u∈dgm (2) i (A) |u 1 -γ(2) (u) 1 | = max u∈dgm (2) i (A) u 1 = max u∈dgm (2) i (A) |u 1 -γ (2) (u) 1 |, hence max u∈dgm (2) i (A) ∥u -γ(2) (u)∥ ∞ ≤ δ.• We have seen that dgmEQUATIONi (A) and dgmEQUATIONi (M). We simply define the restriction and corestriction γ(3) : dgm(3) i (A) ∪ ∂Ω → dgm (3) i (M) ∪ ∂Ω of γ as being equal to β (3) : dgm (3) i (a) ∪ ∂Ω → dgm (3) i (m) ∪ ∂Ω. The optimality of β implies that max u∈dgm (3) i (A) ∥u -γ(u)∥ ∞ ≤ min δ, Cε 2 .Thus the global matching γ : dgm i (A) ∪ ∂Ω → dgm i (M) ∪ ∂Ω is well-defined, is optimal for the bottleneck distance, and satisfies the conditions stated in the proposition. This completes the proof.We prove Theorem 3.3, which we restate for the reader's convenience:Theorem 3.3. Let M ⊂ R d be a generic compact submanifold and A ⊂ M be a (δ, ε)-dense set in M for some ε, δ > 0. Let a ≥ ε/δ and let i ≥ 0 be an integer. There exist ε 0 > 0 depending only on M and C 0 , C 1 , C 2 , C 3 depending only on M and a such that if ε ≤ ε 0 , then dgmi (A) has at most C 0 points and for all p ≥ 1, α ≥ 0,EQUATIONProof. Let us first prove the bound on the cardinality of dgmi (A). As M is generic, Theorem 1.6 from [6] states that if ε is smaller than some ε 0 = ε 0 (M), then each point in Crit(A) at distance more than τ (M)/2 from A must be at distance at most K 1 ε from one of the finitely many points of Crit(M) for some K 1 = K 1 (M). Corollary 1.7 from the same article then states that the number of points in Crit(A) at distance less than K 1 ε from a given point of Crit(M) is upper bounded by some constant that depends on M and the ratio ε/δ, and is decreasing in this ratio; hence it is upper bounded by some constant that depends on M and a. The proof of this corollary also shows that the maximum number of projections on A of each of these points of Crit(A) is also upper bounded by some constant that depends on M and a. Hence there exist constants K 2 = K 2 (M, a) and K 3 = K 3 (M, a) such that if ε ≤ ε 0 , then there are at most K 2 points in Crit(A) at distance more than τ (M)/2 from A, and each has at most K 3 projections on A.Lemma E.1 below, applied to the interval [τ (M)/2, ∞) and the set A, then states that the number of points in dgm i (A) such that at least one of their coordinates is greater than τ (M)/2 is bounded by K 2 ( K3 i+1 + K3 i+2 ). Hence there are at mostEQUATIONi (A) when ε ≤ ε 0 . Now let us prove the bounds on OT p p (dgm i (A), dgm i (M)) and Pers α (dgm i (A)). As stated in Theorem 2.2, which applies as ε 0 < τ (M)/4, each point u = (u 1 , u 2 ) ∈ dgm (1) i (A) is such that its coordinates satisfy 0 ≤ u 1 , u 2 ≤ ε + ε 2 /τ (M) ≤ 2ε. In particular, they must correspond to the birth or the death of an interval of the Čech persistence module of A that occurs before filtration time 2ε. The homology of the offsets A t can be computed using the Čech simplicial complex of A (see e.g. [37] ). In particular, each change in the homology of the offsets, hence each birth or death in the Čech persistence module of A, is induced by the apparition of some simplex σ at the corresponding filtration value in the Čech complex, and each such apparition causes at most a single death or birth. If a simplex σ appears before filtration time 2ε, it is by definition contained in a ball of radius 2ε, hence it is of diameter at most 4ε. Let us assume from now on that ε 0 ≤ τ (M)/16. Consider x ∈ A; then [2, Proposition 8.7] states that the intersection B(x, 4ε) ∩ A contains at most K 4 (ε/δ) m ≤ K 4 a m points for some constant K 4 = K 4 (M). Hence x belongs to at most 2 K4a m simplices that appear before ε, and there are at most #A • 2 K4a m such simplices. As the cardinality #A can be bounded by K 5 /δ m for some K 5 = K 5 (M), we find that #(dgm(1) i (A)) ≤ K 6 /δ m for some K 6 = K 6 (M, a).Furthermore, when M is generic, Proposition 3.2 states that its PD dgm i (M) has a finite number of points. Let γ be an optimal matching between dgm i (A) and dgm i (M) for the bottleneck distance that satisfies the conclusions of Theorem 2.2. We find that any point u ∈ dgm (1) i (A) is matched to a point of ∂Ω at distance at most ε from u. Moreover, the number of points in dgm(2) i (A) ∪ dgm (3) i (A)is bounded by some constant K 7 = K 7 (M, a), and they are all matched to a point of dgm i (M) or ∂Ω at distance at most ε. In particular, these finitely many points are at distance at most K 8 = K 8 (M) from ∂Ω. Furthermore, this matching is surjective, in the sense that γ matches all points of dgm i (M) to a point of dgm i (A). As a result, for any p ≥ 1, we find thatOT p p (dgm i (A), dgm i (M)) ≤ u∈dgm (1) i (A) ∥u -γ(u)∥ p ∞ + u∈dgm (2) i (A)∪dgm (3) i (A) ∥u -γ(u)∥ p ∞ ≤ K 6 δ -m ε p + K 7 ε p ≤ K 6 a m ε p-m + K 7 ε p ≤ C 1 ε p-mfor some C 1 = C 1 (M, a). Likewise, for any α ≥ 0, we have that As shown in [5] , if z is of critical index i, then the linear span Span(σ A (z) -z) is of dimension i. By Carathéodory's theorem, there exists i + 1 affinely independent points in σ A (z) ⊂ z ′ ∈Cj σ A (z ′ ) such that z belongs to their convex hull. Those i + 1 points uniquely identify z among the critical points of A, as it is the only point equidistant to them that belongs to their convex hull. Hence there is an injection from the topological critical points of A of index i that belong to C j into the set of subsets of cardinality i + 1 of z ′ ∈Cj σ A (z ′ ). Applying the same reasoning to the points of index i + 1, we find that there are at most Pers α (dgm i (A)) = u∈dgm (1) i (A) pers(u) α + u∈dgm (2) i (A)∪dgm (3) i (A) pers(u) α ≤ K 6 δ -m ε α + K 7 K α 8 ≤ K 6 a m ε α-m + K 7 K α 8 ≤ C 2 (C α 3 + ε α-m ) for some C 2 = C 2 (M, a), C 3 = C 3 (M).Let M denote the space of Radon measures on Ω, and let us defineEQUATION)For p ∈ [1, +∞), we defineEQUATIONwhere ∥u∥ ∞ = max(|u 1 |, |u 2 |) and Adm(ν 1 , ν 2 ) is the set of all admissible transport plans between ν 1 and ν 2 . We also defineEQUATION)For all p ∈ [1, ∞], the infimum is in fact a minimum (see [33] ). We call OT p (ν 1 , ν 2 ) the p-Wasserstein distance between ν 1 and ν 2 , though it differs from the usual Wasserstein distance, which is defined between measures with equal finite mass, while OT p is defined between measures that can have different (and even infinite) masses. Intuitively, OT p allows for some of the mass of ν 1 and ν 2 to be transported to the diagonal ∂Ω := {(u, u) ∈ R 2 }, which acts as an infinitely deep landfill. The p-Wasserstein distance is a distance on the space M p = {ν ∈ M : OT p (ν, 0) < ∞}, where 0 denotes the null measure.As explained in Section 4, a PD a can be identified with the Radon measure u∈a δ u . Let D p be the set of PDs being in M p . Then, Divol and Lacombe show in [33] that the OT p distance defined in (18) coincides with the OT p distance defined between PDs in Equation ( 3), and likewise for the case p = ∞.We require the following lemma from [33] : Lemma F. We start with the proof Theorem 4.1, which is split into a series of lemmas, before proving Proposition 4.2, Corollary 4.3 and Corollary 4.4.Let us restate Theorem 4.1 for the reader's convenience: Theorem 4.1 (Law of large numbers). Assume that P has a density f on M bounded away from 0 and ∞. Let i ≥ 0 be an integer and let1 ≤ p < ∞. Then µ f,i ∈ M p and E[OT p p (µ n,i , µ f,i )] ----→ n→∞ 0.Furthermore, for all α > 0, Pers α (dgm(1) i (A n ))n α m -1 = Pers α (µ n,i ) = Pers α (µ f,i ) + o L 1 (1).Before proving Theorem 4.1, we state a simple lemma which allows us to control the mass of balls on M. Lemma G.1. Let M be a compact submanifold with positive reach. Let P be a probability measure having a density f on M satisfying f min ≤ f ≤ f max for two strictly positive constants f min , f max . There exist constants c m , C m depending only on m such that for all 0 ≤ r ≤ τ (M)/4EQUATION)Let A n be a sample of n i.i.d. observations of law P . Then, there exists C = C(M) depending on M such that for all x ∈ M and all r > 0,EQUATIONProof. For the first statement, see [2, Proposition 31] . Let us prove the second one. Remark that the probability is zero for r > diam(M). Hence, we can assume that r ≤ diam(M). When r ≤ τ (M)/4, it holds thatP(d(x, A n ) ≥ r) = (1 -P (B(x, r))) n ≤ exp(-nc m f min r m ).When τ (M)/4 ≤ r ≤ diam(M), we writeP(d(x, A n ) ≥ r) ≤ P(d(x, A n ) ≥ τ (M)/4) ≤ exp(-nc m f min (τ (M)/4) m ) ≤ exp(-nc m f min (τ (M)/4) m diam(M) m r m ).Hence, the result holds with C = c m min 1, (τ (M)/4) m diam(M) m .Proof of Theorem 4.1. Recall that Goel, Trinh and Tsunoda [42] have shown that almost surely, the sequence of Radon measures (µ n,i ) n vaguely converges to the Radon measure µ f,i . We start by showing that, using this vague convergence and Lemma F. Proof. Let us first show that (D n ) n≥1 = (OT p p (ν n , ν)) n≥1 converges in probability to 0. We use the following standard result: if for every subsequence (Z n k ) k≥1 of (Z n ) n≥1 , one can extract a subsequence (Z n k l ) l≥1 that converges almost surely to 0, then the sequence (Z n ) n≥1 converges in probability to 0. Let (D n k ) k≥1 be a subsequence of (D n ) n≥1 = (OT p p (ν n , ν)) n≥1 . Then, as (Pers p (ν n )) n≥1 converges in L 1 to Pers p (ν), it also converges in probability. In particular, there exists a subsequence (n k l ) l≥1 such that (Pers p (ν n k l )) n≥1 converges almost surely to Pers p (ν). When restricting ourselves to this subsequence, we have both vague convergence of the measures and convergence of the p-total persistence. Hence, according to Lemma F.1, we have D n k l = OT p p (ν n k l , ν) → l→∞ 0 almost surely, proving that we actually have that (D n ) n≥1 converges in probability to 0. To prove that E[D n ] → n→∞ 0, it remains to show that the sequence (D n ) n≥1 is uniformly integrable. By considering the trivial transport plan that sends all probability mass to ∂Ω, we have for all n ≥ 1D n ≤ Pers p (ν n ) + Pers p (ν).But the sequence (Pers p (ν n )) n≥1 is uniformly integrable, as it converges in L 1 . Hence, so is the sequence (D n ) n≥1 , concluding the proof.Using Lemma G.2, Theorem 4.1 would follow from the facts that µ f,i ∈ M p and thatE[|Pers p (µ n,i ) -Pers p (µ f,i )|] converges to 0. Recall that C c (Ω)is the set of continuous functions f : Ω → R with compact support (i.e. the support is bounded and at positive distance from ∂Ω). For s ≥ 0, let Proof. We divide the proof into several steps.T s = {(u 1 , u 2 ) ∈ Ω : u 2 ≥ s}. Lemma G.3. Let α > 0. Let (ν n ) n≥11. Let ϕ ∈ C c (Ω). We first show that ( ϕdν n )) n≥1 converges in L 1 to ϕdν. By assumption, the convergence holds almost surely. Furthermore, as ϕ is bounded and as the sequence (ν n (Ω)) n≥1 is uniformly integrable, so is the sequence( ϕdν n ) n≥1 . Hence, E[| ϕd(ν n - ν)|] → n→∞ 0.2. Let (ϕ k ) k≥1 be an increasing sequence of functions in C c (Ω) that converge pointwise to the function pers α . Then, almost surely,ϕ k dν ≤ lim inf n→∞ ϕ k dν n ≤ lim inf n→∞ pers α dν n . By Fatou's lemma, E[lim inf n→∞ pers α dν n ] ≤ lim inf n→∞ E[Pers α (ν n )] = C < +∞by assumption. Hence, by letting k → ∞ and applying the monotone convergence theorem, we obtain Pers α (ν) ≤ C, proving that ν ∈ M α .3. The same argument can be applied to the constant function equal to 1, showing that ν(Ω) < +∞.Let s ≥ 1. The function pers α can be decomposed into a sum of three positive continuous functions pers α = ϕs + ϕs , where ϕs has compact support, the support of ϕ(2) s is included in the band {u ∈ Ω : pers(u) ≤ 1/s} and the support of ϕs is included in T s . Hence,lim sup n→+∞ E[|Pers α (ν n ) -Pers α (ν)|] ≤ lim sup n→+∞ E[| ϕ (1) s d(ν n -ν)|] + lim sup n→+∞ E[| ϕ (2) s d(ν n -ν)|] + lim sup n→+∞ E[| ϕ (3) s d(ν n -ν)|].The first term in the above sum is equal to zero because of the first item, the second one is smaller than s -α (sup n E[ν n (Ω)] + ν(Ω)), and the third one is smaller thanlim sup n E[ Ts pers α (u)dν n (u)] + Ts pers α (u)dν(u).Using the hypotheses of the lemma, the second and the third term converges to 0 as s goes to ∞. We obtain that limsup n→+∞ E[|Pers α (ν n ) -Pers α (ν)|] = 0.Our goal is to show that the conditions of Lemma G.3 holds for the sequence (µ n,i ) n≥1 to conclude. Remark that for any Radon measure ν ∈ M α and s ≥ 0EQUATIONwhere we use Fubini's theorem for the first equality and the fact that {u : pers(u) ≥ t} ⊂ T 2t for the first inequality. We also have ν(Ω) = ν(T 0 ). Hence, the different conditions of Lemma G.3 can all be obtained by controlling the random variable µ n,i (T s ) for s ≥ 0.Proposition G.4. Let M be a compact submanifold with positive reach. Assume that P has a density f on M satisfying f min ≤ f ≤ f max for two positive constants f min , f max . Then there exist c, C > 0 that depend on M, i, f min and f max such that for all integer n ≥ 1 and all s ≥ 0,EQUATIONBefore proving Proposition G.4, let us show how to use it to conclude the proof of Theorem 4.1. First, it implies that the random variables µ n,i (Ω) = µ n,i (T 0 ) for n ≥ 1 have a uniformly bounded second moment, and are therefore uniformly integrable. Second, we haveE[µ n,i (T s )] ≤ E[µ n,i (T s ) 2 ] 1/2using Hölder's inequality. Hence, (22) implies that for any α > 0, we haveE[Pers α (µ n,i )] ≤ α ∞ 0 t α-1 E[µ n,i (T 2t )]dt ≤ α √ C ∞ 0 t α-1 e -c2 m-1 t m dt.In particular,sup n E[Pers α (µ n,i )] < +∞. Likewise, sup n E Ts pers α (u)dµ n,i (u) ≤ α ∞ s/2 t α-1 E[µ n,i (T 2t )]dt + (s/2) α E [µ n,i (T s )] ≤ α √ C ∞ 0 t α-1 e -c2 m-1 t m dt + (s/2) α √ C exp(-c/2s m )so that lim s→+∞ sup n E[ Ts pers α (u)dµ n,i (u)] = 0. We are therefore in position to apply Lemma G.3, proving the convergence of the α-total persistence. Together with Lemma G.2 with α = p ≥ 1, we also obtain the OT p -convergence of µ n,i . It remains to prove Proposition G.4.One can show that the set Ξ j n,s is localized, in the sense that it is included in a ball centered at X j , with a radius depending on the sample A n , that is small with high probability. Hence, the number L j is controlled by the number of points in A n found in a small (random) neighborhood of X j . Let us make this idea rigorous.For r ≥ 0, define the shapeEQUATIONWe build a partition of C(r) in the following way. Consider a finite partition W of the unit sphere in R m × {0} d-m into sets of diameters smaller than θ = π/4 (for the geodesic distance on the sphere), which we fix for a given dimension m. Let W(r) be the partition of C(r) consisting of the sets{y = (y m , y d-m ) ∈ C(r) : y m /∥y m ∥ ∈ W },where W is an element of the partition W.For x ∈ M, consider an isometryι x : R d → R d sending R m × {0} d-m to T x M. Let C(x, r) = x + ι x (C(r)). Likewise, we define a partition W(x, r) by applying the affine transformation W → x + ι x (W ) to each W ∈ W(r).For j = 1, . . . , n, let R jn be the smallest radius r ≤ ε 0 such that every W ∈ W(X j , r) contains a point of A n other than X j . By convention, we let R jn = ε 0 if such a radius does not exist. R jn can be made measurable with a good choice of x → ι x ; we assume it to be the case henceforth.Lemma G.7. Let ε 0 ≤ τ (M)/ √ 2. For all j = 1, . . . , n, if z ∈ Crit(A n ) is such that X j ∈ σ An (z) and d An (z) ≤ ε 0 , then ∥X j -z∥ ≤ c 0 R jn for some positive absolute constant c 0 .Proof. Recall that for x ∈ M, π x is the orthogonal projection on T x M while π ⊥x is the orthogonal projection on the normal space at x. Let j = 1, . . . , n and let z ∈ Crit(A n ) be such that X j ∈ σ An (z).The direction e = π Xj (z -X j )/∥π Xj (z -X j )∥ belongs to the unit sphere in T Xj M; note that π Xj (z -X j ) ̸ = 0 due to Lemma G.8 below, which applies as d An (z) ≤ ε 0 ≤ τ (M)/ √ 2. Hence, ι -1 x (e) belongs to an element W 0 of the partition W. Consider the corresponding element W of the partition W(X j , R jn ).If R jn = ε 0 , then the conclusion of the lemma holds (for c 0 = 1): indeed we have ∥X j -z∥ = d An (z) ≤ ε 0 ≤ R jn . Otherwise, by assumption, there exists a point X k ∈ W for some k ̸ = j. As X j ∈ σ An (z), it holds that ∥X j -z∥ ≤ ∥X k -z∥. Hence,EQUATION)We write⟨X k -X j , z -X j ⟩ = ⟨π Xj (X k -X j ), π Xj (z -X j )⟩ + ⟨π ⊥ Xj (X k -X j ), π ⊥ Xj (z -X j )⟩By construction, as the diameter of W 0 is less than θ, we have ⟨π Xj (X k -X j ), π Xj (z -X j )⟩ ≥ cos(π/4)∥π Xj (X k -X j )∥∥π Xj (z -X j )∥. On the other hand, according to [39, Theorem 4.18] ,EQUATIONwhich also implies that ∥πXj (X k -X j )∥ ≥ ∥X j -X k ∥ 1 - ε 2 0 4τ (M) 2 . Similarly, Lemma G.8 below states that ∥π Xj (z -X j )∥ ≥ ∥z -X j ∥/ √ 2 and ∥π ⊥ Xj (z -X j )∥ ≤ ∥z -X j ∥ 2 /τ (M) (using our assumption that d An (z) ≤ ε 0 ≤ τ (M)/ √ 2).Hence we obtain thatcos(π/4)∥X j -X k ∥∥z -X j ∥ 1 - ε 2 0 4τ (M) 2 √ 2 ≤ cos(π/4)∥π Xj (X k -X j )∥∥π Xj (z -X j )∥ ≤ ∥X k -X j ∥ 2 2 + ∥X k -X j ∥ 2 ∥z -X j ∥ 2 2τ (M) 2 ≤ ∥X k -X j ∥ 2 1 2 + ε 2 0 2τ (M) 2 .Dividing by ∥X j -X k ∥ and using that ∥X j -X k ∥ ≤ R jn and that ε 0 ≤ τ (M)/ √ 2, we see that ∥z -X j ∥ is smaller than R jn up to an absolute multiplicative constant.We now prove the lemma used above:Lemma G.8. Let A ⊂ M, z ∈ Crit(A) and x ∈ σ A (z). Then ∥π ⊥ x (z -x)∥ ≤ ∥z -x∥ 2 /τ (M). Furthermore, if d A (z) ≤ τ (M )/ √ 2, then ∥π x (z -x)∥ ≥ ∥z -x∥/ √ 2.Proof. The point z can be written as a convex combination z = k λ k y k where the points y k are in A ⊂ M. Then, using [39, Theorem 4.18] ,∥π ⊥ x (z -x)∥ ≤ k λ k ∥π ⊥ x (y k -x)∥ ≤ k λ k ∥y k -x∥ 2 2τ (M) = k λ k ∥y k -z∥ 2 + ∥z -x∥ 2 + 2⟨y k -z, z -x⟩ 2τ (M) = ∥z -x∥ 2 τ (M) ,as ∥y k -z∥ 2 = ∥x-z∥ 2 and k λ k (y k -z) = 0. The second inequality ∥π x (z ≥ ∥z -x∥/ √ 2 from the statement follows from the first one through a direct computation.Let us now show that the random variable R jn has controlled tails. Lemma G.9. For all x ∈ M, r ≥ 0, B(x, r) ∩ M ⊂ C(x, r).Proof. Let y ∈ M be such that ∥π x (y -x)∥ ≤ r. Then, according to [39, Theorem 4.18] , ∥π ⊥x (yx)∥ ≤ ∥y-x∥ 2 2τ (M) . In particular, B(x, r) ∩ M ⊂ C(x, r).Lemma G.10. For 0 < t ≤ τ (M)/4 and j = 1, . . . , n, we have P(R jn > t) ≤ C m e -cmfmin(n-1)t m for some positive constants c m , C m .Proof. If R jn is larger than t, then there exists at least one set W ∈ W(X j , t) such that its intersection with A n contains only X j . Hence,P(R jn > t|X j ) ≤ W ∈W(Xj ,t) P(A n ∩ W = X j |X j ) = W ∈W(Xj ,t) (1 -P (W )) n-1 .Let π 0 be the orthogonal projection from R d to R m × {0} d-m . The image of a set W ∈ W(X j , t) by the projection y → π Xj (y -X j ) is equal to ι Xj (π 0 (W 0 )) ⊂ T Xj M for some W 0 ∈ W(t).For t ≤ τ (M)/4, the orthogonal projection y ∈ B(X j , t) ∩ M → π Xj (y -X j ) ∈ T Xj M is a diffeomorphism on its image, with Jacobian lower bounded by a constant c m that depends only on m, see e.g. [31, Lemma 2.2] . According to Lemma G.9, the preimage of ι Xj (π 0 (W 0 )) ⊂ T Xj M by this diffeomorphism is equal to W ∩ M . Hence, by a change of variable,P (W ) = P (W ∩ M ) ≥ f min c m Vol m (W 0 ) ≥ f min c ′ m t m for some c ′ m > 0. Hence, P(R jn > t|X j ) ≤ #We -fminc ′ m (n-1)t m .We conclude by taking the expectation.Let us now control the number of points found in a ball B(X j , κR jn ) for some κ ≥ 0. Let ρ 0 > 0 be small enough such that B(x,ρ0)∩M f < 1/2 for any x ∈ M.Lemma G.11. Let l ≥ 0, κ > 0 be such that κε 0 ≤ min(ρ 0 , τ (M)/4). For j = 1, . . . , n, let K jn (κ)be the number of elements of A n found in B(X j , κR jn ). Then, E[K jn (κ) l ] ≤ C m,l (1+ fmax fmin l κ lm ) for some constant C m,l which depends on m and l.Proof. Let us write {W 1 , . . . , W K } = W(X j , κR jn ). Without loss of generality, we can assume that n ≥ K + 1, as otherwise the bound is trivial. As in [34, Lemma 5] , we remark that there is at least one sample point in every W i , and that there is (almost surely) one single element W i * of the partition with exactly one sample point on its boundary. Let N i be the cardinality of (W i ∩ A n )\{X j }, and N -1 be the cardinality of A n \B(X j , κR jn ). Define αi := Wi f and α i := αi 1-αi * for all i ̸ = i * , as well asα -1 = 1-K i=1 αi 1-αi *. Note that as κR jn ≤ ρ 0 , we have αi < 1/2 for all i = 1, . . . , K. As κR jn ≤ κε 0 ≤ τ (M)/4, we may use once again that the orthogonal projection y ∈ B(X j , κR jn ) ∩ M → π Xj (y -X j ) ∈ T Xj M is a diffeomorphism on its image, with Jacobian upper and lower bounded by constants depending only on m (see [31, Lemma 2.2] ) to also obtain that cf min (κR jn ) m ≤ αi ≤ Cf max (κR jn ) m for all i = 1, . . . , K and some constants c = c(m), C = C(m). Hence there existsC ′ = C ′ (m) > 0 such that cf min (κR jn ) m ≤ α i ≤ C ′ f max (κR jn ) mfor all i = 1, . . . , K. Consider a multinomial random variable L = (L 1 , . . . , L i * , . . . , L K , L -1 ) of parameters n -2 and (α 1 , . . . , α i * , . . . , α K , α -1 ), and let E denote the event{L i ≥ 1 ∀i ∈ {1, . . . , K}\{i * }}.Then conditionally on X j , R jn and i * , the variable N = (N 1 , . . . , N i * , . . . , N K , N -1 ) follows the same distribution as L | E. Thus, conditionally on X j , R jn and W i * , the variable K jn (κ) = 1 + K i=1 N i = 2 + K i=1,i̸ =i * N i (where the initial 1 comes from X j ) has the same distribution as2 + K i=1,i̸ =i * L i | E.Note that as κR jn ≤ ρ 0 , we have α -1 ≥ 1/2.As a result, Lemma G.12 below yields thatE[K jn (κ) l |X j , R jn , W i * ] = E[(2 + K i=1,i̸ =i * L i ) l | E] ≤ 2 l (2 l + E[( K i=1,i̸ =i * L i ) l | E]) ≤ 2 l (2 l + C K,l (1 + (n -2) K i=1,i̸ =i * α i ) l ) ≤ C ′ K,l (1 + (n K i=1,i̸ =i * α i ) l ) ≤ C ′ K,l (1 + (nKC ′ f max (κR jn ) m ) l ) ≤ C m,l (1 + κ ml f l max n l R ml jn )where C K,l , C ′ K,l and C m,l are constants whose dependencies are indicated by their indices (remember that K = #W depends only on m). We can now conclude by consideringE[K jn (κ) l ] = E Xj ,Rjn,W i * [E[K jn (κ) l |X j , R jn , W i * ]] ≤ E Rjn [C m,l (1 + κ ml f l max n l R ml jn )]The quantity n l E[R ml jn ] is bounded by a constant, which is proved by integrating the tail bound found in Lemma G.10. Indeed, Lemma G.10 implies that the random variable nR m jn is subexponential with a subexponential norm m independent of n, of order O(1/f min ); the moment of order l of such a random variable is bounded by C l m l , see [74, Section 2.7] .Let us now prove the technical lemma used above.Lemma G.12. Let K ≥ 1 and L = (L 1 , . . . , L K , L K+1 ) be a random multinomial variable of parameters n and α 1 , . . . , α K , α K+1 . Then there exists C = C(K, l) such thatE[( K i=1 L i ) l |L i ≥ 1 ∀i = 1, . . . , K] ≤ C l (1 + (n K i=1 α i ) l ).Proof. Let X 1 , . . . , X n be i.i.d. categorical variables of parameters α 1 , . . . , α K , α K+1 . Define L k (p) = r≤p 1 Xr=k ; then (L 1 (n), . . . , L K (n), L K+1 (n)) has the same distribution as (L 1 , . . . , L K , L K+1 ), and we identify the two in our notations. For a fixed n, and for any injective function ι : {1, . . . , k} → {1, . . . , n}, consider the eventE ι {L 1 (ι(1)) = 1, . . . , L 1 (ι(K)) = 1},i.e. ι(i) is the first appearance of i among the variables X 1 , . . . , X n . Note that E := {L 1 , . . . , L K ≥ 1} = ι E ι where the sum is taken over all such injective functions. ThenE[( K i=1 L i ) l |E] = ι P(E ι |E)E[( K i=1 L i ) l |E ι ].Fix a function ι, and assume without loss of generality that ι(1) < ι(2) < . . . < ι(K). Conditioned by A ι , the variableY i := ι(i+1)-1 r=ι(i)+1 1 Xr̸ =K+1 is a binomial variable of parameters ι(i+1)-ι(i)-2 ≤ n and i i=1 αi α1+...+αi+α K+1 ≤ K i=1 α i . Hence E[Y l i |E ι ] ≤ C 1 (l)(n K i=1 α i) l using classical bounds on the l-th moment of a binomial variable, and we see thatE[( K i=1 L i ) l |E ι ] = E[( n r=1 1 Xr̸ =K+1 ) l |E ι ] = E[(K + K i=0 ι(i+1)-1 r=ι(i)+1 1 Xr̸ =K+1 ) l |E ι ] ≤ C 2 (K, l)(K l + K i=0 E[Y l i |E ι ]) ≤ C 3 (K, l)(1 + (n K i=1 α i ) l )where we write ι(0) = 0 and ι(K + 1) = n to simplify notations.Let us wrap things up. Recall Lemma G.6: it holds thatEQUATIONwhere L j is the cardinality of the set z∈Ξ j n,s σ An (z). But according to Lemma G.7, if z ∈ Ξ j n,s , then ∥X j -z∥ ≤ c 0 R jn . In particular, d An (z) ≤ c 0 R jn , and any point y ∈ σ An (z) is at distance less than 2c 0 R jn from X j . Hence, L j is smaller than K jn (κ) for κ = 2c 0 . Choose ε 0 so that κε 0 ≤ κε 0 ≤ min(ρ 0 , τ (M)/4). We are in position to apply Lemma G.11. We further remark that Lemma G.7 implies that Ξ j n,s is empty if c 0 R jn < sn -1/m . Hence, by Jensen's inequality,E[µ n,i (T s ) 2 1{E}] ≤ E      1 n n j=1 1{2c 0 R jn ≥ sn -1/m }K jn (2c 0 ) i+2   2    ≤ E 1{2c 0 R 1n ≥ sn -1/m }K 1n (2c 0 ) 2i+4 ≤ P(2c 0 R jn ≥ sn -1/m )E[K 1n (2c 0 ) 4i+8 ] ≤ C m,i exp(-c m f min s m )for some constants c m , C m,i > 0, where we apply Lemma G.10 and Lemma G.11 at the last line.This completes the proof of Theorem 4.1.We now prove Proposition 4.2: Proposition 4.2. Let M be a generic m-dimensional submanifold. Assume that P has a density f on M bounded away from 0 and ∞. Let i ≥ 0 be an integer. There exists an optimal matching γ n : dgm i (A n )∪∂Ω → dgm i (M)∪∂Ω for the bottleneck distance between dgm i (A n ) and dgm i (M) such that for any q ≥ 1:• Region (2): It holds that max u∈dgm (2) i (An) |u 2 -γ n (u) 2 | = O L q (n -2/m ). • Region (3): It holds that max u∈dgm (3) i (An) ∥u -γ n (u)∥ ∞ = O L q (n -2/m) and #(dgm(3) i (A n )) = O L q (1). Proof. Let ε n = d H (A n , M). Let Π M := {x ∈ σ M (z) : z ∈ Crit(M)} be the (finite) set of projections of critical points z ∈ Crit(M). The proof of Theorem 3.3 relied on the use of Theorem 1.6 in [6] . This theorem states roughly that both critical points z ∈ Crit(A n ) far from M and their projections x ∈ σ An (z) are stable with respect to the Hausdorff distance, meaning that every such point z is at distance O(ε n ) from a critical point z ′ ∈ Crit(M), with x being at distance O(ε n ) from a point x ′ ∈ Π M . Thus, the number of critical points of A n located close to a given z ′ ∈ Crit(M) is crudely upper bounded by the number of subsets which can be formed by selecting elements in neighborhoods of size O(ε n ) around x ′ ∈ σ M (z ′ ). We used the same idea to bound the cardinality of dgm In a random setting, the distance ε n is of order (ln n/n) 1/m , as suggested by Lemma G.5, while the number of points found in a ball of radius r is typically of order nr m , yielding a logarithmic number of elements in a neighborhood of size O(ε n ) around a given point x ∈ M. Hence, our earlier strategy is not tight enough to bound in expectation the cardinality of dgm (3) i (A) by a constant. We improve upon this strategy with the following intuition: the maximal distance between a point x of M and the point cloud A n does not really matter in [6, Theorem 1.6], but only the density of the point cloud A n around the (finitely many) projections x ∈ Π M . Although ε n is of order (ln n/n) 1/m , the distance between a fixed point x ∈ M and A n is known to be of order n -1/m (see (21) ). This remark explains how we can intuitively replace neighborhoods of radii (ln n/n) 1/m by radii of size n -1/m in the previous arguments.We now make these ideas rigorous. Let Crit > (A n ) = {z ∈ Crit(A n ) : d An (z) ≥ τ (M)/2} denote the set of critical points of A n "far" from M and let Π An := {x ∈ σ An (z) : z ∈ Crit > (A n )} be the corresponding set of projections. We let ε 0 be a small constant to be fixed later. Theorem 1.6 from [6] states that, thanks to the genericity of M, there exist K 1 , K 2 > 0 such that for ε 0 small enough, if ε n < ε 0 :• there exists a map ϕ : CritEQUATION• there exists a map ψ : Π An → Π M such that d(x, ψ(x)) ≤ K 2 ε n for all x ∈ Π An .Furthermore, the map ψ is such that for each z ∈ Crit > (A n ) and each x ′ ∈ σ M (ϕ(z)), there exists x ∈ σ An (z) such that ψ(x) = x ′ (if ε 0 is chosen small enough). Indeed, due to the genericity of M, each critical point z ′ ∈ Crit(M) belongs to the relative interior of σ M (z ′ ) (as stated in Appendix C). In particular, it cannot belong to the convex hull of any strict subset of σ M (z ′ ). By continuity of the convex hull for the Hausdorff distance, as soon as z ∈ Crit > (A n ) is close enough to ϕ(z) and its projections x ∈ σ An (z) are close enough to σ M (ϕ(z)) (i.e. as soon as ε n is small enough), the point z cannot belong to the convex hull of any subset S ⊂ σ An (z) that does not contain for each x ′ ∈ σ M (ϕ(z)) at least one point x such that ψ(x) = x ′ . As z must belong to the convex hull of σ An (z), we conclude that each x ′ ∈ σ M (ϕ(z)) has at least one preimage by ψ in σ An (z). As Crit(M) is finite, taking the minimum distance such that this property holds for z ′ over all z ′ ∈ Crit(M) proves the claim.We introduce the random function defined as ∀r ≥ 0, E(r) := min(sup{d An (y) :EQUATIONwhere Π r M is as usual the r-offset of Π M . This random variable measures the density of the point cloud A n in neighborhoods of size r of points x ′ ∈ Π M .ρ n := sup{d Π M (x) : x ∈ Π An } (31) give (when ε n < ε 0 for ε 0 small enough) the largest distance between a projection x ∈ Π An and the corresponding projection ψ(x) ∈ Π M . We also defineEQUATIONWe require the following controls on the random variables ρ n and η n .Lemma G.13. There exist positive constantsEQUATIONEQUATIONEQUATIONProof. The lemma follows from a careful read of the proof of Theorem 1.6 in [6] . First, remark that in the proof of Lemma 5.1 in [6] (applied with r = τ (M)/2, R = diam(M)), the Hausdorff distance ε = d H (A n , M) can be replaced by E(η n ). Hence, if z ∈ Crit > (A n ), there exists a µ-critical point z ′ of M at distance less than E(η n ), with µ ≤ L 1 (M)E(η n ). By genericity, for a choice of ε 0 small enough, this point z ′ is at distance L 2 (M)µ from a critical point z 0 ∈ Crit(M). For ε 0 small enough, this point z 0 is necessarily equal to ϕ(z), with ∥z -ϕ(z)∥ ≤ (1 + L 2 L 1 )E(η n ). Due to the Lipschitz property of the projection onto M around z 0 (see the arguments found at the bottom of p. 19 in [6] ), any point x ∈ π M (z) is such that ∥x -x ′ ∥ ≤ L 3 (M)∥z -ϕ(z)∥ for some x ′ ∈ σ M (ϕ(z)). By taking the supremum over all such points x, we obtain thatEQUATIONOne can also check that ε n can be replaced by E(η n ) in the end of the proof of Theorem 1.6 in [6] , so that (35) holds.Let us now prove (33) . Let z ∈ Crit > (A n ). Consider x An ∈ σ An (z); we know that ∥ψ(x An )x An ∥ ≤ K 5 E(η n ) using (33) . As ϕ(z) -ψ(x An ) is orthogonal to T ψ(x An ) M, [39] states that∥π ⊥ ψ(x An ) (x An -ψ(x An ))∥ ≤ ∥x An -ψ(x An )∥ 2 2τ (M) ≤ K 2 5 E(ηn) 2 2τ (M) , hence ∥ϕ(z) -x An ∥ 2 = ∥ϕ(z) -ψ(x An )∥ 2 + 2⟨ϕ(z) -ψ(x An ), ψ(x An ) -x An ⟩ + ∥ψ(x An ) -x An ∥ 2 ≤ d M (ϕ(z)) 2 + K 2 5 E(η n ) 2 τ (M) d M (ϕ(z)) + K 2 5 E(η n ) 2 ≤ d M (ϕ(z)) 2 + E(η n ) 2 L 4 ,whereL 4 = K 2 5 R(M) τ (M) + 1 , R(M)is the radius of the smallest closed ball that contains M, and d M (ϕ(z)) ≤ R(M) because a critical point must belong to the convex hull of its projections. AsThe determinant of the two first rows is equal to SU , and is therefore only equal to 0 if U = 0. But in that case,EQUATIONis a rank 2 matrix. Indeed, note that U is equal to the dot product of e θ = (-sin(θ), cos(θ)) with the (nonzero) vector (r, ∂ θ r). Hence, if U = 0, then the dot product of (r, ∂ θ r) with the vector (cos(θ), sin(θ)) (that is perpendicular to e θ ) is nonzero. Furthermore, one of the two top entries in the second column is also nonzero. Indeed, this is clear if ∂ ϕ r = 0 or if sin(ϕ) = 0 (we have S > 0 by assumption). Otherwise, having the two entries equal to zero would imply that S 2 = -(∂ ϕ r) cos 2 (θ), a contradiction.In all cases, d F (θ, ϕ) is of maximal rank. This implies the conclusion.Let R = 2.4, r = 0.8, σ = 2 and K = 30. We create a random torus by sampling of angles Y = {y 1 , . . . , y K } uniformly at random, conditioned on the fact that max y∈[0,2π] 2 d Y (y) < σ. We then draw the numbers a 1 , . . . , a K as exponential random variables of scale 0.5, conditioned on the fact that max ϕ∈[0,2π] r(ϕ) < R -r. We let M be the image of [0, 2π] 2 by F . Although we do not rigorously prove that the manifold M is almost surely generic, we conjecture that it is the case.A probability measure on P on M is obtained in the following way. Sample (θ, ϕ) ∈ [0, 2π] 2 so that F (θ, ϕ) is uniform on the torus. Then, let x = F (θ, ϕ). To put it another way, P is the pushforward of the uniform measure on the torus by F • F -1 .We sample n = 10 4 points according to P , and compute the Čech PDs of the corresponding set A n . For i = 1, we plot the persistence images with weights pers p , p = 0, 1, 2, 4, with both birth and persistence values ranging between 0 and 1, and grid step equal to 0.002. See Figure 4 .Convergence of the total persistences. We run three experiments. First, we compute the Čech PD for i = 0 of n uniform points on a (nongeneric) circle. Second, we compute the Čech PD for i = 0 of n uniform points on a (nongeneric) torus. Third, we compute the Čech PD for i = 1 of n uniform points on a (nongeneric) torus. Each experiment is ran for values of n ranging from n = 10 2 to n = 10 4 . We observe in Figure 5 the convergence rate of the total persistence of dgmi (A n ) predicted by Theorem 4.1. We then repeat each experiment 10 times, with similar rates of convergence observed for each run, although with a large relative standard deviation (around 30%) for very small values of Pers p (dgm (1) i (A n )) (the relative standard deviation being defined by the ratio between the standard deviation and the mean).Convergence of µ n,i . Let i = 1. Let Q be the probability distribution obtained as the pushforward of the uniform distribution on [0, 2π] 2 by the map F defined above. Using Equation (49) , one can show that the density f of Q is given byEQUATIONwhere (θ, ϕ) = F -1 (x). Assume that the Radon measure µ ∞,i,2 has a density g 0 on Ω (this fact is not proven, but conjectured and strongly supported by experiments). Then, using (9) , one can make a change of variables and observe that µ f,i has a density g f , given by ∀v ∈ Ω, g f (v) = 1 (2π) We sample a set A n of n = 10 5 points on a square and consider the convolution of the measure 1 n u∈dgm i (An) δ n 1/m u with a Gaussian kernel, so that we obtain an estimation ĝ0 of the density g 0 . We then define an estimator ĝf of g f by approximating the integral over a regular grid of 100 points on [0, 2π].We then place a grid of size 100 × 100 over the square [0, 17] 2 . The measure µ f,i is approximated by the measure μf,i with piecewise constant density on each square of the grid, with density in the square centered at x given by ĝf (x). The corresponding measure is displayed in the center of Figure 6 .For a given value of n, we sample a set A n of n points according to Q, and compute the corresponding measure µ n,i . The same transformations are applied to µ n,i , so that we obtain a piecewise constant measure μn,i on the same 100 × 100 grid. The heatmap of this measure is shown on the left of Figure 6 .At last, we approximate the distance OT 2 (µ n,i , µ f,i ) by computing the distance OT 2 (μ n,i , μf,i ) using the POT library, see [40, 55] . The distance is then normalized by OT 2 (0, μf,i ) = Pers 2 (μ f,i ). The evolution of the normalized distance with respect to n is plotted in Figure 6 . As predicted by Theorem 4.1, the OT 2 distance converges to 0 as n gets larger. We then repeat each experiment 10 times, with a convergence to 0 observed each time, the relative standard deviation being always smaller than 7%.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [No] Justification: The numerical experiments that we ran are basic and can be easily reproduced using the GUDHI library [62] . We therefore did not feel that providing open access to the code was necessary. We are happy to share it on demand. Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Justification: The research conducted in the paper conforms, in every respect, with the NeurIPS Code of Ethics. Note that due to the theoretical nature of our work, many (though not all) points raised in the Code of Ethics are moot.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Justification: There is no societal impact of the work performed, as it is foundational.Guidelines:• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.A multiset is a set where each element appears with some non-zero multiplicity.In general, PDs can have points with infinite coordinates. For Čech PDs, this will only be the case for a single point of the diagram for i = 0, of coordinate (0, +∞). We discard this point in the following.A compact set K ⊂ Ω is at positive distance from the diagonal. Hence, a measure µ ∈ M can have an accumulation of mass close to ∂Ω.The persistence diagram of degree i of the distance function to a set has no point with infinite coordinates if i > 0, and a single such point if i = 0 whose coordinates are (0, +∞).This corresponds to the set of diagrams of q-tame persistence modules as defined in[22].The distance function d A is proper due to the compacity of A, hence its persistence module is q-tame and the associated persistence diagram is well-defined -see[22].When a = -∞, we commit a minor abuse of notation by writing [a, b] rather than (a, b], and similarly when b = +∞. 


Decision: The paper proved upper bounds for convergence of persistent homology when data points are sampled from a submanifold in a Euclidean space. All reviewers agreed that theoretical results are worth publishing. The authors acknowledged the limitations of persistence as an isometry invariant for generic point clouds in comparison with easier, faster and stronger isometry invariants, and also in the cases when persistence can be empty and hence the proved upper bounds certainly hold.

Reviews: review: paper_summary: paper_summary: The authors study the behaviour of persistent homology under subsampling of compact sets. They have provided new convergence guarantees with respect to the p-Wasserstein distance and asymptotic results for their $\alpha$-persistence.
strength_weakness: strength_weakness: (W1) While the main results of this paper are theoretically solid and of strong interest to the TDA community, I do not see direct applications of this work to AI/ML. The authors have referenced a few works where their work might be applied (persistent homology dimension), but they have not elaborated enough on how exactly their method can be used, what kind of significant questions it can answer, and how successful that will be. 

(W2) The experiments are very limited and do not demonstrate the implications of the proved results in ML
questions: questions: (Q1) Are there any results about real-world applications of the theory?
limitations: limitations: Yes, all limitations are addressed adequately by the authors.
paper_summary: paper_summary: The $p$-optimal transport convergence of the Cech persistence diagram of a sample of a closed embedded manifold is studied, both in a deterministic and a probabilistic setting. The paper has three main results:
1. An improvement of the classical Cech bottleneck stability result for sufficiently good samples of closed embedded manifolds.
2. A bound for the total $p$-persistence, and a $p$-optimal transport-convergence result, for the Cech persistence diagram of sufficiently good (deterministic) samples of generically embedded closed manifolds; in the case $p$ is strictly larger than the dimension of the manifold.
3. A probabilistic convergence result for the Cech persistence diagram, and a law of large numbers for its total persistence. The probabilistic convergence result says in particular that $p$-optimal transport convergence of the Cech persistence diagram occurs if and only if $p$ is strictly larger than the manifold dimension.
strength_weakness: strength_weakness: - The intersection of Topological Data Analysis and Machine Learning is non-trivial but not huge, restricting the audience of the paper to some extent.
- The results have several restrictive hypothesis: strict manifold hypothesis (data lies exactly on a manifold), genericity of the manifold, no noise of any kind.
questions: questions: 1. Is there any hope that (at least part of) the main probabilistic result (Corollary 4.3) still holds for non-generic manifolds? Could the genericity assumption be removed if we instead assume that the data is sampled from a manifold plus noise?
2. 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?
3. 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$?
limitations: limitations: 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.
paper_summary: paper_summary: The paper describes three new theorems on the stability of persistence diagrams with respect to Bottleneck and Wasserstein distance under certain additional assumptions.
strength_weakness: strength_weakness: I am not sure about how much the results are in scope for a machine learning conference. I do agree that a solid foundational layer is important but my feeling is that the connection could be described in more length (Sec 4.4 seems to serve this purpose partially).

The authors also admit themselves in the conclusion that the results rely on the manifold hypothesis and the absence of noise. I guess one could argue in length about the manifold hypothesis and how realistic it is in practice. But my hunch is that not allowing any noise is a more serious limitation.
questions: questions: Why do you think that the paper is an adequate fit for Neurips, as opposed to, say, a journal specialized on TDA?
limitations: limitations: As mentioned, they address the limitations of their results adequately
paper_summary: paper_summary: The paper provides a more fine-grained analysis of stability results for persistent homology for data sampled from manifolds, proving new theoretical guarantees for methods in topological data analysis.
strength_weakness: strength_weakness: As the authors note, the proofs require some assumptions, which are not always guaranteed: they assume the manifold hypothesis and that the points are sampled without noise. Also, their analysis is based on Cech persistence and not Vietoris-Rips persistence, which is used more often in practice. In this reviewers opinion it is however still reasonable to make these assumptions, as they provide the necessary structure to thoroughly mathematically analyze the used tool (in this case persistent homology) in an „ideal world setting“, as is often done for mathematical guarantees.
questions: questions: -Did you perform any experiments on data with noise or with Vietoris-Rips persistence? If so, how did the results compare to the ones you present in the paper?
limitations: limitations: The limitations (that are also mentioned above) are addressed and explained at multiple points in the paper:
-in line 169 the authors argue why some assumptions are always needed.
-in line 216 they explain why the genericity assumption is needed for their Theorem 3.3.
- in line 353 they again mention the assumptions as the main limitation of their work.

Comments: title: references to past work
Thank you for the detailed reply
Response to the area chair
Comments by the area chair
comment: Thanks again to all reviewers and to the AC for their feedback.
Thanks for the answer. I guess it is up to the area chair, or somebody higher up to decide whether a theory TDA paper is suitable for the conference. My low score reflects my expectations that a Neurips paper should have a more direct connection to machine learning, not because I find the paper weak. In that sense, I am satisfied with the author's response that clarifies that the paper's contribution is on the theory side.
I thank the authors for their response. I have read the response and would like to stick with my score.
I am satisfied with the authors' responses.
Dear authors, because of the page limit, it's enough to briefly include the discussed references about isometry invariants within a review of past work or limitations in the main paper, so feel free to include more details in appendices. If you would like to save space, the words "Additionally, it should also be noted that other invariants, such as the empirical distribution" may not be essential, because the mentioned distributions of distances are explicitly defined invariants, not empirical outputs. Thank you.
Dear AC,

We share your commitment to scientific truth. Would you find it satisfactory if we added something  like the following to the Related Works section

*"Additionally, it should also be noted that other invariants, such as the empirical distribution of pairwise distances, have been used to study similar questions, for instance in [...]",*

as well as a subsection in the Appendix (where we describe Cech persistence diagrams) that mentions and compares alternative methods?
I would like to thank the authors for their convincing rebuttal.
The authors are right that the previous comment didn't criticize the theorems proved in the submission but mentioned the limitations, which were missed in other reviews, but should be included according to https://neurips.cc/Conferences/2024/ReviewerGuidelines : "You are encouraged to think through whether any critical points are missing and provide these as feedback for the authors."

>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 honest statement could have been used by many NeurIPS reviewers as an easy reason for rejection.  

>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

The quoted variety of tasks in [1] involves prediction of simple isometry invariants, so persistence as an isometry invariant is expected to outperform all non-invariant methods: 

(1) counting 0, 1, 2, 4 or 9 holes for samples of 20 shapes, without any guarantees, which were proved in "A fast and robust algorithm to count topologically persistent holes in noisy clouds" (CVPR 2014);

(2) prediction of a *constant* curvature by combining persistence with SVM without guarantees;

(3) convexity detection for samples of 8 shapes based on Theorem 1 saying that "X is convex if and only if for every line in R^d the persistence diagram in degree 0 with respect to the tubular filtration contains exactly one interval", whose proof wasn't found online but seems to immediately follow from the definition saying that a convex body, for any two of its points, should contain the straight-line segment connecting them. More importantly, Theorem 1 requires infinitely many checks for all possible lines.  

The limitations of [1] honestly accept that "we do not have an extensive comparison of the state-of-the-art for the given problems", so the quotes can be more exact. 

Reference [2] includes stronger and more relevant results, which deserve detailed explanations. Already the abstract talks about "a pseudo-metric between metric-measure spaces, that is bounded above by the Gromov-Wasserstein distance". Such a pseudo-metric with upper bounds can be theoretically zero for many non-equivalent objects but Propositions 3.7-3.9 prove some lower bounds under certain hypothesis, though still without claiming a proper metric on isomorphism classes.

>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.

All pairwise distances between 10^4 points in any Euclidean dimension might be computed (at least without storing them) even faster and are much more valuable due to their generic completeness under isometry. This fast computational time hints that the outputs can be small and often even empty as formally proved now for generic clouds with trivial 1D persistence.

The more important problem is to provide theoretical guarantees. Otherwise, any quick output can be claimed the fastest "state-of-the-art". Hence your guarantees for the Cech filtration are valuable before computation becomes relevant. The only advice is to accept the known limitations and carefully quote the relevant past results.
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++
Question. Do all experiments considered only uniformly sampled points on a square and a 2-dimensional torus?

Limitations. The major limitation of persistence is its weakness as an isometry invariant. For all standard filtrations (including Cech complexes considered in this paper) on a point cloud, any persistence diagram is invariant under all distance-preserving transformations and hence should be compared with the already known isometry invariants of point clouds. 

Already in 2004, Boutin and Kemper proved that the distribution of pairwise distances distinguishes all generic clouds of unordered points in any Euclidean space, see  https://www.sciencedirect.com/science/article/pii/S0196885803001015. 

Combined with the computability in quadratic time and Lipschitz continuity, this result makes distance distributions much more practical than persistence. These distributions were extended to the complete invariants for all point clouds (including singular ones) by Widdowson et al in the paper at https://openaccess.thecvf.com/content/CVPR2023/html/Widdowson_Recognizing_Rigid_Patterns_of_Unlabeled_Point_Clouds_by_Complete_and_CVPR_2023_paper.html  

More recently, persistence was proved to be identical (and even empty) for generic non-isometric point clouds by Smith et al in the paper at https://link.springer.com/article/10.1007/s41468-024-00177-6. All stability results for persistence provided only upper (not lower) bounds for distances on persistence diagrams, but these distances can often be zeros for generic clouds of unordered points. 

Though the Cech complex is too slow for real data, the proofs in the paper (if correct) can still be valuable in the hope that they can be later extended to more practical constructions. However, it is important to embrace a bigger picture as advocated in the book "The Scientific Truth, the Whole Truth and Nothing but the Truth", https://www.taylorfrancis.com/books/mono/10.1201/9781003405399/scientific-truth-whole-truth-nothing-truth-john-helliwell

If the authors are committed to the highest level of scientific integrity, the paper should discuss the *whole* truth about persistence including its weakness as an isometry invariant vs easier, faster, and stronger invariants.

The authors and reviewers are encouraged to consult the guidance at https://neurips.cc/Conferences/2024/ReviewerGuidelines and focus on justified comments, questions, and answers, without putting weight on numerical scores because scientific decisions should be made not by popular votes but through rigorous arguments.