Wasserstein convergence of Cech persistence diagrams for samplings of submanifolds
Authors: Charles Arnal
David Cohen-Steiner
Vincent Divol
Venue: NeurIPS 2024 poster (2024)
Keywords: topological data analysis; persistence diagrams; simplicial complexes; differential geometry; Wasserstein distance
Primary area: learning_theory
TL;DR: We study the convergence of Cech persistence diagrams for samples of submanifolds with respect to the Wasserstein distance.

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.

Wasserstein convergence of Čech persistence diagrams for samplings of submanifolds
Charles Arnal* Université Paris-Saclay, Inria
David Cohen-Steiner
Université Côte d' Azur, Inria
Vincent Divol* CREST, ENSAE
Abstract
Čech Persistence diagrams (PDs) are topological descriptors routinely used to capture the geometry of complex datasets. They are commonly compared using the Wasserstein distances OTр; however, the extent to which PDs are stable with respect to these metrics remains poorly understood. We partially close this gap by focusing the case where datasets sampled on m-dimensional submanifold Rdd Under this manifold hypothesis, we show that convergence with respect to the OTp metric happens exactly when p upon the bottleneck stability theorem in this case and prove new laws of large numbers for the total e-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.
We also provide improvements
1 Introduction
Topological Data Analysis (TDA) is 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; (A) of set A, which captures the i-dimensional
topological features of A for i 2 0, see e.g. [46] or Appendix B TDA has been successfully applied in variety of domains, including material science 51
63 30
17), biology (21 68 g real algebraic
geometry 229 35 28 44 and neuroscience 667 61 name 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 graph classifications [19 50
The most prominent techniques TDA rely on multiscale approaches, in particular through the use of persistent homology [22). Given compact set A in Ed persistent homology tracks the evolution of the homology groups H²(A') of the 1-offset A' = UnEA B(x, t) of A as goes from 0 to +oo (where (xx,() is the closed ball of radius / centered at æ). The process is summarized by the Čech persistence diagram (PD) of degree of the set A: the PD dgm, (A) is multise of points in the half-plane := {(u1, u2) E R², 41 < u2). where each point (u),u2) in the PD corresponds to i-dimensional topological feature that appeared in A' at scale ij (its
birth time) and disappeared at scale & tt (its death time), see Figure Points close to the
Equual contribution
"A multiset
where each element appears with 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, +oo). We discard this point in the following.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

0.
03-
Damm
Bitth
The Čech PD of point cloud in TR22 for 1 and its t-offsets. The two points far from the diagonal a in dgm,(A) correspond to the two large cycles in the set A.
Figure 1:
diagonal 02 = (uu, u2) E R
21 = =2) correspond to topological features of small persistence 21-1 which have a short lifetime in the filtration (A ')120-
pers(u) = 2
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 the bottleneck distance between PDs [36). Let and be two PDs. A partial matching between and b is bijection of multisets Y a U 0 + b al, where each point (u, u) of aQ has infinite multiplicity. In other words, the points of 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
either paired with single point of b, mapped to the diagonal an (and
OT (a, b) = inf max |/u (w)]lo
7ET(a.M WEOL
The Bottleneck Stability Theorem
26
22
states that A₁ and Ag are two compact sets, then for any
integer i 2 0
OT (ddm) S
where is the Hausdorff distance between the sets A₁ and A2, defined by (AI, A2)
supzerd IdA, (x) dya (ar) and where dA 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 on a slab of width æ above the diagonal (for the lo -mtric) without changing the bottleneck distance between the two PDs.
Due to this phenomenon, the bottleneck distance turns out to too weak 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 OTp- are defined for S p < oo by
1/p
OT,(a,b)
inf (EL(a.b)
Σ
||u (w)
with OTр S OT,, for 1 sp< distances used in optimal transport, with the diagonal iΩ playing the role of landfill of infinite mass, see e.g.
so. They can be seen as modified versions of the Wasserstein
The increased sensitivity to small perturbations of the OT, distances is of crucial importance in the standard TDA pipeline, which we briefly recall. Starting from sample of sets AI...., An, one computes a sample of PDs a; dgm, (A,),
1,..., n. Statistical methods to analyze this sample of PDs are typically awkward define, due to the nonlinear geometry the space of PDs To overcome this issue, the space of PDs is mapped to vector space through some map
[6 75). called a feature map. Statistical method are then applied in the feature space on the transformed sample & (a11),... ...,..... (a.,). important examples including persistent images (4) PersLay [19] and PLLay (50 in the latter two, the feature map is parametrized by neural network. A good feature map should preserve as much as possible the geometry of the space of PDs (57: particular, Lipschitz (or Hölder) continuity of the feature map basic requirement. However, due to their (often desirable) sensitivity to small scale
Various feature maps have been designed 23 60
54 20 70 (33, 48), 25

---

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, distance (see e.g. [3 Proposition 5.2)), or to the OT, p distances (for 1) when restricted to diagrams whose a-total persistence
Persa (a) = =Σ pers(u)
is bounded for some a > O large enough, see [3 and [53 Boundedness assumptions on the o-total persistence also yield a version of the Bottleneck Stability Theorem with respect the finer OT, distance: if A₁ and Ag are such that Persa (dgm,((A)) S M (k = 1),,, then, for p 2 a,
OTg(dgm,(A)) dgm, (A2)) S Me"-a,
(5)
where (A1: A2), see [27 Hence, in addition to having intrinsic theoretical interest, controlling the total persistence and convergence with respect to the OTp distance of PDs is crucial 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 compact subset of am m-dimensional manifold M in Rd, focusing in particular on the total persistence of the PDs and their convergence to the PDs of M with respect to the OT, 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:
When A C M is compact set satisfying dy (A, M) < E for E 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 E dgm, and the coordinate of the matched point (u) E (gm,(M) U an is of order (E whenever the coordinate of u is larger than 2e.
Theorem 2.2;
Theorem 3.3 In the case where the manifold M is generic and the set A is a ô-sparse point cloud (i.e. mA || - yll 2 6). we provide a finer analysis by showing that the p-total persistence Persy (dggs (A)) remains bounded and the distance OT, (dgm, converges to for all p > m whenever the ratio z/ō upper bounded.
(lgmm(M)
Corollary 4.3 We then focus on random context, by assuming that A = A,, is obtained by sampling n L..dd random variables with positive bounded density f on a generic manifold M. We prove that p (Am), dgm, (M)) converges in expectation to 0 for p >> m. Furthermore, we obtain a law of large numbers for the o-total persistence of dgm; (Am)::
Pers, (dgm, = Pers, (dgm, (M))+ - amm tor (n (n--an a/ - log n
(6)
for all a > 0, where C; is a constant that depends explicitly on M and f. In particular, for 0 0 < m, (dgm,
stays bounded if and only if a 2 m.
Our contributions are to be compared to one of the only preexisting results regarding the a-total persistence of a PD: in (27), the authors proved that for all a strictly greater than the ambient dimension d, the a-total persistence of the Čech PD of a compact set A C B(0, R) C Rd satisfies
Persa (dgm,(A) S Ca
for some constant Co.d depending on a and d. In the two scenarios we considered (either d-sparse or random samples), the ambient dimension in the constraint a > d for the control of the a-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 (444) 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 part of long ongoing effort to understand simplicial complexes and 44 45). Closest to our work, Hiraoka, Shirai
PDs in a random context [10 12 1
49
32
59
3

---

and Trinh gave limit laws for Čech PDs for random points in the cube [0, 1]" 447 while Goel, Trinh and Tsunoda gave similar asymptotics in the case of samples on manifolds
Limit laws for the
total persistence have been obtained by Divol and Polonik in the case of random samples in the cube Among other contributions, this work generalizes this result to submanifolds: unlike the cube, a manifold has 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 777 [22 consider complete isometric invariants for point clouds that are computable in polynomial time.
3d
2 Čech persistence diagrams for subsets of submanifolds
Recall that a fundamental result in TDA, the Bottleneck Stability Theorem 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 and supxes (x) S &. The Bottleneck Stability Theorem ensures that OT oo (dgm,(A) dgm,(S)) S for any i 2 0, bound which cannot be improved in general. However, it turns out that a finer understanding of the proximity between dgm; (A) and (Sm can be obtained if more regularity is assumed on the shape of interest S, namely in the situation where M is a compact submanifold with positive reach.
Let us first set some notation. Let M be an m-dimensional compact topological submanifold of Rd. we always assume that the boundary of M is empty. The orthogonal projection RM on M is defined for x close enough to M, and we define the reach 7 rM) as the largest r > 0 such that the orthogonal projection TM is well (i.e. uniquely) defined for all x E I2 at distance strictly less than y from M.
The reach is key notion to quantify the regularity of manifold, see e.g. (39] and 24 for more information.
Let A C. M be such that du (A, M) S and let Rd By definition of the Hausdorff distance, it holds that (da(2)- - dm (2)) S e. However, this naive bound can be quadratically improved as long as stays far away from M.
Lemma 2.1. Let M C Rdd be compact submanifold with positive reach and let A C M be compact set with (A, M) S for some > O. Let E R.. Then, [dha(z) da(z)l s
(3) 1 11+ dalzz)
7(M)
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
(2)
3 Ca
C22
regions in the upper halfplane Ω (displayed in Figure 2 which contain
Ce
all points in the PD dgm, (A) (for some integer i 2 0). In the first region, corresponding to microscopic topological features disappearing at scales smaller than E + <MM) the Bottleneck Stability Theorem cannot be improved. However, there exists an optimal matching (i.e. a matching 7 dgm, (A) U aΩ + dgm.(M) U an that realizes the
(1)
bottleneck distance ( such that at least one of the coordinates of
any point in the other two regions is larger than r(M) s² 3M/T(M). and the proximity between a large coordinate of a point u E (ggm(()) and the coordinate of the matched point 7(1) E (M)) U an is of order (s²). This yields a quadratic improvement upon the Bottleneck Stability Theorem.
Figure 2: PDs of M (red) and of A (black).
Theorem 2.2 (Improved Bottleneck Stability Theorem). Let M C Idd be compact submanifold with positive reach and let A c. M be compact set such that dy (A, M) < E < T(M)/4. 4. Let i 2 0 be an
integer. Then dgm, (A) the union of three regions dgm, (1) (A) == dgm, (A) n {u1. U2 S - }.
dgm; (2) (A) = dgm, (A) O {un S E, u2 2 T(M)
_² T(M) } and dgm; (3) (A) = dgm;(A) 0 {u1, u2 2
23 }. r(M)- 7(M)

---

Furthermore, let C =(M) (1 R(M)
7(M) ). where R(M) the radius of the smallest ball that contains
M. There exists optimal matching 7, Agmm((A) U an - dM),(M) U an for the bottleneck distance between dgm,(A) and dgg,((M such that
Region (1): uf E dgm. (2) ( (A), then r(u) 8Ω and I|u - --)ll S..
(gg (A), then (u) is of the form u2) and |uz - U2l S Co?. The number of such points is finite and depends only M.
Region (2): If E dgm!
Region (3): Ifu dgm
(3) (A), then ||u 7 oo Co?
Note that for any 2 d, the i-th PDs of M and A are actually trivial.
3 Č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 a-total persistence of (A) and the distance OTp, (dgm, (A), (g), for p < oo crucially depend on the number of points in dgm;(A) having small persistence.
Unfortunately, no control on, say, the total persistence, exist without additional assumptions. Indeed, in general, even the a-total persistence of the Čech PD of the submanifold M can be infinite. Example 3.1. Let f E R + + sin(1/x)2 Consider the C² curve M in R defined as the union of the graphs of the functions and -f on [-2,2]. 2]. Being C², the curve has positive reach [39]. For 1, the Čech PD) of M contains a sequence of points (1,ex) for 2 1, where la = 1 (). In particular, as Enzi(en 1) +o0 for a < 1/4, the O-total persistence of (dgm,(M) infinite for such value of o.. By considering the product M C R2mm one can also build an mn-dimensional C compact submanifold without boundary such that dgin, (M) has an infinite a-total persistence for < m/4
The existence of such counterexamples is explained by the fact that the distance function dm to a set M is not well- behaved in general, even when the set M is smooth. Yim & Monod (in the case of surfaces in R3) and Arnal, Cohen-Steiner & Divol (in the general case) studied the distance function dM M when M is generic submanifold 71). Their findings indicate that, although counterexamples such as the one presented in Example 3.1 exist, they are extremely uncommon in sense which can be made precise.
contrast to this bleak general case, Song,
Namely, given an abstract manifold M, Arnal, Cohen-Steiner and Divol show that the set of C2 embeddings of M into Rd such that dm satisfies some desirable regularity conditions (described in Appendix C forms an open and dense set in the set of all C2 embeddings equipped with the C2-Whitney topology (6] Theorem 1. In what follows, we will simply refer to a Cº² compact submanifold M such that dm satisfies the regularity condition described in Appendix[Clar generic. See Figure 3 for an example.
Figure 3: A generic torus.
Proposition 3.2 (Čech PDs of generic submanifolds). Let M be a generic submanifold of TR... Then, for any integer i 2 0, the PD dg), contains finitely many points. In particular, Pers, (dggm(M)) too for all a >
When M is generic submanifold, it becomes a reasonable task to control the number of points in (A) where
M is an approximation of M with dæ (A, M) < The Bottleneck Stability Theorem implies that when E is small enough (compared to the smallest persistence of point in dgm, (M)), every point of dgm; (M) is mapped to point in dgm, (A) by the optimal bottleneck matching, leaving the points of dgm, (A) at E. distance to 82 less than unmatched; those will be mapped to the diagonal A2 The Improved Bottleneck Stability Theorem 2.2 (see Figure 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(e)), 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,, is random
5

---

sample of n points, the number of points in Region (I) is of order ((n)), In contrast, the genericity hypothesis allows us to show that the number of points in Region (3) small under reasonable sampling assumptions.
We say that point cloud A C M is (6, ed-dese in M if d (A, M) and min | yll 8.
Such point clouds naturally occur, c.g. as products of the farthest point sampling algorithm [2).
Theorem 3.3. Let M C Rd be a generic compact submanifold and A C M be a (5, - set in M
for some E, 8 > O. Let a 2 e/ô and let i Z 0 be an integer. There exist Eo 0 depending only on M and Co, C1 C2 C3 depending only on M and a such that if S co, then dgm; (A) ( points and for all p 2 1, 0,
has at most Co
(Tg (A), dM)) S Cien-m Pers. (dgm, & C2(C3 + +55 -.
(8)
In particular, as long as the ratio e/6 is larger than some constant a > O. the OTp distance between dgm,(A) (A) and (M) converges 0 for all p > m as E + O, while the p-total persistence persp( (dgm, (A)) stays bounded.
Example 3.4. Consider two parallel line segments M in IR2 and a finite set A consisting of two parallel grids of step 2e: the set A is (2e, e)-desse in M. Then, there are O points in dgm, (A)
with birth coordinates un equal 1/2 and persistence of order O(e²); they all belong to dgm, (3) (A),
whose cardinality is thus not bounded by some Co = Co(M). This example can be easily modified to
make M compact C2 1-dimensional manifold. This shows that the first conclusion of Theorem 3.3
cannot hold without a genericity assumption on M.
4 Random samplings of submanifolds
We now turn to the case of random samplings of (non- moon-generic and generic) submanifolds. They tend to adopt configurations that are more regular than what can be expected from e.g. a general E-dense sampling, yet their randomness gives rise to new technical difficulties. Let P be probability measure having a density f (with respect to the volume measure) on a compact submanifold M of dimension m 2 1. Let A = A,, (X1..... X,). where Xj...., X,, is an i.i.d. sample from distribution P. Let i 2 0 be an integer; we consider the three regions described in Figure 2 and in the statement of Theorem 2.2 and write again dgm!") (1) (Am.). dgm, (2) (A..) and dgm, (3) (A..) 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) (A..) only depends on small-scale scale phenomena and can essentially be reduced to the case of a cube, even if M is non-generic, while dgm, (2) (An) and dgm, (3) (A..) 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 () (A..) requires extending the metric OTp between PDs to more general Radon measures. Indeed, a PD can equivalently be seen as an integer- valued discrete Radon measure on Ω2 by identifying a multiset with the Radon measure Evea 6g- Let M denote the space of Radon measures on $2, that is the space of Borel measures on Z which give finite mass to every compact set K C 2 The space of Radon measures is endowed with the vague topology, where a sequence (mn),, of measures in M is said to converge vaguely to μ E M if Sa oxdj,, + Jn ødp as n + oc for all continuous functions @ Ω + RR with compact support.
The a-total persistence is defined for μ .M by (p) Jo ddrs()))dy(w). For p 2 1, we let .M {u M : Pers, (n) < +00}. The distance OT,,- p. defined between PDs in (3), can be extended to the set MP, see [33]. The distance OT, 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, is defined for measures having different (and even infinite) masses. We refer to Appendix [ for the precise definition and the main properties of the OT, p distance on the space Mp.
A compact set K C Ω is at positive distance from the diagonal. Hence, measure E . can have an accumulation of mass close to M..

---

For > O. given a function f:N - R and sequence of (nonnecessarily measurable) real maps (Y,),, defined on some probabilisitic space, the notation Y,, Or. (f()) means that [-]],,]""] (()(n))), where IF" denotes the outer expectation 73 p.6] (and similarly for the little notation).
4.1
Region (1)
Consider the rescaled Radon measure Mn.i +. weddgm ( (A.) / and note that Un is random measure, owing to the randomness of the set An. Goel, Trinh and Tsunoda studied the vague convergence of the sequence (H,,,), 42] Remark 4.2]. Namely, assuming that the density f satisfies SM f < oo for all 2 O, they show that with probability the sequence (Un,i)n converges vaguely to some (non-random) Radon measure Mf,-- The limit measure Hf. has support {0} x R, if = 0 and Ω if < < m;; it is the zero measure if i 2 m. We can further describe as follows: let Moa,i,m be the limit of the sequence (Mn,)) in the case where the sample A, is uniform on the unit cube [0, 1)md (see 34 ). Then, for any continuous function Φ + IR with compact support,
J ((u)dps=(") = (/aaa I (()))((())))//)) 1/ 1/m" udddddddpce..... (u).
Note that the vague convergence of Radon measures is only defined with respect to compactly supported functions; as such, is blind to phenomena located increasingly close the diagonal as as n nogs to infinity. In particular, and except in the case of the uniform distribution on the unit cube [0, 1.11 (see (4) ) it was not known whether Mn.i converges to ff for the OT, distance as well, nor whether the sequences of total persistence (Pers, (Jn,))) converge. We close this gap with the following result.
Theorem 4.1 (Law of large numbers). Assume that P has a density I on M bounded away from 0 and 0o. Let i 2 0 be an inleger and let 1 S p < 00. Then jig. M, and ( (f,,,]
120000
Furthermore, for all 0, Pers (dgm, (1) (A -1 Persa (pn,)) Pers, (pz,a) + oz (1).
4.2 Regions (2)-(3)
It is well-known fact that the Hausdorff distance drr, M) between random sample and M of order (log nongnnn) n//n)//m whenever the underlying density is bounded away from zero and co on
M, see e.g. [38] Hence the PDs dgm (2) (Am)) and dggm (3) (A..) can be described using Theorem 2.2 However, in the case where M is generic submanifold, one actually obtain tighter results. We let #E denote the cardinality of multiset E.
Proposition 4.2. Let M be generic m-dimensional submanifold. Assume that P has density I on M bounded away from O and Do. Let be an integer. There exists an optimal mutching Tn dgm, (An) U + dgm;(M)U888 (M)U80 for the bottleneck distance between dgin((A)) and dgm, (M) such that for any q 2 1:
Region (2): holds that max wEdgm,"
(2 (A..) Iu2 - (x)2l = 01o
Region (3): It holds that max dedgm! (A.). ||u - (n(llllo = O On-(n2//m) and
#(dgm,
(A..)) (3)()))))
(1))
We remark that the same bounds can be obtained almost surely (e.g. "a.s. there exists C such that "Edgmm" (9) (A..) ||u (w))ll I Cn -n/mm",,, rather than in expectation, using similar arguments.
Proposition 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 12) 2/m Second, the random sample A,, is in general only ô-sparse for ö of order n 2/m
Hence, A, (6, dense in M, but with a diverging ratio e/ő. Therefore, Theorem 3.3 cannot be applied to control the total number of points in dgm,(A,) ) in Region (3).
4.3 Consequences for the Wasserstein convergence of persistence diagrams
As a simple consequence of Theorem 4.1 and Proposition 4.2 we obtain that for i < m, the p- Wasserstein convergence of (dgm,(A,) ) to dgm, (M) holds if and only if p >> m, as well as precise asymptotics for the total persistence of (dgm, (A,)).
7

---

p p p 2
p -
Death
6.2
Birth
Figure 4: Left: the Čech PD dgm; (A,) of a sample of n 10a points sampled on generic torus, with points in Regions (1), (2) and (3) highlighted in different colors. Right: the persistence images of dgm, (Ap) with weight pers? for different values of p.
Corollary 4.3. Let p 2 and let S d be integer. Under the same assumptions in Proposition 4.2 the following holds:
Ifp > m, then (dgm, (M))( + co.
P m, B[OT (dgm, (An), dgm,(M)) (ersp((Hx...,m) Vol(M) Do, where Vol(M) is the volume of M.
1f m and < m, then EloTg (An), dgm; +00 0
Furthermore, for all a > 0, Persa (ggmm(( (An)) is equal to
(dgm, + nn' Persa (M f(x) - dx ol (n'-#)+ O2 +0 ( log ni
As noted earlier, both (A.,(A.) and dgm,(M) are trivial if 2 d.
This corollary gives a precise answer to the questions raised in the introduction. First, when A,, is a random subset of a m-dimensional generic manifold in Rd the a-total persistence of dgm, (A.) not only bounded for a d was shown by Cohen-Steiner Moreover, the sequence dgm,,A,, (A..) converges for the OT, distance if p > m. A curious phenomenon can observed in the case p m: the sequence does not converge to dgm,(M) as one would expect, but its distance to the power to the power p of matching all the points in Region (I) to the diagonal dn neither converges to nor diverges, but is asymptotically equal to this constant.
al. (27)), but for all a 2 m.
dgm; (M) converges to some constant-in that case, the cost
Using these bounds on the total persistence, feature maps, called linear feature maps, which includes feature maps introduced in [23] 60) 25 54 70 19]. Let (V, II) be normed vector space, and let Ω be a continuous bounded map. For a 2 O. the linear feature map 4 associated to @ and defined on the space Dj of PDs having finite number of points is defined for all E DD by (a) Enea (ers(u)"dd())) E V.
obtain regularity guarantees for a large family of
Corollary 4.4. Let a 1 and let 0
d be an integer. Under the same assumptions as in Proposition 4.2 it holds that & (dgm, (A.)) converges in probability to &a (dgm,(M)) whenever m.
argued for using linear feature maps of the form (a) = Evea arctan(pers(u)) (u)). Similar results would hold for such feature maps, as the map + (persn ((())/)()))))))))))) ((uu//prr(u))) (u))(u)" continuous and bounded whenever ø is.
Remark that other weighting schemes possible. For instance, 53
Numerical experiments
illustrate our results with synthetic experiments, full details are given in Appendix H. We create generic submanifold of dimension
by applying random diffeomorphism V to a given m- dimensional submanifold Mo (e.g. a torus). We then draw sample of n i.i.d. observations sampled according to the pushforward P of the uniform distribution on M by V.

---

10a
10a
102
10a
10-1
p=1
10a
2=2
100
10-3
p=3
10
p=4
10-1
10
10a
10a
10
10²
10a
10a
10a
10a
10a
Figure 5: Plot in log-log scale of Persy (dgm. (1) (An)) as a function of n for points sampled on circle, i (left), points sampled on torus, 0 (center), points sampled on torus, =1 (right). Dashed lines have slopes equal to p/m.
Continuity of feature maps. As first experiment, test the continuity of a feature map, the persistence image [4]. In Figure[4] we plot the persistence image of dgm, (A,) where A,, is a sample of n = 10 points points with large persistence corresponding to the PD of the underlying torus are nonapparent in the image. For p > the two points are apparent, and the contribution of points with small persistence (close to the lower edge) has vanished. In the limit situation 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" with p > m should be used; when the relevant information is the underlying density of the datasets, the choice < m should be preferred.
generie torus. We observe that the map is discontinuous for p < 2: the two
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 10a to 10 we compute Persy(dgui) (1) (A..) )) in three scenarios: points sampled circle for i = 0, and points sampled torus for 0 and i == 1. The correct rates of convergence are observed on log-log plot, see Figure For = 1, we remark that the asymptotic regime starts at larger values of n, above 10a
Convergence of Mn,i- We sample n points on a torus by uniformly sampling the two angles (0) parametrizing the torus. We obtain a (nonnuniform) probability measure, having density f. We then compute, for various values of n. the measure (*,,1- The measure is approximated by kernel density estimation (see Figure 6 We approximate in a similar manner the measure 1o,, by sampling n 10 points on square. We then apply the change of variable formula (9) to compute the theoretical limit f. The distance OT2 Hf.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
16.
16
0.08
Death
10
Death
10
0.06
0.04
0.02
2
10
10
0 20000
40000 60deo 80000 100000
Birth
Birth
Figure 6: Left: Heatmap of |n,1 for 5. 10 points sampled on the torus with density f. Center: Heatmap of py.1. Right: OT, distance between fn,1 and fy.1 (normalized by OT2(0, Hy,,)) for n ranging from 102 to 105.

---

Conclusion
Under the manifold hypothesis, 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- p-Wassertein distances, as well as detailed asymptotics for their total a-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 sampled from submanifold, and without any noise. Relaxing those assumptions, as well establishing similar guarantees for Victoris- Rips complexes, could be the subject of future research. We also plan on exploring the consequences of our findings regarding the persistent homology dimension 66 65 of submanifolds.
10

---

References
[1] Eddic Aamari. Rates of convergence for geometric inference. PhD thesis, 2017.
[2] Eddie Aamari and Clément Levrard. Stability and minimax optimality tangential Delaunay complexes for manifold reconstruction. Discrete & Computational Geometry, 59:923-977 2018.
[3] Henry Adams, Manuchehr Aminian, Elin Farnell, Michael Kirby, Joshua Mirth, Rachel Neville, Chris Peterson, and Clayton Shonkwiler. A fractal dimension for measures via persistent homology. In Topological Data Analysis: The Abel Symposium 2018, pages 1-31. Springer, 2020.
[4] Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence images: A stable vector representation of persistent homology. Journal of Machine Learning Research, 18(8):1-35, 2017.
[5] Charles Amal. The distance function to a finite set is a topological Morse function. arXiv e-print arxiv:2407.15555 2024.
[6] Charles Amal, David Cohen-Steiner, and Vincent Divol. Critical points of the distance function to generic submanifold. arXiv preprint arXiv:2312. 13147, 2023.
[7] Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken. Tight Bounds for the Learning of Homotopy à la Niyogi, Smale, and Weinberger for Subsets of Euclidean Spaces and of Riemannian Manifolds. http:://arai..orggbb/2226..0
2022.
[8] Andrew Aukerman, Mathieu Carrière, Chao Chen, Kevin Gardner, Raúl Rabadán, and Rami Vanguri. Persistent homology based characterization of the breast cancer immune microenvi- ronment: A feasibility study. Journal of Computational Geometry. 12(2):183 106, 2022.
[9] Tolga Birdal, Aaron Lou, Leonidas J Guibas, and Umut Simsekli. Intrinsic dimension, persistent homology and generalization in neural networks. Advances in Neural Information Processing Systems, 34:6776-67788 2021.
[10] Omer Bobrowski and Robert Adler. Distance functions, critical points, and the topology of random Cech complexes. Homology, Homotopy & Appllccatinn,, 16(2), 2014.
[11] Omer Bobrowski and Matthew Kahle. Topology of random geometric complexes: a survey. Journal of applied and Computational Topology, 1:331-364, 2018.
[12] Omer Bobrowski, Matthew Kahle, and Primoz Skraba. Maximally persistent cycles random geometric complexes. The Annals of Applied Probability, pages 2032-2060 2017.
[13] Omer Bobrowski and Shmuel Weinberger. On the vanishing of homology in random Cech complexes. Random Structures & Algorithms, 51(1):14-51, 2017.
[14] Magnus B Botnan and Christian Hirsch. On the consistency and asymptotic normality of multiparameter persistent Betti numbers. Journal of Applied and Computational Topology, pages 1-38, 2022.
[15] Bradley CA Brown, Anthony L. Caterini, Brendan Leigh Ross, Jesse C Cresswell, and Gabriel Loaiza-Ganem. Verifying the union of manifolds hypothesis for image data. arXiv preprint arXiv:2207.02862 2022.
[16] Peter Bubenik and Alexander Wagner. Embeddings of persistence diagrams into Hilbert spaces. Journal of Applied and Computational Topology, 4(3):339-351, 2020.
[17] Mickaël Buchet, Yasuaki Hiraoka, and Ippei Obayashi. Persistent homology and materials informatics. Nanoinformatics, pages 75-95, 2018.
[18] Luigi Caputi, Anna Pidnehesna, and Jaroslav Hlinka. Promises and pitfalls of topological data analysis for brain connectivity analysis. Neurolmage, 238:118245,, 2021.
11

---

[19] Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topologiaal signatures. In International Conference on Artificial Intelligence and Statistics, pages 2786-2796. PMLR, 2020.
[20] Mathieu Carriere, Marco Cuturi, and Steve Oudot. Sliced Wasserstein kernel for persistence diagrams. In International conference machine learning, pages 664-673. PMLR, 2017.
[21] Mathieu Carrière and Raál Rabadán. Topological data analysis of single-cell hi-c contact maps. In Topological Data Analysis: The Abel Symposium 2018, pages 147-162. Springer, 2020.
[22] Frédéric Chazal, Vin De Silva, Mare Glisse, and Steve Oudot. The structure and stability of persistence modules, volume 10. Springer, 2016.
[23] Frédéric Chazal, Brittany Terese Fasy, Fabrizio Lecci, Alessandro Rinaldo, and Larry Wasser- man. Stochastie convergence persistence landscapes and silhouettes. In Proceedings of the thirtieth annual symposium on Computational geometry, pages 474-483, 2014.
[24] Frédéric Chazal, David Cohen-Steiner, and André Lieutier. A sampling theory for compact sets Euclidean space. Discrete Computational Geomelry, 41 41:441 1-79, 06 2006.
[25] Yen-Chi Chen, Daren Wang, Alessandro Rinaldo, and Larry Wasserman. Statistical analysis of persistence intensity functions. arXiv preprint arXiv: 10.002500, 2015.
[26] David Johen-Steiners Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. In Proceedings of the twenty-first annual symposium on Computational geometry, pages 263-
271, 2005.
[27] David Cohen-Steines Herbert Edelsbrunner, John Harer, and Yuriy Mileyko. Lipschitz functions have Lp-stable persistence. Foundations of Computational Mathematics, 1072):127-139, Apr 2010.
[28] Sandra Di Rocco, Parker B. Edwards, David Eklund, Oliver Gäfvert, and Jonathan D. Hauenstein. Computing geometric feature sizes for algebraic manifolds. SIAM Journal on Applied Algebra and Geometry, 7(4):716-741) 2023.
[29] Sandra Di Rocco, David Eklund, and Madeleine Weinstein. The bottleneck degree of algebraic varieties. SIAM Journal on Applied Algebra and Geometry, 4(1):227-253, 2020.
[30] Joshua A Dijksman, Lenka Kovalcinova, Jie Ren, Robert Behringer, Miroslav Kramar, Konstantin Mischaikow, and Lou Kondic. Characterizing granular networks using topological metries. Physical Review E, 97(4):042903, 2018.
[31] Vincent Divol. Minimax adaptive estimation in manifold inference. Electronic Journal of Statistics, 15(2):58885533 2021.
[32] Vincent Divol and Frédéric Chazal. The density of expected persistence diagrams and its kernel based estimation. Journal of Computational Geometry, 10(2): 2019.
[33] Vincent Divol and Théo Lacombe. Understanding the topology and the geometry of the space of persistence diagrams via optimal partial transport. Journal of Applied and Computational Topology, 5:1-53, 2021.
[34] Vincent Divol and Wolfgang Polonik. tions of persistence diagrams. Journal of Applied and Computational Topology, 3(3):249-283, 2019.
On the choice of weight functions for linear representa-
[35] Jan Draisma, Emil Horobet, Giorgio Ottaviani, Bernd Sturmfels, and Rekha Thomas. The euclidean distance degree of an algebraic variety. Foundations of Computational Mathematics, 16:99 - 149, 2013.
[36] Edelsbrunner, Letscher, and Zomorodian. Topological persistence and simplification. Discrete & computational geometry, 28:511-533 2002.
[37] Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. 01 2010.
12

---

[38] Brittany Terese Fasy, Fabrizio Lecci, Alessandro Rinaldo, Larry Wasserman, Sivaraman Balakr- ishnan, and Aarti Singh. Confidence sets for persistence diagrams. The Annals of Statisties, 42(6))2301, 2014.
[39] Herbert Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3):418 491, 1959.
[40] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, al. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021.
[41] Christopher R Genovese, Marco Perone-Pacifice Isabella Verdinelli, and Larry Wasserman. Manifold estimation and singular deconvolution under Hausdorff loss. The Annals of Statistics, 40(2):941-963, 2012.
[42] Akshay Goel, Khanh Duy Trinh, and Kenkichi Tsunoda. Strong law of large numbers for Betti numbers in the thermodynamic regime. Journal of Statistical Physics, 174(4):865-89) 2019.
[43] Karsten Grove. Critical point theory for distance functions. Proceedings of Symposia in Pure Mathematics, pages 357-385, 1993.
[44] Andrea Guidolin, Antonio Lerario, Isaac Ren, and Martina Scolamiero. Morse theory of Euclidean distance functions and applications to real algebraic geometry. arXiv e-print arXiv:2402.08639, 2024.
[45] Olympio Hacquard and Vadim Lebovici. Euler characteristic tools for topological data analysis. arXiv preprint arXiv:2303. 14040, 2023.
[46] Allen Hatcher. Algebraic topology. Cambridge Univ. Press, Cambridge, 2000.
[47] Yasuaki Hiraoka, Tomoyuki Shirai, and Khanh Duy Trinh. Limit theorems for persistence diagrams. The Annals of Applied Probability, (8(5):7700-2780 2018.
[48] Christoph D Hofer, Roland Kwitt, and Marc Niethammer, Learning representations of persis- tence barcodes. Journal of Machine Learning Research, 20(126): 1-45, 2019.
[49] Matthew Kahle and Elizabeth Meckes. Limit theorems for Betti numbers of random simplicial complexes. Homology, Homotopy and Applications. 15(1):343-374, 2013.
[50] Kwangho Kim, Jisu Kim, Manzil Zaheer, Joon Kim, Frederic Chazal, and Larry Wasserman. Pllay: Efficient topological layer based persistent landscapes. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15965-15977. Curran Associates, Inc., 2020.
[51] Kondic, Kramár, Luis Pugnaloni, C Manuel Carlevaro, and K Mischaikow. Structure of force networks in tapped particulate systems of disks and pentagons. ii persistence analysis. Physical Review E, 93(6):062903, 2016.
[52] Vitaliy Kurlin. Simplexwise distance distributions for finite spaces with metrics and measures, 03 2023.
[53] Genki Kusano, Kenji Fukumizu, and Yasuaki Hiraoka. Kernel method for persistence diagrams via kernel embedding and weight factor. Journal of Machine Learning Research, 18(189):1-4) 2018.
[54] Genki Kusano, Yasuaki Hiraoka, and Kenji Fukumizu. Persistence weighted gaussian kernel for topological data analysis. In International conference on machine learning, pages 2004-2015 PMLR, 2016.
[55] Théo Lacombe, Marco Cuturi, and Steve Oudot. Large scale computation of means and clusters for persistence diagrams using optimal transport. Advances in Neural Information Processing Systems, 31, 2018
[56] J.W. Milnor. Morse Theory, Annals of mathematics studies. Princeton University Press, 1963.
13

---

[57] Atish Mitra and Ziga Virk. Hilbert space. Proceedings of the American Mathematical Society, 149(6):6633-2703 2021.
The space of persistence diagrams on points coarsely embeds into
[58] Marston Morse. Topologically non-degenerate functions on a compact n-manifold m. Journal d' d'Analyse Mathématique, 7(1):189-2000 208, 1959.
[59] Takashi Owada. Convergence of persistence diagram in the sparse regime. The Annals of Applied Probability, 3266):470--4736, 2022.
[60] Jan Reininghaus, Stefan Huber, UIrich Bauer, and Roland Kwitt. A stable multi-scale kernel for topological machine learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4741-4748, 2015.
[61] Bastian Rieck, Tristan Yates, Christian Bock, Karsten Borgwardt, Guy Wolf, Nicholas Turk- Browne, and Smita Krishnaswamy. Uncovering the topology of time-varying fMRI data using cubical persistence. Advances in neural information processing systems, 33:6900-699 2912, 2020.
[62] Vincent Rouvreau. Alpha complex. In GUDHI User and Reference Manual. GUDHI Editorial Board, 2015.
[63] Mohammad Saadatfar, Hiroshi Takeuchi, Vanessa Robins, Nicolas Francois, and Yasuaki Hiraoka. Pore configuration landscape of granular crystallization. Nature communications, 8(1):15082, 2017.
[64] Nathaniel Saul and Chris Tralie. Seikit-tda: Topological data analysis for python, 2019.
[65] Benjamin Schweinhart. Persistent homology and the upper box dimension. Discrete & Compu- tational Geometry, 65(2):331-364 2021.
[66] Umut Simsekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimension, heavy tails, and generalization in neural networks. Advances in Neural Information Processing Systems, 33:5138- 33:5138-515,, 2020.
[67] Ann E Sizemore, Jennifer E Chillip-Cremins, Robert Ghrist, and Danielle S Bassett. The importance of the whole: topological data analysis for the network neuroscientist. Network Neuroscience, 3(3):56--67) 2019.
[68] Yara Skaf and Reinhard Laubenbacher. Topological data analysis in biomedicine: review. Journal of Biomedical Informatics, 130: 104082, 2022.
[69] Philip Smith and Vitaliy Kurlin. Generic families of finite metric spaces with identical trivial 1 --imensional persistence. Journal of Applied and Computational Topology, 8:839-855, 05
2024.
[70] Anirudh Som, Kowshik Thopalli, Karthikeyan Natesan Ramamurthy, Vinay Venkataraman, Ankita Shukla, and Pavan Turaga. Perturbation robust representations of topological persistence diagrams. Proceedings of the European Conference on Computer Vision (ECCV), pages 617-635, 2018.
[71] Anna Song, Ka Man Yim, and Anthea Monod. Generalized morse theory of distance functions to surfaces for persistent homology. arXiv preprint arXiv:2306. 14716, 2023.
[72] Guillaume Tauzin, Umberto Lupo, Lewis Tunstall, Julian Burella Pérez, Matteo Caorsi, Anibal Medina-Mardones, Alberto Dassatti, and Kathryn Hess. giotto-tda: A topological data analysis toolkit for machine learning and data exploration, 2020.
[73] Aad W Van Der Vaart and Jon A Wellner. Weak convergence and empirical processes: with applications to statistics. Springer New York, 1997.
[74] Roman Vershynin. Higl--dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018
[75] Alexander Wagner. Nonembeddability of persistence diagrams with p > 2 Wasserstein metric. Proceedings of the American Mathematical Society, 149(6):66332677, 2021.
14

---

[76] Jonathan Weed and Francis Bach. Sharp asymptotic and sinite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli. (5(4A)::620-26433 2019.
[77] Daniel Widdowson and Vitaliy Kurlin. Recognizing rigid patterns of unlabeled point clouds by complete and continuous isometry invariants with no false negatives and no false positives. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1275-1284, 2023.
15

---

Appendices
Outline of the appendix
16
Persistent homology
16
Distance functions, topologcaa Morse functions and generic submanifolds
17
D Proofs of Section 2
19
Proof of Theorem 3.3
23
The OT, distance between Radon measures
24
G Proofs of Section
25
Details on numerical experiments
39
Outline of the appendix
We recall some basic definitions regarding persistent homology Appendix B Appendix
define topological Morse functions and discuss some of the properties of distance functions to compact sets. We also detail the genericity conditions from 66 and prove Proposition 3.22 We prove
Lemma 2.1 and Theorem 2.2 in Appendix [D. and Theorem 3.3 in Appendix E We rigorously define
the partial optimal transport distance OT between Radon measures on 12 in Appendix F before proving Theorem 4.1 Proposition [4.2 Corollary 4.3 and Corollary in Appendix Gi Finally,
provide some details on our experimental setup in Appendix [ Throughout the appendices, we write C' C(a, b, to implicitly state that newly introduced constant C² depends only on some objects
a, ... (e.g. C' = (M)).
B Persistent homology
Although this work is only concerned with PDs with respect to the Čech filtration, 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 an even more general context.
Let f Rd + R be proper continuous function that is bounded below-e.g. the distance function to compact set. For E R. let X, f- be the sublevel set of f at level t. The collection (X,)eR is called filtration. Let i 2 0 be an integer. We let (X,) be the homology group of degree with coefficients any fixed field F (e.g. F = 7./27 is popular choice) of X For 8, the inclusion between the sublevel sets at levels r and s induces a map li,r,s at the homology level. We define the persistent Betti number
Br,,,( rk(u,, Hx(X,) Hx(())).
(10)
As shown in 22 Corollary 3.34], this number is finite. Informally, it represents the number of ith dimensional topological features present the sublevel set level r that are still present at level s.
Define the extended half-plane 220 = {u- = (u,, U2) E (R U (-oo, +oo))² -00 S un < U2 S {00} and & (u = (u U2) E R Uj u2 The collection of persistent Betti numbers (f)ms(f))) defines a multiset of points in Roe. called the persistence diagram dgm, (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 of little interest in the cases considered in this article]] To simplify notation and definitions, we let from
'The persistence diagram of degree i of the distance function to set has no point with infinite coordinates if i and a single such point if = 0 whose coordinates are (0, +00).
16

---

(fm,(() 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 f == {u = (W1 u2) E IR2 : < u2). which leads to the following definition: the space 'D of persistence diagrams is the set of all multisets a in $2 that contain a finite number of point in every quadrant Qu. u E 1
Note that while persistence diagrams capture key topologiaal 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 copology-centers dimensionality reduction technique. Other topological invariants have been proposed, some of which are complete, such as those from [77 52
C Distance functions, topological Morse functions and generic submanifolds
In this section, consider a special class of PDs those yielded by the distance function to compact set A C Rdd 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 1R4 + R. Morse function f is C2 function whose critical points x (points for which d f = 0) are non- degenerate (meaning that the Hessian of f at is non-degenerate). The index of the critical point is equal 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 sets ʃ (-000, un] and (- u2] are isotopic if no critical values are found the interval [u1, u2] and if f- [w1, u2] is compact. Second, if [w1, u2] is compact and contains the critical points Ti.... KK. then f f (-30, U2] has the homotopy type of f- (-20, (-20, U1] with cells ek
of dimension equal to the index of zy attached along their boundaries (see e.g. [56] for much more
in-depth treatment).
In such a situation, the PD (f) has a clear interpretation: the coordinates (u1, u2) of a point dgm; (f) correspond to the critical value of a critical point of index and i 1 respectively. Informally, the corresponding i-dimensional topological feature appears with the attachment of i-dimensional cell at value w1, and is "killed" by the attachment of a + 1)-dimensional cell at value W2.
The notion of Morse function extends to continuous functions with the following definition.
Definition C.1 (Topological Morse functions 58 be a contimuous function.
Let U C Rd be an open set and let f U: TR.
A point z E U is said to be a topological regular point of f if there is a homeomorphism à : V1 + V2 between open neighborhoods V1 of in RR and V2 of U in Rd with (00) and such that for all x = (II...., Id) E V1,
fo foo(x) f(2) + xz.
(11)
A point z E U is said to be a topological critical point of J if not a topological regular point of J.
A point E U is said to be non non-degenerate topological critical point of f of index if there exist an integer S i S d and a homeomorphism ő : V1 - U2 between open neighborhoods V1 of 0 in Rd and V22 of U in Bdd with d(0) such that for all (Z1....,22, ..) E Vi.
d
foo(z) = f())
Σ
2
(12)
3=1
j=++1
The function f is said be 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:
TThis corresponds to the set of diagrams of q-tame persistence modules as defined in 22
17

---

Lemma C.2 (Isotopy Lemma). Let f R - R be proper topological Morse function. Let a < b be such that f- [a. contains no topological critical point. Then f (-00, a] deformation retruct of 5 (-x,
Lemma C.3 (Handle Attachment Lemma). Let f R +RR
R be a proper topological Morse function. be such that fe c E) contains topological critical point except
Let E IR and for 21,...,, E (c), with 2j of index ij. Then (- (-00, $] with cells B", B",.... ....,,". Bih of dimension i attached, i.e.
E| is homotopically equivalent to
- U U...UB"..
Their proofs roughly the same as for smooth Morse functions -see 771 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 the PDs of the distance function dA to various compact sets A, called the Cech persistence diagram of A and denoted by dgm;(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 E IRAA as
Vda(y) - c(o((v))
(13)
da(v)
where (v) = {I E || = da (v)} is the set of projections of on A and c(T) represents the center of the smallest enclosing ball of a set T. When y E R satisfies Vda(y) = 0, y is called differential critical point of da. We let Crit(A) denote the set of differential critical points of dA. An adapted version of the Isotopy Lemma remains true, as shown in [43
< b are such that dı |a, b] contains no differential critical point of dR, then dz ( (-00, is a deformation retract of (- Consequently, any (M1, u2) E dgm,(() is such that u1, U2 & [a, b).
Lemma C.4 (Isotopy Lemma for Distance Functions). If0 0
00,10 b).
Without further assumptions, little else can be said regarding the topology of the sublevels of dA; in particular, there no equivalent to the Handle Attachment Lemma to control the changes occurring critical values.
However, the distance function dm to compact C2 submanifold C Rd turns out to be a topological Morse function in a "generic" sense, was proven by Arnal, Cohen-Steiner and Divol. Theorem C.5 (Genericity Theorem [ō). Let M be a compact C2 (abstract) manifold. Then the set of C embeddings i: M > IRd such that
1. the distance function du(a)= (RM) - T.. is topological Morse function,
2. for every z E Crit(M), the projections ama(z) are the vertices of non-degenerate simplex of Rd and belongs to its relative interior,
3. the set Crit(M) is finite,
4. for every E Crit(M) and every x E (=M(2), the sphere S(z, dm((2) is non-osculating M at in the sense that there exist 8 >> O and
such that for all y E Mn (xx,8).
2|| z I 211 + ally =
x:|2
(14)
5. there exist constants C > O and po E (0, 1) such that for every E (o), any point x such that d[ (x:) |I & p is at distance at most Cp from Crit(M),
is open and dense in the set of C2 embeddings M - Rdd for the Whitney -o-ooooooy.
When M is generic, the topological critical points of dm coincide with its differential critical points (see (6 Theorem 1.8]), and the Čech PD dgm; (M) can be related to the critical points of dm in the same way as for smooth Morse function. We are now position to prove Proposition 3.2 which we restate for the reader's 's convenience:
"The distance function da is proper due to the compacity of A, hence its persistence module is t-tame and the associated persistence diagram is well-defined see [2]]
18

---

Proposition 3.2 (Cech PDs of generic submanifolds). Let M be a generic submanifold of IR.. Then, for any integer O, the PD (g),(M) contains finitely many points. In particular. Persa (dgm,d)) < +o0 for all a > O.
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; briefly summarize it for completeness nonetheless. We do not distinguish between differential and topological critical values and points, they coincide.
The set (ri 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 and M if
b and [a, bj contains critical value. Similarly, M has the same homotopy type as M if > 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 dm. and there can be no birth or death of interval between them.
Let us now consider a critical value e > O and < < c such that dM'(c E, c + E| contains no critical point except for 2 Lemma states that Mo+e is homotopically equivalent to M with cells Bh, Bu...., B of dimension .,...., ig attached, i.c.
2 E (c), where 2j is of index iz. Then the Handle Attachment
Mo+E = U
Let 2 1. and let D&s be the dimension of the cokernel of H; (M + (M (where the map is induced by the inclusion): it is preciscly the number of births of intervals between and c c & (hence precisely at c) in the persistence module of degree of the filtration. Similarly, the dimension D, of the kernel of (M + (M=1(M*+5) is the number of deaths of intervals at c the persistence module of degree - of the filtration. A straightforward application of the Mayer-Vietoris exact sequence yields that D..6 b + D;-1,d .,d is exactly equal the number of i-dimensional cells among B" ..... Bix meaning that each i-cell corresponds exactly either to the birth of an interval for the homology of degree i, or to the death an interval for the homology of degree - 1 (in particular,
1-cell and an é-cell cannot "cancel each other out"). This proves
that for any 2 1, the multiset of critical values (2) of critical points of M index i is equal to the multiset
{un (u,, U2) E dgm;((M 21 * 0} U {w2 : (W1, U2) E dgm;--(M).
(15)
This fact proves in turn that dgm, (M) is finite for any i 2 0, which immediately implies that Pers, (M)) < too for all a > 0.
D Proofs of Section 2
For M a m-dimensional differential submanifold of I2d and x M, we let T.M be the tangent space of M at z, which is identified with linear subspace of RR.. We denote by T. Rdd - T,M the orthogonal projection on this subspace and let म. id मN the orthogonal projection on the normal space at ar 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 E M,
|x - v12²
|| (x b)ll S 2T 2T(M)
(16)
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 unique at critical point, must have wfs(M) 2 ((M).
We first prove Lemma
Lemma 2.1. Let M C ddd be compact submanifold with positive reach and let A C M be compact set with (A, M) < 8 for some > O. Let E Rdd, Then, [dua(z) - da(z)l s da(z) 7M)
2dh(() 1
19

---

Proof. As A C M, we have (z) I dz(2). Let x be projection of 2 onto M, and let y E A be point at distance less than from x. Then, using (T6) and the fact that 2 orthogonal T, M.
we obtain that
da(2)² & ||2 - y/1² = ||2 - a²12 + || - ul12 + 2(2 x,, x v)
I dm(z)² + =² + 2(2 Ir a (x -1)
s dm(z)² + + dm(2)e²
r(M)
Hence,
da(z) dm(z)= da(z)² dm(2)²
E² da(z) + dz(z) - 2dm(22)
(1+ dm(z)
r(M)
We can now prove Theorem 2.2
Theorem 2.2 (Improved Bottleneck Stability Theorem). Let M C IR be a compact submanifold with positive reach and let A C M be compact such that du (A, M) I (MM) Let i 2 0 be an
integer. Then dgm; (A) is the union of three regions dgm; (1) (A) == dgm; (A) n [u1, U2 S F(M) }.
dgm; (2) (A) = dgm,(A) (A) n {ur S u2 2 ((M) -(MJ } and dgm; (3) (A) dgm, (A) n {ui, U2 Z
r(M) 7(M)).
Furthermore, let C =
2 (1
7(M) ). where R(M) is the radius of the smallest ball that contains
ROM;
r(M]
M. There exists an optimal matching : dgm, (A) U on - dgm,(M) U 0n for the bottleneck
distance between dgm,(A) (A) and (M), such that
Region (1): If E dggm (1) (A), then r(u)= E OΩ and ||u - ((u)llo Se.
Region (2): If u E dgm! (A)), then (u) is of the form (0, v2) and Iu2 u22 s C The number of such points is finite and depends only on M.
Region (3): If E dgm (1)
(A), then I|u - 7()) S C
Proof. Proposition 5 from (7] states that if = (A, M) < (V2 - 1)T(M), then the offset A deformation-retractt onto M for any
+ E (T(M) VA), (T(() (MM +8 + VAi
2
and A r(M)²- (M) - 5², Under the stronger assumption that d (A, M) < <MM)/4 and using elementary calculus, we find that the offset A" deformation-retracts onto M for any
g2 T(M) T(M)
r E
7MM)
This means in particular that the homology type, hence the homology, of A" 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 + z²
T(My and r(M) - and all (u1, u2) E dgm; (A) must either be such that 2
2 W1, U2 S + F(M or #n S + 7(My 22 2 T(M) - 7My or W1, U2 2 (M) (2) (A) and dgm;
2
22
7(M)- This almost
proves that the partition of (A),(A) into dgm; (1) (A), dgm;
(3) (A) as defined in the
statement is correct, except that the definition of dgm (2)(A) requires that #1 S E, whereas we only
have obtained that u1 < E + -(M)
Let y dgm,(() U 0 + (M) U 82 be any optimal matching for the bottleneck distance: then the Bottleneck Stability Theorem states that any point u = (u1, ug) dgm; (A) is such that
||u - >w))l>> (A, M) S e. Suppose that u is such that S e + -(Mj and u2 2 T (M)
_2
7(Mj-
20

---

Its distance in the infinity norm to the diagonal ön is equal to (u2 -21/2 2 (T(M) - 2=²/T(M))/2 2 IE
5 (MM) > E, where we use the fact that E < 7MM /4. Hence 7(u) must belong to (M). Let (01, 12) denote 7(u). As in the proof of Proposition 3.2 the Isotopy Lemma shows that (M) only contains two types of points: points of the shape (0, W2), which correspond to the homology of M itself, and points of the shape (w1, W2), where in both cases W1, W2 are critical values of dm. In particular, both wi and w2 must be greater than wfs(M). Let clgin (gg (M() (M) denote the multiset of all points of the first type, and dgm, (M() denote the multiset of all points of the second type. If U1 was non-zero, it would have to be greater than wfs(M) 2 r(M). and we which would be
would have ||u (u))lo 2 |m1 v1l 2 TMM)
F(MY 2 (M)/2
ea
contradiction (we once again use that E < 7 /M) Hence i must be (i.e. 7(u) E dgm ( (M)). (M)) and |0n 11 s 1|u 7()) lcc S c. This proves the correctness of the partition into regions from the statement.
Consider now v = (u,, u2) E ddgm () (A). All = (v1, E dgm; (M) are such that
E²
(1 (1-4 16
11 > E 2 ||u lo)
|/2 01/00 2 U/2 U2 2 wfs(M) -
7(M) 2 TM)
hence 7(u) must belong to an This completes the proof of the first bullet point of the statement.
We have already shown that if y is an optimal matching and u E dgm; (2) (A), then 7(u) E dgm,(M) is of the form (0, v2). As y maps at most a single point of dgm, (2) (A) to each point of dgm; (M). the number of such points is upper bounded by the number of points of the form (0, v2) with 2/2 2 wfs(M) in dgm,(MM Though dgm; (M) need not be finite (M is not assumed to be generic), applying Corollary 3.34 from [22] to dm shows that dgm, (M) is q-tame, and in particular that it contains only a finite number N of points (11, 02) with v1 S wfs(MM)4 /4 and 12 2 wfs(M)/2. Hence the cardinality of dgm;
(2) (A) is bounded by N.
only remains to show that y can be chosen such that if u = (w1, u2) E dgm, Ce? To that end, remember first that as shown above, our starting optimal matching y must be such that points in dgm;
(2) (A), respectively
uf E dgm, (3) (A), then |ug - 7())2l s CE?, respectively || - (x))
(2) (A) must be matched to points dgm, (2) (M). Conversely and for the same reasons, points in
dgm (2) (M) must be matched to points in dgm (2) (A). Similarly, points u E dgm," (3) (A) can only be
matched to points in dgm! (3) (M) to the diagonal 8Ω; otherwise, [/) 2 |M1 ( = u1
would be too large. Likewise, points in dgm; (3) (M) can only be matched to points in dgm, (A) or to
the diagonal. Hence 7 defines disjoint submatchings
(2) dgm;
(2) (A) + dgm; (M)
and
(3) dgm;
(3) (A) U Un + dgm; (3) (M) U an
Now let R(M) be the radius of the smallest ball that contains M. and consider the functions
a Bdd + R, x + miinmmax((a(e) R(M))
and
Rdd RR. x - min(max(dm (m)) R(M)).
Let us compare the persistence diagrams (a) and dgm.(m) of the sublevel sets filtration of a and m and the Čech persistence diagrams dgm,(A) and dgm, respectively (which are by definition the persistence diagrams of the sublevel sets filtration of dA and dm).
Note first that dA and dM 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 L E [r(M)/2, R(M)]. the sublevel set a a--((=o, xo, E) is exactly equal to (- t] = At. Consequently, dgm,(a) contains exactly two disjoint types of points. The first type are points of the form /M/ Mz)) which are in bijection with the points (1i, u2) E (A) with in < T r(M)/2 2 (the bijection maps (u,, u2) (r(M)/2, u2)); those are exactly the points in dgm (2) (A). The second type are points of the form (ux, u2) with 11 2 (M))/2, which are in trivial bijection (the bijection is the identity) with the points in dgm,(A) (A)
21

---

that satisfy the same condition; those are exactly the points of dgm (A). (A). The points of dgmm (
(A)
cannot be "seen" in (g),(a). We will call dgm (2) (a) the subdiagram comprised of the points of the first type, and dgm (3) (a) the subdiagram of (gm,(a) comprised of the points of the second type.
Similarly, (m) contains two types of points: the first type are points of the form (T(M)/2 U2), which are in bijection with the points (0, 02) E dgg,(M) (the bijection maps (0, 02) + (T())22, 22)); those are exactly the points in dgm
(2) (M). The second type are points of the form (UI, (2)) with 2 (M)/22 which are in trivial bijection (the bijection is the identity) with the points in dgm,(M) (M) that satisfy the same condition; those are exactly the points of dgm; (3) (M). We will call (2) (m) the subdiagram of dgm, (m) comprised of the points of the first type, and dgm, the subdiagram comprised of the points of the second type.
dgm,
(3) (m)
Recall that Lemma 2.1 states that (dm(2) - da(=) S 2da(z) (1 du(=)
+²
for any Rd M. If
7(M)
E IR is such that dz(z) < 7(M)/2, then th)n m(=) T(M) /2; if it is such that dma(z) 2 R(M),
then a(z) = m(z)= = R(M). Otherwise, dm(2) 2 dA( M) 2 r(M) 4 and dm(22) = R(M). hence
8²
1+ dm(=))
28
(1+ R(M) ) Co.
(dm(2) d^(=)l S
S TM))
2dM(2) where C' is as defined in the proposition. This means that
T(M)
7M))
||m - allco S Ce?.
Due to the Bottleneck Stability Theorem, the diagrams (a) and (gm,(m) must be at bottleneck distance less than Ce
Furthermore, let denote (A) I/u - (u) The matching y (and in particular the submatchings 7.(2) and 7)()) also induces (through the correspondence detailed above between the points of (g)n(() and a subset of the points of dlgm((A) a matching ? between dgmm(a) and (mm,(m) such that maxuedgm, (a)uen I|u - ?'())ll S 6. Hence the bottleneck distance between (a) and (mm) is most min(6, Ce?).
Let B dgm,(a) U a - dgm,(m) U an be an optimal matching for the bottleneck distance. For similar reasons as for y, the matching / can also be decomposed into two disjoint submatchings
g(2) dgmn (a) + dgmm (m))
(2)
and
g(3) : dgm (a) U an - dgm;
(3) (m) U M2.
We can use the two matchings (22) and g(3) define new optimal matching 7 dgm,(A) U82 - dgm,(M) U an as follows:
* The points in dgm!" (A) are matched by 7 to 0n as with y.
Given u = (ui, U2) E dgm? (2) (A), let u' = (T(M) u2) be the point of dgm
(2) (a) with
which is in bijection. We let 7 match with the point (0, 02) E dgm, (2) (M) which is in bijection with (1') = (T(M)/2, o2) E dgm? ( (m). Then |u2 - U2l I min (8, Ce due to the optimality of 8, and this defines a bijective matching 7(2) dgm (2) (A) - dg (M). Note also that max wedgmm?") (a)
(A) |u1 (w) max Eddgm ( (A)) "1 max (2) [u1 (2) (1) hence max wEdgm!?) ||u (2)) S
We have seen that dgm (3) (a) dgm! ( (A) and dgm (3) (m) dgm (3) (M). We simply
define the restriction and corestriction (3) dgmn;
(3) (A) U 0 + dgm;
(3) (M) U 82 of 7 as
being equal to g(3) dgm (3) (a) U an + dgm, (3) (m) U UN. The optimality of 3 implies that max wEdgm (9) (A) ||u 7(u)]l S min (6. Ce2).
Thus the global matching 7 dgm,(A) an - dgm, (M) U 09 is well-defined, is optimal for the bottleneck distance, and satisfies the conditions stated in the proposition. This completes the proof.
D
22

---

E Proof of Theorem 3.3
We prove Theorem 3.3 which we restate for the reader's convenience:
Theorem 3.3. Let M C Rdd be a generic compact submanifold and A C M be a (6, (..5)--esss set in M for some e, 8 > O. Let 2 e/8 and let i Z 0 be an integer. There exist Eo depending only on M
and Co, C2 O2. C3 depending only on M and a such that if S Eo, then dgm, ( (A) has at most Co points for all p 2 1, a 22000 0,
OTgidgm, (A), dgm, S Cjea-m (dgm;()))) S C2(C3 + +--=-)
(8)
Proof. Let us first prove the bound on the cardinality of dgm (8) (A). As M is generic, Theorem 1.6
from [6] states that if is smaller than some Eo Eo (M), then each point in Crit(A) at distance more
than r(M) /2 from A must be at distance at most ei from one of the finitely many points of Crit (M) for some K₁ = K₁ (M). Corollary 1.7 from the same article then states that the number of points in (A) at distance less than Ki from a given point of Crit(M) is upper bounded by some constant that depends M and the ratio // 6, 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₂ = K2(M. a) and K3 = K2 (M, a) such that I Eo. then there at most K₂ points in Crit(A) at distance more than 7 rM))2 from A, and each has at most K3 projections on A.
Lemma E. below, applied to the interval [T(M) /2, oo) and the set A, then states that the number of points in dgm,(A) (A) such that at least one of their coordinates is greater than T (M)/2 is bounded by K2( K3)
(++1) + (x Hence there are at most Co == K22Ks 2 k2(((()) (2) + (#42)) points in
dgm;
(3) (A) when E I Eg.
Now let us prove the bounds on (dg,,,,,(A), dgm,(M) and Persa (dgm, (A)). As stated in Theorem 2.2 which applies as Eu < TMM) /4, each point (u1, u2) E dgm?" (1) (A) is such that its coordinates satisfy 0 S U1, U2 S
S 2r. 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 2z. The homology of the offsets A' 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 a at the corresponding filtration value in the Čech complex, and each such apparition causes at most a single death or birth. simplex appears before filtration time 2s, it is by definition contained in ball of radius 2s, hence it is of diameter at most 4s. Let us assume from now on that En S 7 7MM)/16 /16. Consider x E A; then 2 Proposition 8.7] states that the intersection B(x, 4z) n A contains at most K₃ K2(=/5)m* < K₃a' points for some constant K₂ = (M). Hence x belongs to at most 2* simplices that appear before e, and there are at most #A 2Kaa such simplices. As the cardinality #A can be bounded by Ks/5m for some K₃- K5 (M), we find that # #(dgm (1) (A)) S Ke/5m for some Kg (M,M. a).
Furthermore, when M is generie, Proposition 3.2 states that its PD dgm,(M) has a finite number of points. Let be an optimal matching between dgm, (A) and dgm, (M) for the bottleneck distance
that satisfies the conclusions of Theorem 2.2 We find that any point E dgm (2)(() (A) is matched to
(2) point of Ue at distance at most ε from u. Moreover, the number of points in dgm, (A) U dgm (3) (A)
bounded by some constant K;- = (m a), and they are all matched to point of dgm, (M) or 0o
at distance at most e. In particular, these finitely many points are at distance at most Kg = Kg(M)
from H.. Furthermore, this matching is surjective, in the sense that y matches all points of dgm,(M)
to point of (A). As result, for any 2 1, we find that
(A), <
Σ ("dgmn
1 (u)-
Σ
Iuu - (w)13
eddgu! (2) (A)Udgm (A))
< Kgō Ko8-m + Kge" < K m + KyeB < c
23

---

for some C₁ C1 (M. Likewise, for any a 2 0, we have that
(dgs,,
Σ
pers(u)"= +
Σ
pers(u)
wEdgm (A)
medgm; ( (Ajudgm! (A)
S Kōō the ed + KgKg S Kaa" + K & C2(C3 + =
for some C2 C3 = CM(M). This completes the proof.
Lemma E.1. Let A C Rd be a finite set, and let a < <be RUI (-o0, too} and 2 0. Let
ÚC,- Crijnni j=1
be a covering of the set of critical points of dA whose critical value belongs to [a, and let
N₂ = # (U #EC,
be the cardinality of the union of the projections of the critical points C,. Then the number of points dgm,(A) such that at least one of their coordinates belongs to (a, is upper- bounded by Ej (411) + ( hence by E N
upper-bounded
Proof. It is shown in [5] that the distance function to any finite point cloud is a topological Morse function. Hence its topological critical points are in bijection (via their critical values) with the non-zero coordinates of the points in (the union over all degrees of) the Čech persistence diagrams of A. The number of points in dgm, (A) such that at least one of their coordinates belongs to [a, b] must then be upper bounded by the number of topological critical points z of topological Morse index or i ++1 such that da (=) E (a, b). Moreover, it is also shown that the topological critical points of da subset of A U Crit though not all differential critical points need be topologically critical. Hence any such belongs to Cj for some E {l..... L}, and (A(2) C CUveo (A(2').
As shown in [5, if is of critical index i, then the linear span Span(ox(2) 2) is of dimension i. By Carathéodory's theorem, there exists + 1 affinely independent points a= C U=+ec, (=(=)) such that z belongs to their convex hull. Those + 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. Henee there an injection from the topological critical points of A index that belong to Cj into the set of subsets of cardinality i + of Usec, (2(2'). Applying the same reasoning to the points of index
i 1, find that there are at most > coordinates in [a, 6). desired.
(+11
N N, points in dgm, (A) with at least one of their
(42
F The OT, distance between Radon measures
Let M denote the space of Radon measures on Ω, and let us define Q := {u (u1, u2) R² U1 I u2]. We call π an admissible transport plan between 1/, 1/2 E M if is Radon measure on
Ω x Q such that for all Borel sets A, B C Ω
T(A x 22) (A) and x(1 x B) (B)
(17)
For p [L, +oo), we define
/f ||u dr v) E ERU(+oo)
inf =EAdm(en v2) (2,,
(18)
where ||u]|oc = max(/uuh, |uz)) and Adm(U1, 12) is the set of all admissible transport plans between Vn and V2. We also define
(1,, TEAdm(P))1))
inf
sup - o/1o0 (u, v) E Support(T)}
(19)
'hen a -00, we commit a minor abuse of notation by writing (a, b] rather than (a, 6). and similarly when b +00.
24

---

For all E [1, so], the infimum is in fact a minimum (see 133 Wasserstein distance between 1/1 and V2, 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, OTp allows for some of the mass of i and v2 be transported the diagonal aQ == {(u, u) E 1R²,, which acts as an infinitely deep landfill. The p- Wasserstein distance is a distance on the space Mp = {u E M: OTp(2, 0) < oc), where O denotes the null measure.
We call (Tp((1. the p-
As explained in Section 4 a PD a can be identified with the Radon measure Evea 6n. Let Dp be the set of PDs being in My, 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 Equation (3), and likewise for the case p
We require the following lemma from 33
Lemma F.1. sequence of measures (Vn)221 converges with respect OT 10 some measure if and only if the sequence (Vn)nzz converges vaguely towards v and (Va) + Persp(v) as n + 00.
G Proofs of Section 4
We start with the proof Theorem 4.1 which is split into series of lemmas, before proving Proposi-
tion 4.2. Corollary 4.3 and Corollary 4.4
Let us restate Theorem for the reader's convenience:
Theorem 4,1 (Law of large numbers), Assume that P has density f on M bounded away from 0 and 00. Leti 2 be an integer and let 1 S p < cc. Then μ.f.s Mp and B (f,i)l Furthermore, for all a > Pers, (dgm) (1) ()) (An))m=
21020
(pn,s) Pers, (p + 01 (1).
Before proving Theorem 4.1 we state 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 be a probability measure having a density f on M satisfying fuin S. f S. fuue for two strictly positive constants fuim fmaxe There exist constants C.n: Cm depending only on m such that for all 0 S S TMM)4
Cmfuin Thhh S P(B(ar,))) I Imsue
(20)
Let An be sample of n i.i.d. observations of law P. Then, there exists = C(M) depending on M such that for all M and all >> 0,
P(d(r, A.) 2 S
(21)
Proof. For the first statement, see 2 Proposition 31]. Let us prove the second one. Remark that the probability is zero for diam(M). Hence, can assume that diam When 7MM)44 holds that
P(d(x, An) 2) = (1 P(B(z, s sesp--ncmfaan
When -MM)445 (M), we write
P(d(x, Am. r) PPd((, Am. > T(M)/4 S exx(p=ncmmmmmmm (m (TM))44)T) (T(M)/4)TM
exp( (-0C--Cmmmma diam MMm "
Hence, the result holds with = Cm min 11,
(T(M)/4)" chami(M5"
Proof of Theorem 4.7 Recall that Goel, Trinh and Tsunoda 42 have shown that almost surely, the
sequence of Radon measures (Mn,)) vaguely converges to the Radon measure ff,i We start by showing that, using this vague convergence and Lemma R. enough to prove the convergence of the p-total persistence.
25

---

Lemma G.2. Let (Vn)z21 be a sequence of random measures in Mp that converges vaguely almost surely a Radon measure v E Mp. and such that [[[Pers, (ers,(v)]] 7 Then, B(OTg(Un: v)] no 0.
Proof. Let us first show that (Dn)m21 = (OT 2))21 converges in probability to We use the following standard result: if for every subsequence (Zng )&>1 of (Zn)n21. one can extract subsequence (Z,, )(21 that converges almost surely to 0, then the sequence (Zn)n21 converges in probability to O. Let (Dm))az 222)1111111) be subsequence of (Da)a21 = (OTg(U,, v)) Then, as (Persp(y)))nn )21 converges in T,* to (vrsp(u), it also converges in probability. In particular, there exists a subsequence (n*, )121 such that (Persp(Un.,))l )2211 converges almost surely to Persp(v). 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.I. have Dnz, (4 v) --+00 0 almost surely, proving that actually have that (Pn)n21 converges in probability to To prove that E[D,,] > remains to show that the sequence (Dn)n21 is uniformly integrable. By considering the trivial transport plan that sends all probability mass to On, we have for all n
D S (v.) + (v)s
But the sequence (Persp 2> is uniformly integrable, as converges Lt, Hence, so the sequence (Dn)n21, concluding the proof.
Using Lemma
would follow from the facts that Ps E Ma and that ([] Persp(uu..) converges to
G
Theorem 4.1
Recall that (S2) is the set of continuous functions f Ω + with compact support (i.e. the support is bounded and at positive distance from M?). For s 2 0. let T, {(u1, u2) E Ω: U2 2 s}.
Lemma G.3. Let > O. Let (Vulaz1 be sequence of random measures in Ma that converges vaguely almost surely to a Radon measure v E M. Assume that the sequence of random variables (P)))22 is uniformly integrable and that
sup P.Persa < +000 and
lim limn sup.e( pers"(u)dun = $10000
Then, E Ma and (e((s Pers. 70 0.
Proof. We divide the proof into several steps.
1. Let é E (i)).. We first show that (f (dv,)))>2 converges in L to ódv. By assumption, the convergence holds almost surely. Furthermore, Φ is bounded and as the sequence (n,, (12))21 is uniformly integrable, so is the sequence (ʃ (dv%))21 Hence, EEI J ōd(1,, I +o 0.
2. Let (dx))²) be an increasing sequence of functions C.( that converge pointwise to the function pe Then, almost surely,
Jónde < iim n-000
/ éxdue < lim inf n00
/ pers
By Fatou's 's lemma, inf pers, dv/] S lim inf E Pers (vx) C < too by assumption. Hence, by letting i + oo and applying the monotone convergence theorem, we obtain (v) < C, proving that v E M..
3. The same argument can be applied to the constant function equal to 1, showing that v(22 < +000
4. Let 2 1. The function pers, can be decomposed into a sum of three positive continuous functions pers, 0.2² + o.²) 2 where of2) has compact support, the support of (2)
(3)
26

---

is included in the band {u E Ω: pers(u) 1/8) and the support of (3) is included in T..
Hence,
lim sup E| Persa (V,) Persa (v) lim sup E1| / df - 2)ll +-++000
+
/
lim sup Ei|
d(vn d(u, u)1l
limsup Bl| ((S)d(un - uV]]- カ-+00
n
The first term the above sum is equal to zero because of the first item, the second one smaller than s (sup,, E(u, v(2)), and the third one is smaller than
/,r pers, (w)de(u))
lim suspppi EE| pers,, (u)s,(u
Using the hypotheses of the lemma, the second and the third term converges to 0 as s goes to We obtain that lim supn-++o E[[Pers (v,) Pers, (v)l = 0.
Our goal is to show that the conditions of Lemma G.3 holds for the sequence (1n,))22 conclude. Remark that for any Radon measure v MM and 0
f pers p (u)du(u)= = [ voL (u: pers(u) 2 f))dt
T.
t t (TTx(( + a l/ ta v(-)d(Taddt
S a
(22)
1/2
< a
to v (s/2))v((T))
a/2
where we use Fubini's theorem for the first equality and the fact that {u pers(u) 2 f C T2 for the first inequality. We also have v([2) =To)). Hence, the different conditions of Lemma G.3 can all be obtained by controlling the random variable (n,i(T)) .) for s 2 O.
Proposition G.A. Let M be a compact submanifold with positive reach. Assume that P has a density on M satisfying Smin S. f S. fmax for two positive constants fmin. fmax. Then there exist c, C. > 0 that depend on M, i, fmin and fmax such that for all integer n Z 1 and all 2
BlJm,,(TT.) S C Cexp(-cs"))
(23)
Before 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 (2, (To) for 2 1 have a uniformly bounded second moment, and therefore uniformly integrable. Second, have (TP), Elun, (T,n,,(T.P00 (2/22 using Hölder's inequality. Hence, (22) implies that for any > 0, we have
/ go- ro-1Elun. (lu)).(TT2:)dd
E[Pers. (um.)) s
S savC 1 1a- 10-1e- -22" 1m dl.
In particular, sup,, E[Pers < too. Likewise,
V pers, (u)d Sa 1 a (T::)n +s))))+ (s. [T,)
sup IE
n
8/2
Savo 1 -02 dt /
80 that lim sup, Bifr, pers, pers, (u)din,
0. We are therefore position to apply Lemma G.3 proving the convergence of the o-total persistence. Together with Lemma G.2 with
1. we also obtain the OT, convergecee of pn,i. It remains to prove Proposition G.4
27

---

T(M)/2 be small parameter, to be fixed later. Recall that we write #S for the cardinality of multiset S. Notice that p (T,) 0 sm 1/m En + e (M). In particular, we may assume without loss generality that s I n diam (MammM)(1++))
Proof of Proposition G.4 Write En (A,, M). Let 2 0 and let Eo
n//"" Emax. / for otherwise there is nothing to prove. Consider the event E = { + (M) En}- By definition of Region (1), if E is satisfied, then all the coordinates of points of the PD dgm (1) (A,,) are smaller than Eg. Notice that the cardinality of dgm; (An) is smaller than the number of i-dimensional simplices in the Čech complex of An, which itself smaller than n²* 1 (as each simplex corresponds uniquely to choice of + vertices of An))
(M)
Hence
(T.) & n n 2 P(En + (M/ 2 ED).
require the following lemma, which bounds the upper tail the random variable en = du (An: M).
Lemma G.5. If S (M)/22 then
C.
P(dn M) >))
expl Sespl-nemJmaee
(24)
suin
for two positive constants Cms Cm depending only on m. In particular, for any q 2 1, du (An, M) O (m))
Proof. The bound pd (An, M) > r) is given in [ Lemma I11.23]. Furthermore, [ Lemma III.23]
also states that for any q > O, there exists C, depending on fmin and m such that, with probability at least 1 9/m du (A,, M) S C. (mm) 1/m particular, we obtain that
Inn q/m
Bid (Am, M)]] S C3
+ didaaaaMMa (aam(MM)n_9i 9/m
proving the second claim of the lemma.
Note that en S diam(MM, so P(en + /M/T(M) 2 Eo) S P(en 2 coeo), with co (1 (M))(M)/r(M)) -. Apply Lemma G.5 with CoEo to obtain that
Cm fminr
E El (T.) s ni
exp(-nem
Co exp(-cin)
for some positive constants C12 Co. Furthermore, recall that s S n 1 Emax. m Hence,
& C. cxe(p chepppc11mmm
Co exp(-c2s" ")
for some positive constant C2-
It remains to bound E[un, (T,)²1(E)) For each j = I,..., n, consider the set E/ of critical points E Crit(A,,) such that a,, (=) contains the point X, and sn 1/m S da. (z) S En + (M)T(().
Lemma G.6. It holds that (T,;((.)) smaller than
Σ
(25)
1=1
where Lj is the cardinality of the set UsEzi aA (2).
upper bounded by ΣØ= L By definition, this means that (T,) S Σ 1 as desired. 1/m 11m En = (+() yields that
Proof. Lemma E.1 applied realization of A and the interval [sn the number of points in dgm, (A,,)(A,,)) with at least one of their coordinates in [sn 1om-1/am 11m e, + 2 (M)] is
28

---

One can show that the set 2 is localized, in the sense that it is included in ball centered at x,, with radius depending on the sample A,, that is small with high probability. Hence, the number L is controlled by the number of points in A, found in a small (random) neighborhood of Xj. Let us make this idea rigorous.
For r 2 0, define the shape
llyl 2T (M)
C(r) = {y (yms Mddmm) E R x Rd-m; |yll| S r, I1ya-m -
}.
(26)
We build a partition of C(r) in the following way. Consider a finite partition W of the unit sphere in RM (0)d-m into sets of diameters smaller than @ at 4/4 (for the geodesic distance the sphere), which we fix for a given dimension m. Let W(r) be the partition of C(r) consisting of the sets
(u (Um, Vd-m) E C(r)= Dm/ Ilmmll E W),
where W is an element of the partition W.
For E M. consider an isometry lx IRd + Hd sending R x {o)d-m to T,M. Let C(x,r) x + Lz (C()). Likewise, we define a partition r(x,)) by applying the affine transformation W + lz (W) to each W W(r).
For j 1, 1,..., n. let Rin be the smallest radius S Eg such that every W W(X,,)) contains point of An other than Xj. By convention, we let Rjn- = if such a radius does not exist. Rjn can be made measurable with a good choice of x ++ tai we assume it to be the case henceforth.
Lemma G.7. Let Eo I 7M)/v2. For all i n, if E Crit(An) is such that X₃ E COAn (2) and dA. (2) S Ev. then |X - 2|| Rn for some positive absolute constant co.
Proof. Recall that for x E M, म. is the orthogonal projection on T,M M while _- is the orthogonal projection the normal space at Let 1, I...., and let 2 Crit(A,,) be such that X, E a (z). The direction& e = Tx, (= / xx, (2 - Xj)Il belongs to the unit sphere in Tx, M; note that xx, X,) * 0 due to Lemma G.8 below, which applies as dA, (=) S en S (M))/22 Hence, Ey (e) belongs to element Wo of the partition W. Consider the corresponding element W of the partition WX,,, Rzn).
If R Co. then the conclusion of the lemma holds (for cu = 1): indeed we have ||X; 2|l = dA. (2) S Eo S Ryn- Otherwise, by assumption, there exists a point X E W for some l # j. As X, AA (z), it holds that ||X,- - = S x|x z||. Hence,
1x, =12 < Xx - =112 = ||x; =1| + ||,, - 22 + - Xj, - 2)
and
(Xx - 10_X,,==- -),) < X XxI1
(27)
2
We write
(Xx X,,= -X,) = (Tx, (Xx Xj), xx, (=- X,)) + (T (Xx - X xx, (3 X,))
By construction, as the diameter of Wo is less than 0, we have (xx, (X2 X,), オx, (z - -X,)) 2
cos(T/4)||=x, (Xx - X,)Ill (a - X.)II On the other hand, according to 39 Theorem 4.18).
|| (Xx - -x,II 1 X,1
(28)
2T(M)
which also implies that ||=T,, (Xx - -X,)I 2 - 4r(M)2 Similarly, Lemma G.8 below
23
states that || X1)I| 2 ||=-X0 Xxy1/22/ and || (=-Xx))) -X,Il $ ||| X, / (using our assumption that dA,, (2) I EO S T(MM)/2).
29

---

Hence we obtain that
cos(T/4)|XX; Xxllll= - V -xlll
I cos((T/4)]l (Xx - -x)) XX, (2 - X,)I
V2
| - X,11?
||xx - -X,11 - X,1
2
2T(M)²
- || - x,1|² (1
o
+
2
2r LM()2
Dividing by |IX,, Xxll and using that -
X < R, and that Eg S 7 (M)/ /2, we see that || - Xyll is smaller than Rjn up to an absolute multiplicative constant.
We now prove the lemma used above:
Lemma G.8. Let A C M, E Crit(A) and o2(2). Then I x)1l S || xM])/ Furthermore, if (x S (M)/ then [ =) 2 |= =11/v2.
Proof. The point = can be written as a convex combination z Σx Auyii where the points y are in A M. Then, using (39 Theorem 4.18).
1lye 2012
|| (2 x) 1
d || (v+- -x)1l
Ak
2T(M)
k
A I1y - 2|12
1|2 1 2 2,
x)
||2 x1|
2T (M)
r(M)
as llye -1 2| and Σx (uk 2) = 0. The second inequality [| x)]| 2 112- /v2 from the statement follows from the first one through direct computation.
Let us now show that the random variable Rjn. has controlled tails.
Lemma G.9. For all x E M, r 2 0, B)x,r) n M c C(x,r).
Proof. Let y E M be such that [T x) S r. Then, according to [39 Theorem 4.18), || (y [y=2||3 In particular, B(x,T) M C(xrr. 2r(M)
<)]l
Lemma G.10. For 0 < <M)) and j 1,..., n, we have TP Rij > 1) S Cine -on 1ye" for some positive constants Cmo C.-
Proof. If Rin is larger than then there exists at least one set W E WWX,,, such that intersection with An contains only Xj. Hence,
P(Rjn > t|X,) S
Σ W)
P(An nw = =X,XX))= =
Σ (1- ((-P(W))~- WEW(X,,.)
Let no be the orthogonal projection from Rdd R. d0]d-m The image of set W W(X,, by the projection y + (y X,) is equal to 1x, (wn(W)) c Tx, M for some Wo E W(t). For < 7MM)44 the orthogonal projection y E B(X,, t) n M + πx, Tx, (v- - X,) E Tx, M is diffeomorphism on its image, with Jacobian lower bounded by constant cm that depends only on m. see e.g. [31 Lemma 2.2]. According to Lemma G.9 the preimage of 4x, (To(W)) C Tx, M by this diffeomorphism is equal to W n M. Hence, by change of variable,
P(W) = P(W n M) 2 fminCm Volm (Wo) 2 Smin
for some dm > 0. Hence,
F(Rgn (1x)) < #W Smin mm-m (n
We conclude by taking the expectation.
30

---

Let us now control the number of points found in ball B(X, KRjn) for some 2 0. Let Pu > 0 be small enough such that B(E f 1/2 for any 2 E M.
Lemma G.11. Let 1 2 0, be such that keo I min(po, - (M)/4). For j =1,1,-- . n, let K Kinn Kin((s)) be the number of elements of An, found in for some constant Cm,, which depends on m and I.
Then, jm S (1d(1+ Smmax k!/)
= W(X,, MKX,,KRjj kRja). Without loss of generality, we can assume that 2 K 1, otherwise the bound is trivial. As in 34 Lemma 5], we remark that there is at least one sample point in every W, and that there is (almost surely) one single clement W,, of the partition with exactly sample point on its boundary. Let N, be the cardinality of (W; O A,)) (xx)) and N-1 be the cardinality of A, B(,,, RRja). Define
Proof. Let us write
ās = L
W.
and a; = I-a,- for all + i", as well as a- 1- 1->: ā. Note that as KRjn S Po: we have I-a c; < 1/2 for all - J...,,K K. As kRin I KEO < (M) we may use once again that the orthogonal projection y E B(x,, KRjn) M πx, (v X3) Tx, M diffeomorphism its image, with Jacobian upper and lower bounded by constants depending only on m (see 31 Lemma 2.2]) also obtain that
(f S ã, S C'fmax(XR
for all i = I,..., K and some constants c(m), C C(m). Hence there exists C" CC 0 such that
(Iiil(iiBjnn)) " a, S C' fmax
for all i 1, .. K. Consider multinomial random variable L (Li,..., Dr.... LK, L-) of parameters 2 and (a1...., dut ..... (KKa-1). and let E' denote the event
[1: 2 1vie (1..,)11,,,))11))))
Then conditionally on Xj. Rin and i*, the variable N (Ni,..., ...,..,, NK, N-1) follows the same distribution as L E. Thus, conditionally on Xj. Rin and W., the variable K Kjn (x) 1 Σ N₁ 2 ΣK Ei=,i N; (where the initial comes from X,) has the same distribution as
2
Σ
L.E. E.
im1.iih
Note that KRjn S Po. have a-1 2 1/2.
As result, Lemma G.12 below yields that
K Σ 4) E] 22 + B[(
K
Ryn Wir = E[ +
Σ
E)
1,
i=1,8
K Σ an)')
< 2 + CK.(1 + (n -2)
S Cki(11 + (n Σ
a:)' S Ck,((1 + (nKC' Smax (1.j))
i=iiiii"
s Cm,(1 + mm fla Rij!))
where CK., Ck,, and Cm.1 are constants whose dependencics are indicated by their indices (remem- ber that = #W depends only on m)) We can now conclude by considering
[ (nnnnt (K)²1 = Ex, Ry., W.- [E[K5n (x))) Rins W S ER,, [Cm, + ml pl flane 12ml)) ]
31

---

The quantity n2E [ is bounded by a constant, which is proved by integrating the tail bound found in Lemma G.10 Indeed, Lemma Lemma|G.10 impliess that the random variable n jn is subexponential with a subexponential norm m independent of n, of order O(1/fmin) the moment of order I of such random variable is bounded by Cim', see 74 Section 2.7].
Let us now prove the technical lemma used above.
Lemma G.12. Let K 2 and = (Li,..., LK,, LK+1) be a random multinomial variable of parameters and a1 ....... .....
KK, aK+1- Then there exists C = C(K,)) such that
KJ S Ci(1 (n
an)
Proof. Let X1...., Xn be i..dd categorical variables of parameters Ciyy.., OrK 0K+1- De- fine (p(p) = Erso 1x,=ki then (z)....... Lx (n), (x))(a) has the same distribution as (In...., LK,IIK Ix+1), and we identify the two in our notations. For a fixed and for any injective function (: (l....... [I. .I....,ii. n]. consider the event
E, (L((((1) -,...., -,,..,,,((((()))) =}}
i.e. ((i) is the first appearance of i among the variables XI...,, Xn. Note that E == (Li,..., Lx 2 1} = L1 E, where the sum is taken over all such injective functions. Then
BIC
L.) LYJEJ
Σ
P(EEEE)
L L.E.
Fix a function and assume without loss of generality that <(1) < (2) <... < ((K). Conditioned by (1++))11 (+)+ 1 is a binomial variable parameters (i++1)-
A., the variable Y; = >
Dim az and an +... a tak+) Ei= a, Hence E|Y;" E.] < (1() Σ a.)" using classical bounds on the 1-th moment of a binomial variable, and we see that
K
K
((t+)-1
E[( E. E(O
1x E. + Σ Σ
1x.+K+M\|E.
im r=((i+1
K (n
< C((K,))(K)
Σ
as)")
1=1
where we write <(0) 0 and (KK + 1) to simplify notations.
Let us wrap things up. Recall Lemma G.6 it holds that
nn, (T.) S
i+2 1j
(29)
1=1
where Lj is the cardinality of the set USE3! aA, (z). But according to Lemma G.7 if E E
then ||X,- =|| S colinn In particular, da,, (z) < coRjnn and any point y E OA. (z) distance
less than R0,R from X,. Hence, Lj is smaller than Kzn(k) for k = 20p- Choose en so that
KSp < KEn < min(po. 7 7M)/4)) We are in position to apply Lemma G.1 We further remark that
Lemma G.7 implics that E/ is empty if Ro < sn -1/m
32

---

Hence, by Jensen's 's inequality.
27
Blun, (T.)²1{H s E
1 1220olinn 2 sn 1/m Knn (0):n(22)))) (2co) j+2
E
1 2 on 1/m Kin (2c
)20)) 2i+4
PPccooBjn sn /n-1/mmB[Kinn (440)
I Cm.i exp(-cm Iminnin"
for some constants Cm Cm O, where we apply Lemma G.10 and Lemma G.1l at the last line.
This completes the proof of Theorem 4.1
We now prove Proposition
Proposition 4.2. Let M be a generic m-dimensional submanifold. Assume that P has density on M bounded away from 0 and Dc. Let Z be an integer. There exists an optimal matching In dgm,(An such that for any q 2 1:
UuN UnN + dgm, (M) the bottleneck distance between dgm, (An) and dgm,
Region (2): It holds that max
wEdgm!" max (A.,) ju2 (u())2l On
Regiio (3): holds that max ( ||u ma(u)llo Oze (n and
#(dgm; (Am.) (1)
Proof. Let En = d M). Let IIM := fo E 0M(2): : E Crit(M)) be the (finite) set of projections of critical points 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 = E Crit(A,.) far from M and their projections E on, are stable with respect to the Hausdorff distance, meaning that every such point 2 is at distance (E,) from a critical point 2' E Crit with x being at distance O(e,) ).) from point x' 1l.. Thus, the number of critical points of An located close is crudely upper bounded by the number of subsets which can be formed by selecting elements in neighborhoods of size O(e,) around x' (=)). We used the same idea to bound the cardinality of
given z' Crit(M)
dgm; (3) (A) in Theorem 3.3
In a random setting, the distance E, is of order (Inn/n)1/m as suggested by Lemma G.5 while the number of points found in ball of radius is typically of order nr" yielding logarithmic number of elements in a neighborhood of size (e,,) around a given point x E M. Hence, our earlier strategy not tight enough bound in expectation the cardinality of dgm, (3) (A) by constant.
We improve upon this strategy with the following intuition: the maximal distance between point of M and the point cloud A, does not really matter in 6 Theorem 1.6), but only the density of the point cloud A,, around the (finitely many) projections x E II Although is of order (In n/n) I/m the distance between fixed point x E M and A,, is known to be of order n -1/mm (see (2I)). This remark explains how we can intuitively replace neighborhoods of radii (Inn/n)//m by radii of size n- -1/m the previous arguments.
We now make these ideas rigorous. Let Crit, (A,) {= Crit(A.)) dA, (z) > ((M/2) denote the set of critical points of A,, "far" from and let IIA,, := {ar oA, (=) 2 Critz (A.)) } be the corresponding set of projections. We let Eo be small constant to be fixed later. Theorem 1.6 from [6] states that, thanks to the genericity of M, there exist K₁, K2 > 0 such that for Eg small enough, En Eg:
there exists a map Φ Crity (An) + Crit(M) such that d(z, Φ(x)) & Kien for all =
Crity (An), and
there exists map 2) II. + II such that d(z, (xx)) K2En for all r II
33

---

Furthermore, the map & is such that for each E Crit, (An) and each x' E o' there exists oA. (z) such that (z)) =z' (if Eo is chosen small enough). Indeed, due to the genericity of M. each critical point x' E Crit(M) belongs to the relative interior of (=(=") (as stated in Appendix C.. particular, cannot belong to the convex hull of any strict subset of (=()). By continuity of the convex hull for the Hausdorff distance, as soon as E Crit (A,,) is close enough to Φ(z) and its projections H E JA.., (z) are close enough to om (0(=)) (i.e. as soon as En is small enough), the point z cannot belong to the convex hull of any subset S C oA,,, (z) that does not contain for each r' E (m)()=)) at least one point a such that (b))) = x'. As z must belong to the convex hull of JA (2), we conclude that each z' (m))) has at least one preimage by & in oA, (2). As Crit(M)
is finite, taking the minimum distance such that this property holds for 2' over all 2 E Crit(M) proves the claim.
We introduce the random function defined as
Vr 2 0, E(r) == min(sup(da,.
y M (M) =: min(F(r),
(30)
where II is as usual the r-offset of IIM. This random variable measures the density of the point cloud An neighborhoods of size of points x' e IIM.
Let
Pn == su, (x) l
(31)
give (when en < Eo for So small enough) the largest distance between projection E TT and the corresponding projection (x)) E IT.. We also define
T/ sup(dun (z): x TM()), Crit (An))-
(32)
We require the following controls on the random variables Pn and Tn.
Lemma G.13. There exist positive constants so (M)) K3 K2(M), Ka (M(M) and K;- = (M(M) such that in < Eo, it holds that for any E Crit> (An)
Ida, (2) - d & Kg
(33)
T/ S kmm)),)
(34)
Pn S KsE(mn)
(35)
Proof. The lemma follows from 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 = T rM)/22 R = diam( (M). the Hausdorff distance E = d (An, M) can be replaced by (T),). Hence, if E Crit, (A,), there exists ju-critical point z' of M at distance less than (nn)). with /4 S L, (M) ((r)). By genericity, for choice of &o small enough, this point z' at distance L2(M) from a critical point 20 E CM)t For eo small enough, this point is necessarily equal to d(z), with - < (1+ (2-1))))
Due to the Lipschitz property the projection onto M around 2g (see the arguments found at the bottom of p. 19 in (6), any point x E (2) is such that ||æ x'Il < [>)M]]l d(2) for some x' om(o(2)). By taking the supremum over all such points x, we obtain that
Th S Ls(1+ +1++4) L2b))
proving 34
One can also check that en can be replaced by E(ma) in the end of the proof of Theorem 1.6 in 6 so that (35) holds.
Let prove
33
Let
Crity (An). Consider IA,, E OA, (2): know that [=(A,,)) As x1z) - (TTA,) is orthogonal to TM M,
IA.Il < KzE(TT) using
(33
M. [39] states that
|
((DA,) (IA.. (TTAA.) ))ll
||
v(a )1 < k( hence
2r(
2r(M)
[10(z) - I2..11 = [|+(2) - ( 21 + 2(((z) - (( ), (lTA.) IA.)) + [1(((xA))) IAA. 11?
5 dd()= + K K2E(nn)² d (d)))())) + KG 3 dha()(=))² + (2
(M)
where La K3 (2(M)
F(M) 1). R(M) is the radius of the smallest closed ball that contains M, and dm)) < R(M) because critical point must belong to the convex hull of its projections. As
34

---

the same bound applies to each of the projections z'A,. E JA, (2), we find that the closed ball B (o(z), dm(l(2))² Lss contains ar (2). Since is the center of the smallest ball that contains AA, (z), whose radius is da,, (z), we find that
dam (z)² dm( + E(.
(36)
Similarly, consider now IM E (m(()=)) and let aAA.. E (TM) n A... (z) (we have seen below the definition of and d that its existence guaranteed). We have shown earlier that there exists I E OM (M) such that || IM | IAA. S (()(T))) and the same reasoning as above yields that ||z - -AA 2 == =1|² (LE())) and ||z 2m|l² ||2 - x 1l2 + O (L)()))) (with all big O constants depending only on M), hence that || zmll I ||2 JAn. E(m ) Ls = dA.. (2)² + > Ls.
As before, this shows that the closed ball B (z, da, (z)2 + L( that
contains om(((2)), hence
dm()(2))² S da, (2)2 + En,. L This, together with (36) and the fact that dA,, (z) 2 7M))22 shows that Id (z) dm (+()))
(37)
S
(m)M))
Consider (random) optimal matching 7a dgm,(A,, U an dgm, (M) U an such that wedgm/"m! max (9,,) (A.) |u2 - 7x(u)2/ S Cez and max wedgm!") (A..) [|u. - 7n (w)ll I Ce whose ex-
istence guaranteed by Theorem 2.2 (for some C = C(M) 0). For r 2 0, we let (()) be the number of points of A, found in I (I.e. at distance less than from a point in TTa).
Lemma G.14. There exists Eg = (M( such that if em S Eo, then
max |02 - mm (u)21 S KgF((n)) "Edgm! ( (A..)
max wEdgmm (A..)
||u 7/1 (w)llo S KzE(n,)
Furthermore, # (dgm,
(3) ( )) is smaller than N (pn)
Proof. Let us assume from now on that Eo small enough that 2(K3 + C) is smaller than the smallest difference between two distinct critical values of dm-
Consider a point (u1, U2) E dgm (3) (A,) that is mapped by %n to the diagonal. The coordinates uj and U2 differ by at most Ce hence they are critical values of dA, that correspond to critical points that are mapped by & to two critical points of M that have the same critical value (due to 2(K3 + C) being smaller than the smallest difference between two distinct critical values of dm). But as stated in Equation (33) of Lemma G.13 these critical values must then be K3 (=.))=-closee to that of the two critical points of M, hence u To. (u)ll so = d(u, 02) = (u2 u1)/2 S Er),) as desired.
Likewise, consider point (u,, u2) of dgm; (3) (A..) that is mapped by 7/n to a point (ui, v2) of dgm, (3) (M). The birth coordinates #1 and V1 differ by most C=², hence the associated critical values must correspond to a critical point z of A,, and a critical point z' of M such that d(z) has the same filtration value as z' (again due 2(K3 + C)e² being smaller than the smallest difference between two distinct critical values of dm).. But as above, we have (u1 21 = Ida,, (2) dz)(2') Ida,, (2) dm (0(2)) < Em,.), As the same applies U2 and U2, we find that ||u - 7n (w) <
K KnEE())) and max uEdgm," (2) (A..) ||u (m)ll I KzE(m))² The same reasoning shows that wedgm (A..) Iug Tme (u)2l < Kn.(nn)?
max
Finally, and by definition, II far E AA (2): 2 Crit(An), da, (2) (MM)/2) is included in An n lfp. hence # (IIA,,) < (p.). Lemma E. applied to A, and the interval [T(M)/2, +o0) then yields that the number of points in dgm, (3)
(A.)) is smaller than N ((p))
Lemma G.15. Let En be the parameter defined in Lemma G. 14 It holds that for all q 2 1,
E(r) (sx S < O1=(r (n-1/mm and N [(En I <0) = Ozz
35

---

Assume for a moment that Lemma G.15 holds. Then, we write (for choice of Eu small enough)
max wEdgm (Aa)
|u2 - (o(2)2l 1022-((20
- (a.E(n)) I fo} R(M)1(En > Eo}
I (nm (00m)m))((e.) 1 1 =o} + R(M)1(En > Eo}.
(38)
where we recall that R(M) the radius of the smallest enclosing ball of M. Because of Lemma G.5
the random variable 1(en Eu] is a Oza (n-22 (n-mm for all 9 1. But then, because of Lemma G.15
we obtain that the right-hand side (38) is O (n 2/m) for all g 2 1. Likewise, we obtain that max uEdgm! (Am) ||u (n) Dc Oz 22/m) for all q 1. At last, we have
#(dgm; (3) (A..) (p.))*+
Ea) + n 1 > Eu).
The first term is OL= for all 2 1 because of Lemma G.15
while the second one is Og= (1)
for all g 2 because of Lemma G.5 This concludes the proof of Proposition 4.2 Let us now prove Lemma G.15
Proof of Lemma G.15 Let 0. The key observation to obtain Lemma G.15 is that implies that if > t, then there exists
with r - Er).
Lemma G.16. For all X > 0, there exist positive constants Cy cx (depending on X, and fmin) such that for all > 0, P(r S XE(r)) S Cx exp( exp(-cxnr"))
Proof. Remark that i S XE(r), then S AF()). The set MΩII the union of a finite number of balls of radius r. Hence, it can be covered by Cx (M( open balls of radius r/(2)), with centers Ti,.... #C,, E M. Note that if all these balls intersect A,, then for all y E M da,, (y) < r/>. then the intersection of one of these balls with A., is empty. Hence, according
Hence, if (
to Lemma G.1
C2 P (F(r)) S Σ P(da, (Tx) r2())) s CA
Remark that the fonction E is nondecreasing and 1-Lipschitz continuous: have for E(r) S E(s) I E(r) + (r s). Fix > O and consider the sequence ty = a for some > 1 to fix. Assume that 7a > and that En I Eg. Then 7h is between two values ta tk+1. But then, according to Lemma G.14
E(tx),
E(Tr))
(1m - tx)
E((m)
tu+1 (a-1)
1 K₂
(a 1)
to 1 [(Tm)
tk
a
?n
tx
E(tx+1)
1 [(mm)
tk+1
a
tk
a
On
K4a
Choose
such that
K4 (a
1) 0, and let
A = min
K4 (a - 1), K4a > 0
We have proven that if Eo and nn then there exists k 2 0 with E(tx) 2 Ats.
Hence,
P/) > 1,8n S 60) S SC Σ exp( exp(-cxa mm
k20
A standard comparison between this sum and an integral shows that this sum is at most of order
"e(n("")-lexxpp exp([Kxnt""
(39)
for two positive constants Kg. Ky depending on M and fmin. But when ntt < 1, we can simply use the bound Pnn, > t, En < E < 1. Hence,
P( > En < 50) < min(1, Ke(nt"))
S Kg exp(-Kent""
(40)
36

---

for two other constants Ks. Kg.
To summarize, have shown that the random variable nn ( S εo} is subexponential, with suhexponential norm depending only on M and Jmin. see e.g. [74, Section 2.7]. We will now simply say that random variable is subexponential to indicate that it is subexponential with norm depending only on M and fmin.
Lemma G.1 shows that the random variable rdd,, (x) th for fixed E M is also subexponential. Thus, so is (0) = nt max dA., (x) as a maximum of a finite number of subexponential random variables. As nE able (m,) (1 {En I Eo} is also subexponential. In particular, we have E(n,) [ S Eo =
n(m, E(0)) 2 2m='(nn" =))) the random vari-
O (n/mm) for all q 2 1.
It remains to bound N(p)). First, because of (35). the random variable ponential. Also, for fixed f, (t) follows binomial distribution of parameter n and P( As long as S 74M)/4, ball of radius t is of mass smaller than Cmfmaxt" (see Lemma G.1 Let n an integer. For any S 7 (M)/4, we bound
I Eo) is subex-
(p,) 2 h en S Ea) S P(N(() 2 k, Pr. 1)) P(pn > t, S ED)
S P(N(t)) 2 k) + 2 2exp( Klont"),
where 1i is proportional to the subexponential norm of 11pn S Eo). see 74 Section 2.7]. Let
l = (k/n)* ( 1/m min(r(M) 1/M#Il 20 1//m) This choice of ensures that / < 7MM)44
and that [t) $ m(#IIM Cm fmaxt I k/2. Then, by Bernstein's inequality 77 Theorem
2.8.4].
((N(() 2 k) ((N()) ([N( 2 k/2) - exp (-
12/8
(n((#llM) mm mm k/6
f exp k))
for some constant Kn depending on m, M and fmax. We have proven that for all k 2 0,
P(N(pa) k En S eo) 2 2xx (- K K11k) -exp(-exnnnnie )n
< 2exp ( kink) + 2exp(( (
for some constant 112 depending on m, M, suin and fmax- Hence, the random variable [(, S En} is subexponential, with subexponential norm depending M, fmin and fmax- This implies in particular that le, I co) = O1)(1) for all 2
Corollary 4.3 is a simple consequence of Proposition
Corollary 4.3. Let p and let < i < be an integer. Under the same assumptions as in
Proposition 4.2 the following holds:
1fp > m, then E (dgm, dgm, + 0 as 00.
p = m, B p (dgin, (A,)),
+ Persp(Woc,,tm))l as n + co, where
Vol(M) the volume of
.
Ifp m and < m, then (dgm dgm, (M)) +00
Furthermore, for all > 0, Pers, (dgm, (n))) is equal
(( (log 7
Persa (M)) n²= Pers, (Moo,t.)
((x)'-==a = dx on (m'-=) +0 MM f(x)²-
Proof. Let dh (An, M). Consider the event E (en < 7(M)/2). According to Theorem 2.2 on E, the number of points of dgm, (2) (A.,) is bounded by some constant No depending only on M.
Consider the optimal matching Yn given by Proposition 4.2 On the event E, this optimal
matching sends all the points of dgm;")) (1) (A,,) to the diagonal 0Ω. Thus, we have (when E is
37

---

satisfied)
10Tz(dgm, (An). (g), Persp (dgm, (1) (An))
ulu (n))ll + #(ggm) (3) (Am))
| (u)-m(u)lle. (41)
S No
max
max "Edgm (An)
"Edgm ( (An)
Furthermore, note that
max wEdgm (A..)
||u- (u)ll I max
max (2), (A.)
I12 .n (u)222 e
max
1/2 In (u)2 + e
(MI, (2)gm)) (An.
We take the expectation and apply the Cauchy- Schwarz inequaall to obtain (together with Theorem 4.1, Proposition 4.2 and Lemma G.5)
B[OTg(dgm; (An)));;(A) (M))
S 1 //-p//"PPnnn (p)) + o(1)
When E is not realized, we crudely bound (Tg (A,), dgm, by considering the matching sending every point the diagonal. The of this matching is bounded by CM(1 + n(+l), where *+1 is an upper bound on the number of points in dgm; (A.) and CM some constant depending on M. Hence,
( (A.), dgm, [E")] < CM(1 + nn'"")(PPe > 7(M)22 = o(1)
according to Lemma G.5 This proves the first bullet point.
The second bullet point is proved likewise from 441) Indeed, in that case, it holds that
(d (An),, dgmm (M)) - Pers, (ers, ( (dgmm/(A.m)))))mmccccc.eee( (Am) = o(1).
(42)
Also, using the same crude bound, we obtain that
E dg), Pers, (ers, (1) (A,))) o(1)
(43)
So far, we have proved that (dgm,, (An),, dgm, (M)) (drsp(dgmm (1) (An)) According to Theorem 4.1 holds that Pers,(dgum (A..) Pers, (uF,i) + oz (1) for
01 (1).
p m, proving the second bullet point.
For the third bullet point, we use that on the event E,
(dgm, (Am) (An), dgm, (M)) 2 Persp (dgm) (1) (An)).
(44)
The latter equal to nttp//mPerspl (prs/ + or (nt-p/m), with (ersp(urs)) > 0: indeed, the support of the measure μt is nontrivial for < m, 47 42). Hence, E(OTT(dgmm(An)) dgg) (M)) 2 [[T][dgm, dgm (M))1((E))
z (deers, (1) (Am)))
E. E[Pers,
The second term goes to zero (use the crude bound (ers,(dgm)) while the first one diverges. This proves the third bullet point.
(0lgmm(((())) (An)) S Cm(1 nn*!)),
At last, we prove the formula for the asymptotic expansion of Pers, Persa(dgm, (d.,,(A...) Pers. (dgm (1) (Am.) Pers,, (dgm (2) (Am.) Persa (dgm, (3) (An)). (45)
The first term equal to 1oll-//merss (m)),,.m) JM fxx 1- dz + or (n la/mm according to The- orem 4.1 Remark that for u, E Ω. pers,, (u) pers (v)) 2o (1) pers, (v)) alloc.
Hence, on the event E = {en < T (M)/2))
|Pers. (dgm) (2) (Am.)) Pers, (dgm (3) (A..)) Pers (M))l < 20c, (Pers,, (2) (A.))) + Pers, (dgm, (3) (A..)) + Pers, (M)))
38

---

We crudely bound the persistence of point in dgm;(An) by R(M), the radius of the smallest enclosing ball of M, obtain that
[Pers (dgm (2) (An)) + Persa (dgm (3) (An)) Pers. (dgm((M)))
< 2aE,, ( + 1)(# (dgm, (2) (An)) + # (dgm, (3) (A,)) + (dgm.(c)
We have already established that # (dgm; (2) (A,.) = O2= (1) (actually, it is larger than No with only exponentially small probability). Furthermore, Proposition 4.2 states that #(dgm) (An.) (1)
Lemma G.5 also states that En = (L=((((ognn)) r)/m)//.mm) Hence,
Persa (dgm. (2) (An)) Persa (dgm, (3) (Am)) Pers, (dgm, (M))) O2 (((logn)/n))
This concludes the proof.
Finally, remember that we defined linear feature maps as follows (at the end of Section 4 we let (V (]) be normed vector space and Φ Ω - V be Lipschitz continuous. For 2 0. the linear feature map a associated to & and defined on the space Dj of finite PDs is
Va E Dj, (a(a)
peers(u)* (()) E V.
(46)
wEa
Let us prove the associated Corollary 4.4
Let 2 1 and let 0 < < d be integer. Under the same assumptions in Proposition 4.2 it holds that &a (An) converges in probability to Qa (.dgg,()) whenever
Corollary 4.4.
Proof. According to 33
Proposition 5.1], J, the feature map 4, is continuous with respect to the
OT, distance. But we have shown in Corollary 4.3 that E(OT;, (dgm; (Am),, dM)] - 0 as n + co. In particular, OT, (dgm, (A,), dgm,(M) converges in probability to O. By continuity, so does || 2. (A,))(A..) 4 (dgm,(M) (M)
H Details on numerical experiments
We provide this section additional details on the numerical experiments conducted in Section PDs
are computed using GUDHI [22] PDs are plotted using the giotto-tde tttto-dda library [72] and persistence images using scikit-tda few hours.
644 All experiments can be easily rum on a standard office laptop over
Simulation of generic tori. Let R >
be two positive numbers. The (standard) torus Mn of major radius R and minor radius r is given as the image of [0, 2x]²² by the map
(R + (f) cos ())
F: (0, E 20.
-
(R + cos ()) sin (Ø) r (0)
(47)
Consider list .1..... Uk of pairs of angles in [0, 2x together with positive numbers .,,...,
, ag.
We let r(y) r Ek k= (dd yx) //)/)), where v1(() 1fl 1) exp(1((( 1)). 0 2m and d is the Euclidean distance on the flat torus. We then define
(R + r(A, Φ) cos(t)) cos(Ø)
( +
(R + r(0, Φ) c0) sin sin())
sin(o))
(48)
r(0, Φ) sin
Lemma H.1. Assume that (0 r(f, Φ) < - r. Then, the image of F is a compact
smooth submanifold, homeomorphic torus.
Proof. The condition on the function r ensures that the function f is injective and (2TT -periodi in each of its variables. Let (0, Φ) E [0, 2= We write r as shorthand for r(0, v). Let S = R+r cos and U = si) + Ögr cos( The differential of F is equal to
cos(Φ) U sin ④)
-S sin( + der cos( (0) cos(
d.F d.F(B. o)
S cos(() + d&r c0) (i)s(n())
(49)
r cos cos + 0g (0)
der sin(0)
39

---

The determinant of the two first rows is equal to SU, and is therefore only equal to 0 if U = -0. But in that case,
- S Siin( + d2r (0) cos(o)
dF((0, 6)
S co)( + der cos(0) sin
(50)
r (O) + Ogr sin(0)
Oer sin(0)
rank matrix. Indeed, note that U is equal to the dot product of Eq = (in()) cos(()) with the (nonzero) vector (r, dør). Hence, if U = O, then the dot product of (r, dgr) with the vector (cos(0), sin( (that is perpendicular to eg) nonzero. Furthermore, one of the two top entries the second column is also nonzero. Indeed, this is clear if dør = 0 or if sin 0 (we have S > 0 by assumption). Otherwise, having the two entries equal to zero would imply that S = (3ar) ((ggr)oo) cos (0). contradiction.
In all cases, d0, σ) is of maximal rank. This implies the conclusion.
Let R 2.4, r 0.8, o = and K = 30. We create a random torus by sampling pairs of angles Y {y1,... ...,.....3................... yk² uniformly at random, conditioned on the fact that maxye(n.2e dy(y) < We then draw the numbers 01,... ax as exponential random variables scale 0.5, conditioned on the fact that m 2m] r(Ø) < R - r. We let M be the image of [o, 2nT² 2 by F. Although we do not rigorously prove that the manifold M is almost surely generic, we conjecture that it is the case.
probability measure on P on is obtained in the following way. Sample (0, () E [o, 2n|² so that F00, o) is uniform on the torus. Then, let x F(0, 6). To put it another way, the pushforward of the uniform measure on the torus by F F F-1
Continuity of feature maps We sample n 10 points according to P, and compute the Čech PDs of the corresponding set A,, For i = 1, we plot the persistence images with weights pers", p 0, 1, 2, 4, with both birth and persistence values ranging between 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 = of n uniform points on a (nongeneric) circle. Second, we compute the Čech PD for i = 0 of n uniform points on (nongeneric) torus. Third, we compute the Čech PD for = of n uniform points on (nongeneric) torus. Each experiment is ran for values of n ranging from
10 to n 10 We observe in Figure the convergence rate of the total persistence of dgm! (1) (A..) predicted by Theorem 4.1 We then repeat each experiment 10 times, with similar rates of convergence observed for each run, although with large relative standard deviation (around 30%) for very small values of Persp (dgm, (1) deviation and the mean).
(A.,)) (the relative standard deviation being defined by the ratio between the standard
Convergence of /4n.i. Let i = 1. Let Q be the probability distribution obtained as the pushforward of the uniform distribution on [0, 2x by the map defined above. Using Equation (49), one can show that the density f of Q is given by
Va E Mo, f(x) = (2 r r( + cos(
(51)
where (0, (xx) Assume that the Radon measure Moc,i,,2 has density go Ω (this fact is not proven, but conjectured and strongly supported by experiments). Then, using (.. one can make a change of variables and observe that j4 has density 9j. given by
J r(R + cO)
Ve E Ω g5(u)= = (2m)
90
d0.
(52)
2TT Vr(R cos(
We sample a set A, of n = 100 points on a square and consider the convolution of the measure n Euedem, (A..) 5ya/mu with a Gaussian kernel, so that we obtain an estimation ğu of the density 9o-
We then define an estimator 9y of g by approximating the integral over a regular grid of 100 points on [0, 27..
40

---

We then place grid of size 100 x 100 over the square [0, 17)2. The measure μ is approximated by the measure f. with piecewise constant density on each square of the grid, with density the square centered at given by (z)). The corresponding measure is displayed in the center of Figure [6]
For given value of n, sample A, of points according to Q, and compute the corresponding measure Mn... The same transformations are applied to Un.., so that we obtain piecewise constant measure in,, on the same 100 100 grid. The heatmap of this measure is shown the left of Figure 6
At last, we approximate the distance (T2(Ea, My,a) by computing the distance OT2 (pm,5 (s.ss)
using the POT library, see 440 555 The distance is then normalized by OT₂(0, وم,)) v Perss (pt.)
The evolution of the normalized distance with respect to n is plotted in Figure 6 As predicted by
Theorem 4.1. the OT,, distance converges
n gets larger. We then repeat each experiment
10 times, with convergence to 0 observed each time, the relative standard deviation being always smaller than 7%.
41

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Rigorous proofs of our main claims are provided. All statements include precise assumptions, which were clearly summarized in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Our main results are theorems whose hypotheses are rigorously stated, as well as informally discussed. These hypotheses (such as the fact that the data is sampled on manifold, and the lack of noise) are the main limitations of our work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
42

---

Answer: [Yes]
The proofs of all the theorems appearing in the main text are given in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Appendix H contains all the details necessary to reproduce the numerical experiments conducted in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
43

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
The numerical experiments that we ran are basic and can 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.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
wwtp://wweeeeeeee Coaeee/mddeSSSbibic wwwpeddeuumisssiooooo. wwiiiisssiiniiyiyioo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 the paper to 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, as supplemental material.
7. 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 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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
44

---

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 the standard error of the mean.
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 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 range (e.g. negative error rates).
If error bars 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: As stated in the appendix, we only ran small 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 include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/neuripps httperpppp.cpppubceeeehteccccccc itw.e
Answer: [Yes]
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 NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed, as it is foundational.
Guidelines:
45

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
All the libraries used in the experiments are free use and properly credited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
46

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
47

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
48


Reviews:
[{"review_id": "nfTy1SizjK", "reviewer": "Reviewer_G8s6", "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.", "questions": "(Q1) Are there any results about real-world applications of the theory?", "limitations": "Yes, all limitations are addressed adequately by the authors.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(S1)\tThe paper addresses a relevant problem in TDA, and proves a number of significant results\n\n(S2)\tThe paper is comprehensive and well-written", "weaknesses": "(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. \n\n(W2) The experiments are very limited and do not demonstrate the implications of the proved results in ML", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your feedback. We address your concerns and your question in our response to all reviewers.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JdY28zCtmu", "reviewer": "Reviewer_rgww", "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:\n1. An improvement of the classical Cech bottleneck stability result for sufficiently good samples of closed embedded manifolds.\n2. 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.\n3. 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.", "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?\n2. 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?\n3. 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": "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.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is very well written: it is clear and easy to follow, it contains many useful and relevant references, and the results are clear and well abstracted.\n- The results are (to the best of my understanding) novel, as well as relevant for both theoretical and applied purposes. The results are connected to a lot of previous literature, so they should be of great interest to researchers in stochastic topology as well as the Topological Data Analysis public in general.\n- The probabilistic result identifies precisely the choices of $p$ that lead to convergence.", "weaknesses": "- The intersection of Topological Data Analysis and Machine Learning is non-trivial but not huge, restricting the audience of the paper to some extent.\n- The results have several restrictive hypothesis: strict manifold hypothesis (data lies exactly on a manifold), genericity of the manifold, no noise of any kind.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your appreciation of our work and your interesting questions.\nWe discuss noisy data in general in our response to all reviewers.\nTo answer your questions more specifically:\n\n*Is there any hope that (at least part of) the main probabilistic result\n(Corollary 4.3) still holds for non-generic manifolds?* :\n\nNo, one can build strong counter-examples (e.g. with a well-chosen union of circles in a high-dimensional space). In fact, such configurations will be studied at length in our next work on persistent homology dimension.\n\n*Could the genericity assumption be removed if we instead assume that the data is sampled from a manifold plus noise?*\n\nThis is a very interesting question, whose answer seems to depend on the kind of noise considered. See also our discussion of noisy data in our answer to all reviewers. \n\n*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?*\n\nIt might be doable, but it would require a lot of additional (and somewhat tedious) work. Indeed, the proofs of [ACSD 23] rely on nonquantitative compactness arguments; quantitative versions of these arguments would need to be developed to achieve such a result.\n\n*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$?*\n\nConvergence also occurs if  $i\\geq m$ and $p=m$. Furthermore, we do not know under which precise conditions it occurs when $p<m$ and $i\\geq m$.\n\n\n*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.*\n\nYou are right to point out that we cannot expect *all* submanifolds to be generic.\nHowever, one can easily build counter-examples to most of our results if the genericity assumption is dropped - as such, the need for genericity is not really a limitation of our work in itself, but rather an unavoidable constraint.\nNote also that not all highly structured scenarios are hopeless: in particular, it has been shown that among real algebraic submanifolds (a highly non-generic and structured subset of all submanifolds), a generic subset satisfies conditions similar to ours (see e.g. https://arxiv.org/abs/2402.08639).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rBmfW0X9rt", "reviewer": "Reviewer_xmoJ", "summary": "The paper describes three new theorems on the stability of persistence diagrams with respect to Bottleneck and Wasserstein distance under certain additional assumptions.", "questions": "Why do you think that the paper is an adequate fit for Neurips, as opposed to, say, a journal specialized on TDA?", "limitations": "As mentioned, they address the limitations of their results adequately", "rating": 4, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "All three results are interesting fundamental contributions to the field of topological data analysis", "weaknesses": "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).\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your appreciation of the overall quality of our work.\\\nWe discuss the soundness and importance of our noiseless data hypothesis, as well as the relevance of our work for the ML community, in our response to all reviewers.\\\nRegarding specifically the question *Why NeurIPS rather than a journal specialized in TDA?*, our understanding is that any high-quality contribution to a subfield of Machine Learning (e.g. TDA, bandits, causality, fairness, etc.) is welcome at NeurIPS, though such a contribution could also be submitted to a more specialized journal or conference.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Piwy9zXrs0", "reviewer": "Reviewer_hrBD", "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.", "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": "The limitations (that are also mentioned above) are addressed and explained at multiple points in the paper:\n-in line 169 the authors argue why some assumptions are always needed.\n-in line 216 they explain why the genericity assumption is needed for their Theorem 3.3.\n- in line 353 they again mention the assumptions as the main limitation of their work.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The results of the paper are in this reviewers opinion strong and interesting. Topological methods, in particular persistent homology, has become a widely used and powerful tool for the analysis of data, in particular data zhat is sampled from an underlying manifold. In many cases, the use of persistent homology can add an additional layer of explainability. For this, mathematical guarantees are fundamental. The new guarantees proven in this paper are significantly stronger than previous ones. In this reviewers opinion the proofs are correct and the precise arguments as well as the underlying ideas are nicely presented.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you very much for your interest in our work.\nWe address the issue of noisy data in our response to all reviewers, and we agree that similar guarantees for the Vietoris-Rips complex would be valuable; in fact, we are already working towards proving such results.\n\n\nRegarding experiments in particular, preliminary investigations suggest that comparable results should hold for the Vietoris-Rips persistence, and also seem to support what we explain regarding noisy data in our general response.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their time, effort, and valuable feedback. We are grateful for the overall positive reception of our work.
The most common questions pertained 1) to the practical applications of our results, and 2) to our assumption that the data is noiseless.
We address these two points below, and respond to each reviewer individually regarding their more specific questions.

* **Applications and relevance to the ML community:** (particularly in response to reviewers G8s6 and xmoJ)

    Though our paper does provide some new heuristics regarding the optimal choice of parameter for the Wasserstein distance (see Section 5), its main goal is to offer strong theoretical guarantees and a better understanding of techniques and objects routinely used by the TDA community, which is part of the wider ML community.
    As such, it is a study of existing ML methods rather than the description of a new method, similar e.g. to http://proceedings.mlr.press/v139/carriere21a.html (for an example within the field of TDA).
    Hence the main real world applications of our results are to be found in more experimental papers that apply the techniques that we examine, and for which we provide new guarantees.
    Of course, we also hope that a deeper understanding of those methods will in turn result in new methods, but those are beyond the scope of this (already rather long) article.

    This explains the relatively small number of experiments as well (which was commented upon by reviewer G8s6); those are not meant to showcase the power of some new method, nor to prove that our results are correct (as the mathematical proof is enough), but rather to illustrate them and to show that our asymptotic results are already observable with a reasonably small number of points.


    
* **Noise:** (particularly in response to reviewers rgww, xmoJ and hrBD): \
    Being limited by space constraints, we chose to focus on the noiseless case, but we agree that statements that allow for some noise would be a welcome addition to our results. \
Depending on the nature of the noise considered, some of our results extend seamlessly to the noisy case, while others would require additional work:
for example, if we let the maximum amplitude of the noise be small compared to the density $\epsilon = d_H(A,M)$ of the sampling $A$ in the manifold (before the addition of the noise), i.e. of order $\epsilon^2$, then Theorem 2.2 still holds (with modified constants) thanks to the Bottleneck stability theorem, and Region 3 of the diagram still has a finite number of points in expectation, as in Proposition 4.2. \
If we assume that the noise is normal to the submanifold and uniform (or at least that its density is lower and upper bounded) and that its amplitude $l$ is fixed and independent from the point cloud, then the situation is equivalent to sampling from an upper and lower bounded distribution on the open set $M^l$ (the offset of the submanifold by the amplitude of the noise). Its boundary is smooth or at least very regular, depending on the amplitude of the noise.
Regarding the small cycles (i.e. the points in Region 1 of the diagram), everything should work roughly as in the case of the $d$-dimensional cube, i.e. the limit distribution of $\mu_{n,i}$ should be some integral of $\mu_{\infty,i,d}$ over the open set. The behavior of the large cycles, i.e. of the points in Regions 2 and 3, should be dictated by the shape of the boundary of $M^l$. In particular, $\partial M^l$ should be generic enough for a generic choice of $M$ and $l$ that slightly modified of most of our results still hold, in particular the finite expected number of points in Region and the Wasserstein convergence of the diagrams  (except that $p$ needs to be greater than the ambient dimension $d$, rather than the intrinsic dimension $m$).
These questions might be explored in detail in future work.

Meta-review: 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.
Decision: Accept (poster)