A descriptive and formal perspective for grammar development Introduction. -For many linguistic theories, a grammar is a mechanism making it possible to define a natural language. The idea behind generative theories is more precisely to consider grammars as an enumerative process deriving a language. This idea is still very present, even in non-generative approaches, and a grammar is considered as a device used to check whether an input belongs or not to the language. This conception is very restrictive for many reasons. First, it has a lot of consequences on the way of representing linguistic information which is expressed in order to rule out ungrammatical utterances. This is particularly clear in the Optimality Theory [START_REF] Prince | Optimality theory : Constraint interaction in generative grammars[END_REF]) in which constraints (considered as universals) are stipulated precisely in this perspective. Second, considering grammar as a way of defining a language relies on a clear distinction between grammatical and ungrammatical productions. However, we know that such a distinction doesn't fit with the reality of language for many reasons. Corpus linguistics has shown for many years how often inputs can be ill-formed, and this characteristics concerns written as well as spoken productions. A linguist as well as an engineer has to deal with such material either to explain or to treat it. This means that we need an approach taking into account such aspects. Moreover the notion of grammaticality requires a total covering of the language : uncertainty, incompleteness, heterogeneity have no place in such approaches. However, in some cases, there is (almost) no information available at the syntactic level. This is the case for example between core and peripheral elements or in some configurations such as example (1). In this case, no relation (and no grammatical functions) can be given taking only into account the succession of words.

(1) Monday, washing, Tuesday, ironing, Wednesday, rest.

Our conception of grammar. -For these reasons, we think that grammar doesn't have to be restricted as a defining mechanism anymore. We need a more general conception in which grammar is an actual descriptive tool containing information from which the description of an input can be built, whatever its form. This claim is even strongest when taking into account the different domains of linguistic information. The classical way of defining interaction between these domains relies on structure mapping. In other words, the relations between different domains (for example between prosody and syntax) are expressed in terms of relations between parts of the respective structures (for example a prosodic and a syntactic tree). This incremental conception of building meaning actually doesn't work. Things have to be described in a more interactional way making it possible to take into account the fact that meaning is spread over the different linguistic domains. More precisely, meaning is the result of the interaction of elements of information spread over the domains.

Considering this, we think that a grammar is a set of information (that can even be non connected) capable of describing an input, whatever its form. The main role of a grammar is not to build a structure, but to specify the different characteristics of the linguistic objects. In this perspective, each piece of linguistic information has to be taken per se, which corresponds to a non holistic view of grammar (see [START_REF] Huddleston | The Cambridge Grammar of English Language[END_REF]). Such an approach is intrinsically monostratal in the sense that all information, including the relations between the different domains, is expressed at a unique level. It is also non-derivational especially because it doesn't necessarily propose a full coverage and can build non-connected structures. Last, it ignores deliberately the question of universality.

Constraints and Constructions. -In our conception, a grammar is then a set of information clusters indicating interaction between different objects. The idea is to bring together different sources of information as soon as they have an identified consequence on meaning. This conception is that of Construction Grammars (noted CxG, see for example [START_REF] Fillmore | Inversion and constructional inheritance[END_REF] or [START_REF] Kay | An informal sketch of a formal architecture for construction grammar[END_REF]). We propose in our approach to integrate the CxG framework within the constraint-based perspective of Property Grammars (hereafter PG, see for instance [START_REF] Blache | Property grammars : A fully constraint-based theory[END_REF]). From this CxG/PG point of view, a construction is a set of features plus a set of relations represented by means of constraints, as described in figure 1. Example. -Let's now consider the example of an analysis that intrinsically has to make use of several levels of information : the treatment of disfluencies. This phenomenon has two main characteristics that allow to consider it as specific. First, disfluencies bear neither syntactic nor semantic role : they do have a linguistic form, but this set of words (or beginning of words) isn't a (syntactic) phrase-structure (most of time it's the beginning of a phrase) ; moreover they aren't a way to express a semantic variation in comparison with a production without disfluency (e.g., il il in ex.

(2) has exactly the same meaning as one only utterance of il would have had).

(2) il il a quand-même un une fibre pédagogique assez assez euh enfin réelle quoi 1

The second characteristic is that the disfluency phenomenon must be considered through a multi-level feature set : to be complete, it must be described as a set of (morpho-)syntactic (POS, sub-categorization), semantic (sense, reference) and prosodic (intonation, pauses) features.

The disfluency construction in our CxG/GP approach will have the description of figure 2. This construction, which takes place in our mono-stratal resource, shows that a disfluency is a set of objets, consisting in one object x (of any category) and one of several objet(s) x' (that can be different). The "agreement" property tells that the x' has to have a feature set very close to x 's one : every value 2 of x' must agree with the corresponding value of x, which means that their entire form AVMs must be almost the same. The consequences of this description in a analysis process are the following : if all the evaluated properties are satisfied, then a "completed" 3 disfluency is characterized, like il il or assez assez in example (2). If some of the evaluated properties are violated, then a "modified" disfluency is characterized : un une in (2) is an example of a syntactically modified disfluency, where the two determiners only differ in the value of their gender (un is masculine and une is feminine), whereas in example (3) we can see a semantically modified disfluency, where un peu and pas mal have exactly the same feature set, except their intensity value.

(3) ils sont pas à l'abri de ça quoi mais c'est un peu pas mal d'hypocrisie quand-même à ce niveau-là 4

Perpectives. -A formal grammar for French is currently being developed in this CxG/PG framework. The aim of this grammar is to represent a set of fine-grained descriptions coming from corpus linguistics. Some of the represented phenomenon are characteristic of spoken productions. This grammar is the result of the theoretical reflections we have presented here, about the nature and the aims of formal representation of linguistic information, and about the way that very heterogeneous problems can be considered through a single homogeneous system.

Fig. 1 -

 1 Fig. 1 -(Rough) Description of the NP construction in CxG/GP.

Fig. 2 -

 2 Fig. 2 -CxG/GP representation of the disfluency construction.


Mickaël Buchet
email: mickael.buchet@m4x.org

Frédéric Chazal
email: frederic.chazal@inria.fr

Steve Y Oudot
email: steve.oudot@inria.fr

Donald R Sheehy
email: don.r.sheehy@gmail.com

Efficient and Robust Persistent Homology for Measures

A new paradigm for point cloud data analysis has emerged recently, where point clouds are no longer treated as mere compact sets but rather as empirical measures. A notion of distance to such measures has been defined and shown to be stable with respect to perturbations of the measure. This distance can easily be computed pointwise in the case of a point cloud, but its sublevel-sets, which carry the geometric information about the measure, remain hard to compute or approximate. This makes it challenging to adapt many powerful techniques based on the Euclidean distance to a point cloud to the more general setting of the distance to a measure on a metric space.

We propose an efficient and reliable scheme to approximate the topological structure of the family of sublevel-sets of the distance to a measure. We obtain an algorithm for approximating the persistent homology of the distance to an empirical measure that works in arbitrary metric spaces. Precise quality and complexity guarantees are given with a discussion on the behavior of our approach in practice.

Introduction

Given a sample of points P from a metric space X, the distance function d P maps each x ∈ X to the distance from x to the nearest point of P . The related fields of geometric inference and topological data analysis have provided a host of theorems about what information can be extracted from the distance function, with a particular focus on discovering and quantifying intrinsic properties of the shape underlying a data set [START_REF] Chazal | A sampling theory for compact sets in Euclidean space[END_REF][START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF]. The flagship tool in topological data analysis is persistent homology and the most common goal is to apply the persistence algorithm to distance functions, either in Euclidean space or in metric spaces [START_REF] Carlsson | Topology and data[END_REF][START_REF] Edelsbrunner | Topological persistence and simplification[END_REF][START_REF] Zomorodian | Computing persistent homology[END_REF]. From the very beginning, this line of research encountered two major challenges. First, distance functions are very sensitive to noise and outliers (Fig. 1 left). Second, the representations of the sublevel sets of a distance function become prohibitively large even for moderately sized data. These two challenges led to two distinct research directions. First, the distance to the data set was replaced with a distance to a measure induced by that data set [START_REF] Chazal | Geometric inference for probability measures[END_REF]. The resulting theory is provably more robust to outliers, but the sublevel sets become even more complex to represent (Fig. 1 center). Towards more efficient representations, several advances in sparse filtrations have led to linearsize constructions [START_REF] Tamal | Computing topological persistence for simplicial maps[END_REF][START_REF] Oudot | Zigzag zoology: Rips zigzags for homology inference[END_REF][START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF], but all of these methods exploit the specific structure of the distance function and do not obviously generalize. In this paper, we bring these two research directions together by showing how to combine the robustness of the distance to a measure, with the efficiency of sparse filtrations.

Contributions:

1. A Generalization of the Wasserstein stability and persistence stability of the distance to a measure for triangulable metric spaces.

2.

A general method for approximating the sublevel sets of the distance to a measure by a union of balls. Our method uses O(n) balls for inputs of n samples. Known methods for representing the exact sublevel sets can require n Θ(d) balls. Existing approximations using a linear number of balls are only applicable in Euclidean space [START_REF] Guibas | Witnessed k-distance[END_REF]. The first is too sensitive to noise and outliers. The second is smoother, but substantially more difficult to compute. The third is our approximation, which is robust to noise, efficient to compute, and compact to represent.

3.

A linear size approximation to the weighted Rips filtration. For intrinsically low-dimensional metric spaces, we construct a filtration of size O(n) that achieves a guaranteed quality approximation. Specifically, if the doubling dimension of the metric is d then the size complexity is 2 O(dk) n if one considers simplices up to dimension k (see Def. 2.1 for the formal definition of doubling dimension). This is a significant improvement over the full weighted Rips filtration, which has size 2 n in general or size n k+1 if one considers only simplices up to dimension k. It also has the advantage that the sparsification is independent of the weights. Thus, the (geo)metric preprocessing phase can be reused for any weighting of the points. If one attempted to use previous methods directly, this preprocessing phase would have to be repeated for each set of weights. This is especially useful if one is interested in several different weight functions such as when approximating the distance to a measure for several different values of the mass parameter.

4. An effective implementation with experimental results.

Overview of the paper Originally, the distance to a measure was introduced to capture information about both scale and density in a Euclidean point cloud. We extend the distance to a measure to any metric space X. We write B(x, r) to denote the closed ball with center x and radius r. The distance to a measure is then defined as follows.

Definition 1.1. Let µ be a probability measure on a metric space X and let m ∈]0, 1] be a mass parameter. We define the distance d µ,m to the measure µ as

d µ,m : x ∈ X → 1 m m 0 δ µ,l (x) 2 dl,
where δ µ,m is defined as δ µ,m : x ∈ X → inf{r > 0 | µ( B(x, r)) > m}.

The distance to a measure has interesting inference and stability results in the Euclidean setting [START_REF] Chazal | Geometric inference for probability measures[END_REF]. That is, the sublevel sets of the function can be used to infer the topology of the support of the underlying distribution (inference), and also, the output for similar inputs will be similar (stability). In Section 3, we extend these stability results to any metric space. The results about the stability of persistence diagrams apply to any triangulable metric space, i.e. metric spaces homeomorphic to a locally finite simplicial complex (the persistence diagram may not exist for non-triangulable metric spaces).

We then give a new way to approximate the distance to a measure. Using a sampling of the support of a measure, we are able to compute accurately the sublevel sets of the distance to a measure in any metric space, using power distances. We show in Section 4.1 that these functions have adequate stability and approximation properties. Then, in Section 4.2, we give the practical implications for computing persistence diagram for finite samples.

The witnessed k-distance is another approach to approximating the distance to a measure proposed in [START_REF] Guibas | Witnessed k-distance[END_REF]. This approach works only in Euclidean spaces as it relies on the existence of barycenters of points. The analysis links the quality of the approximation to the underlying topological structure. In this paper, we look at bounds independent of intrinsic geometry. When restricted to the Euclidean setting in section 4.3, our method improves the approximation bounds from [START_REF] Guibas | Witnessed k-distance[END_REF]. The new bounds match the quality of approximation achieved by our method of Section 4.1, which has the added advantage that it is valid in any metric spaces..

In Section 5, we introduce the weighted Rips complex. Given a parameter, the sublevel set of a power distance associated with this parameter is a union of balls. Generalizing the Vietoris-Rips complex, we define the weighted Rips complex as the clique complex whose 1-skeleton is the same as the one of the nerve of this union of balls. The induced filtration has important stability properties and can be used to approximate persistence diagrams.

Unfortunately, the weighted Rips filtration is too large to construct in full for large instances. This problem already exists with the usual Rips filtration. Sparsifying schemes have been recently proposed in [START_REF] Tamal | Computing topological persistence for simplicial maps[END_REF][START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF]. Extending the approach used in [START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF], we construct a sparse approximation that has linear size in the number of points (Section 6). This can be used to approximate persistence diagrams even for high dimensional inputs if the data is intrinsically low dimensional. As we show in Section 6, there are very simple examples where the input metric is intrinsically low-dimensional and yet the weight function can cause the weighted distance function to be high-dimensional. Our approach has the advantage over previous methods in that the size complexity will only depend on the dimension of the input metric, rather than the dimension of points under the weighted distance.

The combination of these approaches makes it possible to use the distance to a measure to infer topology on real instances. In Section 7, we illustrate the theory with some examples and results from an implementation.

Background

In this paper, we consider a metric space X with distance d X (•, •). In a slight abuse of notation, we also write d X to denote the distance between a point and a set defined as d X (x, P ) = inf p∈P d X (x, p). The Hausdorff distance between two sets P and Q will be denoted d H (P, Q). We write B(x, r) for the open ball of center x and radius r in d X , and we write B(x, r) for the corresponding closed ball.

Metric Spaces and doubling dimension

For metric spaces that are not embedded in Euclidean space, the doubling dimension gives a useful way to describe the intrinsic dimension of the metric space by bounding the size of certain covers of subsets. Formally it is defined as follows.

Definition 2.1. The doubling constant λ X of a metric space X is the maximum over all balls B(x, r) with x ∈ X of the minimum number of balls of radius r/2 required to cover B(x, r). The doubling dimension is defined to be log 2 (λ X ).

Wasserstein distance

To compare measures, we use the Wasserstein distance, also called the earth-mover distance. Intuitively, it is the minimal cost to move all the mass from one measure to another. To state the formal definition we first introduce some notation.

Given a measure µ on a metric space X, we write B(X) to denote the set of all Borel subsets of X. Given A ∈ B(X), we define the mass of A as µ(A). Similarly µ(X) is called the total mass of µ. We write Supp(µ) for the support of the measure µ. Definition 2.2. Let µ and ν be positive measures with the same total mass on a metric space X. A transport plan between µ and ν is a measure π on X × X such that for all A, B ∈ B(X),

π(A × X) = µ(A) and π(X × B) = ν(B).
We denote by Π(µ, ν) the set of all transport plans between µ and ν. The pth order cost of the transport plan π is defined as

C p (π) = X×X d X (x, y) p dπ(x, y) 1 p .
The Wasserstein distance between µ and ν is the minimum cost over all transport plans. Definition 2.3. Let µ and ν be positive measures with the same total mass on a metric space X. The Wasserstein distance of order p between µ and ν is defined as

W p (µ, ν) = min π∈Π(µ,ν) X×X d X (x, y) p dπ(x, y) 1 p
.

The Wasserstein distance is finite if both probability measures have finite p-moments, which is always the case for measures with compact support.

Persistence theory

A filtration F = {F α } α∈R is a sequence of spaces such that F α ⊆ F β whenever α ≤ β. Persistence theory studies the evolution of the homology of the sets F α for α ranging from -∞ to +∞. More precisely, the filtration induces a family of vector spaces connected by linear maps at the homology level, called a persistence module. More generally, a persistence module is a pair V = ({V α }, {v β α }) where each V α is a vector space and v β α is a linear map

V α → V β such that v γ β • v β α = v γ
α for all α ≤ β ≤ γ and v α α is the identity. A persistence module is said to be q-tame if v β α has finite rank for every α < β. A filtration is said to be q-tame if its corresponding persistence module is q-tame. The algebraic structure of a q-tame persistence module U can be described and visualized by the persistence diagram Dgm(U), a multiset of points in the plane. If U comes from a filtration {F α }, a point (α, β) in Dgm(U) indicates a nontrivial homology class that exists in the filtration between the parameter values α and β.

We overload notation and write Dgm({F α }) to denote the persistence diagram of the persistence module defined by the filtration {F α }. Moreover, for a real-valued function f , we write Dgm(f ) to denote Dgm({f -1 (] -∞, α])}), the persistence diagram of the sublevel sets filtration of f . For an introduction to persistent homology, the reader is directed to [START_REF] Chazal | The structure and stability of persistence modules[END_REF][START_REF] Edelsbrunner | Computational topology: an introduction[END_REF].

Bottleneck distance

We put a metric on the space of persistence diagrams as follows. First, a partial matching M between diagrams D and E is a subset of D × E in which each element of D ∪ E appears in at most one pair. The bottleneck cost of M is max (d,e)∈M d -e ∞ . We say M is an -matching if the bottleneck cost is and every (α, β) in D or E with |β -α| ≥ 2 is matched. The bottleneck distance between D and E is defined as d B (D, E) = inf{ | there exists an -matching between D and E}.

It is often useful to look at persistence diagrams on a logarithmic scale, because the distance does no longer depend on the scale at which the object is seen. The log-bottleneck distance, denoted d log B is the bottleneck distance between diagrams after the change of coordinates (α, β) → (ln α, ln β).

Filtration interleaving

One way to prove that two persistence diagrams are close is to prove that the filtrations inducing them are interleaved. Two filtrations {U α } α∈R and {V α } α∈R are said to be -interleaved if for any α,

U α ⊆ V α+ ⊆ U α+2 .
The following classic result [START_REF] Chazal | Proximity of persistence modules and their diagrams[END_REF][START_REF] Chazal | The structure and stability of persistence modules[END_REF][START_REF] Cohen-Steiner | Stability of persistence diagrams[END_REF] about stability of persistence diagrams says that interleaved filtrations yield similar persistence diagrams.

Theorem 2.4. Let U and V be two q-tame and -interleaved filtrations. Then, the persistence diagrams of these filtrations are -close in bottleneck distance, i.e., d B (Dgm(U ), Dgm(V )) ≤ .

We work with the persistence theory on functions, which means studying the persistence of the sublevel sets filtration defined as {f -1 (] -∞, α])} α∈R for any real-valued function. To simplify notation, we write Dgm(f ) to denote the persistence diagram of the sublevel sets filtration of f .

Persistence module interleaving

The notion of interleaving can be extended to persistence modules as seen in [START_REF] Chazal | Persistence stability for geometric complexes[END_REF]. Given two persistence modules U = ({U α }, {u β α }) and V = ({V α }, {v β α }) and a real > 0, an -homomorphism from U to V is a collection of linear maps Φ = {φ α } such that for all α < β, v β+ α+ • φ α = φ β • u β α . Two -homomorphisms Φ from U to V and Ψ from V to W can be composed to build a 2 -homomorphism ΨΦ from U to W whose linear maps are obtained by composing the linear maps of Φ and Ψ. Among -homomorphisms from U → U, one has a particular role. The -shift map 1 U is the collection of maps u α+ α given in the persistence module U. We use it to define the interleaving of two persistence modules as follows.

Definition 2.5. Let U and V be two q-tame persistence modules. U and V are -interleaved if there exists -homomorphisms Φ : U → V and Ψ : V → U such that ΦΨ = 1 2

V and ΨΦ = 1 2 U . Note that the definition is equivalent to the commutativity of the following diagrams for any α < β, where Φ = {φ α } and Ψ = {ψ α }.

V β+ V α+ U α U β v β+ α+ u β α φ α+ α φ β+ β V β V α U α+ U β+ v β α u β+ α+ ψ α+ α ψ β+ β U α- U α+ V α u α+ α- φ α α- ψ α+ α V α- V α+ U α v α+ α- ψ α α- φ α+ α
The following theorem is an algebraic analog of Theorem 2.4. The proof can be found in [START_REF] Chazal | The structure and stability of persistence modules[END_REF].

Theorem 2.6. Let U and V be two q-tame and -interleaved persistence modules. Then, d B (Dgm(U), Dgm(V)) ≤ .

Contiguous simplicial maps

Let X and Y be simplicial complexes. A simplicial map f : X → Y is a map between the corresponding vertex sets so that for every simplex σ ∈ X, f (σ) = p∈σ f (p) is a simplex in Y . Two simplicial maps f and g are contiguous if σ ∈ X implies that f (σ) ∪ g(σ) ∈ Y . If two simplicial maps are contiguous, then they induce the same homomorphism at the homology level [START_REF] Munkres | Elements of Algebraic Topology[END_REF]Chapter 1].

A clique complex is a simplicial complex whose simplices are the cliques of a graph. Many of the simplicial complexes considered in this paper are clique complexes. We will use the following simple lemma to construct contiguous simplicial maps between clique complexes. Lemma 2.7. Let X and Y be clique complexes and let f and g be two functions from the vertex set of X to the vertex set of Y . If for every edge (p, q) ∈ X, the tetrahedron {f (p), g(p), f (q), g(q)} is in Y , then f and g induce contiguous simplicial maps from X to Y .

Proof. Let σ be a simplex of X. Every pair in f (σ) ∪ g(σ) is of the form (f (p), f (q)), (f (p), g(q)), or (g(p), g(q)) for some vertices p and q in σ. Since (p, q) ∈ σ, the tetrahedron hypothesis of the lemma implies that all of these pairs are edges of Y . Thus, f (σ) ∪ g(σ) is a simplex in Y because Y is a clique complex. Moreover, f (σ) ∈ Y and g(σ) ∈ Y because simplices are closed under taking subsets. Therefore, f and g are indeed contiguous simplicial maps as desired.

3 Persistence and Stability of the Distance to a Measure in a Metric Space

In this section, we prove that, if we have two close probability measures, then the persistence diagrams of the sublevel sets filtration of their distance to measure functions are close. The result applies to triangulable metric spaces, i.e., those that are homeomorphic to a locally finite simplicial complex. The persistence diagrams considered in this paper are well defined in this class of spaces. In particular, every compact Riemannian manifold is triangulable.

If the persistence diagram is to be meaningful, one might expect that it is stable with respect to perturbations in the underlying measure. The following theorem shows that this is indeed the case. Two measures that are close in the quadratic Wasserstein distance, W 2 yield persistence diagrams that are close in bottleneck distance, d B (see [START_REF] Villani | Topics in Optimal Transportation[END_REF]Sec. 7.1]). Theorem 3.1. Let µ and ν be two probability measures on a triangulable metric space X and let m be a mass parameter. Then Dgm(d µ,m ) and Dgm(d ν,m ) are well-defined and

d B (Dgm(d µ,m ), Dgm(d ν,m )) ≤ 1 √ m W 2 (µ, ν).
To prove this theorem, we first show that the distance to measure functions are stable with respect to the Wasserstein distance. Then, we prove that their diagrams are well-defined and are close using Theorem 2.4. This result provides the same bound as the existing Euclidean space result. Technicalities exist for the well-definition of persistence diagrams which required the metric space to be triangulable.

Wasserstein stability

A measure ν is a submeasure of a measure µ if for every B ∈ B(X), ν(B) ≤ µ(B). Let Sub m (µ) be the set of all submeasures of µ, which have a total mass m.

The distance to a measure µ at point a x can be expressed as the Wasserstein distance between two measures, the Dirac mass δ x on x and a submeasure of µ of mass m. Using this view, we generalize the stability result from [START_REF] Chazal | Geometric inference for probability measures[END_REF] as follows.

Proposition 3.2. Let µ be a probability measure on a metric space X, and let m ∈]0, 1] be a mass parameter. Then,

d µ,m (x) = min ν∈Subm(µ) 1 √ m W 2 (mδ x , ν).
Given x ∈ X and m > 0, let R µ,m (x) be the set of the submeasures of µ with total mass m whose support is contained in the closed ball B(x, δ µ,m (x)) and whose restriction to the open ball B(x, δ µ,m(x) ) coincides with µ. The proof shows that R µ,m (x) is exactly the set of minimizers of Proposition 3.2.

In order to prove this theorem we need to introduce a few definitions. The cumulative function F ν : R + → R of a measure ν on R + is the non-decreasing function defined by

F ν (y) = ν([0, y)). Its generalized inverse F -1 ν : m → inf{t ∈ R | F ν (t) > m} is left-continuous.
Proof. If ν is a measure of total mass m on X then there exists only one transport plan between ν and the Dirac mass mδ x . It transports every point of X to x. Hence we get

W 2 (mδ x , ν) 2 = X d X (h, x) 2 dν(h).
Let d x : X → R denote the distance function to the point x and let ν x be the pushforward of ν by the distance function to x. That is, for any subset

I of R, ν x (I) = ν(d -1 x (I)). Note that F -1 νx (m) = δ ν,m (x).
Using the change of variable formula and the definition of the cumulative function we get:

X d X (h, x) 2 dν(h) = R + t 2 dν x (t) = m 0 F -1 νx (l) 2 dl.
Suppose further that ν is a submeasure of µ, then F νx (t) ≤ F µx (t) for all t > 0. So, F -1 νx (l) ≥ F -1 µx (l) for all l > 0, and thus,

W 2 (mδ x , ν) 2 ≥ m 0 F -1 µx (l) 2 dl = m 0 δ µ,l (x) 2 dl = md µ,m (x) 2 . ( 1
)
This inequality implies that d µ,m (x) is smaller than

1 √ m W 2 (mδ x , ν) for any ν ∈ Sub m (µ).
Consider the case when the inequality in (1) is tight. Such a case happens when for almost every l ≤ m, F -1 νx (l) = F -1 µx (l). Since these functions are increasing and left-continuous, equality must hold for every such l. By the definition of the pushforward, this implies that ν( B(x, δ µ,m (x))) = m, i.e., all the mass of ν is contained in the closed ball B(x, δ µ,m (x)), and that ν

(B(x, δ x,µ (m))) = µ(B(x, δ x,µ (m))). Because ν is a submeasure of µ this is true if and only if ν is in the set R µ,m (x) described before the proof. Thus R µ,m (x) is exactly the set of submeasures ν ∈ Sub m (µ) such that d µ,m (x) = 1 √ m W 2 (mδ x , ν).
To conclude the proof we need only show that there exists at least one measure µ x,m in the set

R µ,m (x). If µ( B(x, δ µ,m (x))) = m, then µ x,m = µ| B(x,δµ,m(x)
) is an obvious choice. The only difficulty is when the boundary ∂B(x, δ µ,m (x)) of the ball has too much mass. In this case we uniformly rescale the mass contained in the bounding sphere such that the measure µ x,m has total mass m. More precisely we let:

µ x,m = µ| B(x,δµ,m(x)) + (m -µ(B(x, δ µ,m (x)))) µ| ∂B(x,δµ,m(x)) µ(∂B(x, δ µ,m (x)))
.

We hence have

1 √ m W 2 (mδ x , µ x,m ) = d µ,m (x).
From this result, we have the following Wasserstein stability guarantee for the distance to a measure.

Theorem 3.3. Let µ and ν be two probability measures on a metric space X and let m ∈]0, 1] be a mass parameter. Then:

d µ,m -d ν,m ∞ ≤ 1 √ m W 2 (µ, ν). Proof. Using Proposition 3.2, we get that √ m d µ,m (x) = W 2 (mδ x , µ x,m ), where µ x,m ∈ R µ,m (x).
Let π be an optimal transport plan between µ and ν, i.e., a transport plan between µ and ν such that

X×X d X (x, y) 2 dπ(x, y) = W 2 (µ, ν) 2 .
Let us consider the submeasure µ x,m of µ. Then there exists π a submeasure of π that transports µ x,m to a submeasure ν of ν. We get that:

W 2 (µ x,m , ν) ≤ W 2 (µ, ν).
Using Proposition 3.2 again, we get that for any x ∈ X,

√ m d ν,m (x) ≤ W 2 (mδ x , ν). Thus, √ m d ν,m (x) ≤ W 2 (mδ x , ν) ≤ W 2 (mδ x , µ x,m ) + W 2 (ν, µ x,m ) ≤ √ m d µ,m (x) + W 2 (µ, ν).
The roles of µ and ν can be reversed to conclude the proof.

Another consequence of Proposition 3.2 is that d µ,m is 1-Lipschitz with respect to x.

Proposition 3.4. Let µ be a probability measure on a metric space X and let m ∈]0, 1] be a mass parameter. Then d µ,m is 1-Lipschitz.

Proof. Let x and y be two points of X. Using Proposition 3.2, there exists a submeasure y). The choice of x and y is arbitrary, so by symmetry,

µ x,m of µ such that d µ,m (x) = 1 √ m W 2 (mδ x , µ x,m ). The same proposition applied to y gives d µ,m (y) ≤ 1 √ m W 2 (mδ y , µ x,m ). Knowing that W 2 (mδ x , mδ y ) = √ m d X (x, y), we can conclude that d µ,m (y) ≤ d µ,m (x) + d X (x,
d µ,m (x) ≤ d µ,m (y) + d X (x, y). Therefore, d µ,m is 1- Lipschitz.

Persistence

For persistence diagrams of sublevel sets filtrations of distance to measure functions to be well-defined, we need to prove that they are q-tame. Proposition 3.5. Let X be a triangulable metric space, let µ be a probability measure on X, and let m ∈]0, 1] be a mass parameter. Then, the sublevel sets filtration of d µ,m is q-tame.

Proof. According to Proposition 3.4 d µ,m is 1-Lipschitz and thus continuous. Also, d µ,m is nonnegative by definition. Moreover, d µ,m is proper, i.e., the preimage of any compact set is compact. As the function is nonnegative and continuous, it suffices to show that any sublevel set

d -1 µ,m ([0, α]) is compact. Suppose for contradiction that for a fixed α > 0, d -1 µ,m ([0, α]) is not compact. Then there exists a sequence (x i ) i>0 of points of d -1 µ,m ([0, α]) such that d X (x 0 , x n ) → ∞ when n → ∞.
Hence we can extract a sub-sequence (x φ(i) ) i>0 such that for any i and j, B(x

φ(i) , √ 2α) ∩ B(x φ(j) , √ 2α) = ∅. Let us remark that µ( B(x φ(i) , √ 2α)) ≥ m 2 . So, d µ,m (x φ(i) ) 2 = 1 m m 0 δ µ,l (x φ(i) ) 2 dl ≤ α 2 .
The function δ µ,l (x φ(i) ) is nonnegative and increasing with l and therefore

m 2 δ µ, m 2 (x φ(i) ) 2 ≤ mα 2 . Using the definition of δ µ,m , this implies that µ( B(x φ(i) , √ 2α)) ≥ m 2 .
Measures are countably additive, so

µ(X) ≥ i>0 µ( B(x φ(i) , √ 2α)) ≥ i>0 m 2 = ∞.
However, µ is a probability measure and therefore µ(X) = 1. This contradiction implies that

d -1 µ,m ([0, α]) is compact.
As X is triangulable, there exists a homeomorphism h from X to a locally finite simplicial complex C. Then for any α > 0, we can restrict the simplicial complex C to a finite simplicial complex

C α that contains h(d -1 µ,m ([0, α])) as d -1 µ,m ([0, α]) is compact. The function d µ,m •h -1 | Cα is continuous on C α .
Thus its sublevel sets filtration is q-tame by Theorem 2.22 of [START_REF] Chazal | The structure and stability of persistence modules[END_REF].

The construction extends to any α and therefore the sublevel sets filtration of d µ,m • h -1 is q-tame. Furthermore, homology is preserved by homeomorphisms and thus we can say that the sublevel sets filtration of d µ,m is q-tame.

d µ,m -d ν,m ∞ ≤ 1 √ m W 2 (µ, ν).
The sublevel sets filtrations are therefore interleaved since for all α ∈ R,

d -1 µ,m (] -∞, α]) ⊆ d -1 ν,m (] -∞, α + 1 √ m W 2 (µ, ν)]) ⊆ d -1 µ,m (] -∞, α + 2 √ m W 2 (µ, ν)]).
Therefore, applying Theorem 2.4 gives

d B (Dgm(d µ,m ), Dgm(d ν,m )) ≤ 1 √ m W 2 (µ, ν).

Approximating the Distance to a Measure

Computing the persistence diagram of the sublevel sets filtration of d µ,m requires knowing the sublevel sets. They are not generally easy to compute. We propose an approximation paradigm for d µ,m that replaces the sublevel sets by a union of balls. The approach works in any metric space and yields equivalent guarantees as the witnessed k-distance approach used in [START_REF] Guibas | Witnessed k-distance[END_REF] for Euclidean spaces.

Power distances

Definition 4.1. Given a metric space X, a set P and a function w : P → R, we define the power distance f associated with (P, w) as

f (x) = min p∈P d X (p, x) 2 + w 2 p , (2)
where w p is the value of w at the point p.

The function w can be defined on a superset of P . Moreover, the sublevel set f -1 (] -∞, α]) is the union of the closed balls centered on the points p of P with radius r p (α) = α 2 -w 2 p . By convention, we assume the ball is empty when the radius is imaginary.

Stability

Power distances are stable under small perturbations of the points.

The following lemma states a result about inclusions between balls. It allows another stability result on power distances (Proposition 4.3) and will be useful for studying the stability of the weighted Rips filtration in Section 5. Lemma 4.2. Let p, q ∈ X be such points such that d X (p, q) ≤ , and let w : X → R be a t-Lipschitz function. For all α ≥ w p , r p (α) + ≤ r q (α + 1 + t 2 ).

Proof. First, observe that r p (α) can be bounded as follows.

r p (α) 2 = α 2 -w 2 p ≤ α 2 -w 2 p + (tα -1 + t 2 w p ) 2 = ( 1 + t 2 α -tw p ) 2 .
Next, we relate r p and r q as follows.

(r p (α) + ) 2 = α 2 -w 2 p + 2 α 2 -w 2 p + 2 ≤ α 2 -w 2 p + 2 ( 1 + t 2 α -tw p ) + 2 = (α + 1 + t 2 ) 2 -(w p + t ) 2 ≤ (α + 1 + t 2 ) 2 -w 2 q = r q (α + 1 + t 2 ) 2 .
The requirement that α ≥ w p allows us to take the square root of both sides of the inequality since both will be nonnegative.

As a consequence, we obtain the following. Proposition 4.3. Let X be a metric space and let w : X → R be a function. Let P and Q be two compact subsets of X. Let f P and f Q be the power distances associated with (P, w) and

(Q, w). If w is t-Lipschitz, then f P -f Q ∞ ≤ 1 + t 2 d H (P, Q).
Proof. Let x be any point of X. There exists p ∈ P such that x ∈ B(p, r p (f P (x))). There also exists q ∈ Q such that d X (p, q) ≤ d H (P, Q). By Lemma 4.2 and the triangle inequality, x ∈ B(q, r q (f P (

x) + √ 1 + t 2 d H (P, Q))). Thus, f Q (x) ≤ f P (x) + √ 1 + t 2 d H (P, Q). P and Q are interchangeable therefore f Q -f P ∞ ≤ √ 1 + t 2 d H (P, Q).
Remark that this bound is tight. If we replace t by 0, we have

f Q -f P ∞ = d H (P, Q).

Approximation

To approximate the distance to a probability measure µ, we introduce the following function.

Definition 4.4. Let µ be a probability measure on a metric space X and let m ∈]0, 1] be a mass parameter. Given a subset P of X, we define d P µ,m as the power distance associated with (P, d µ,m ).

d P µ,m (x) = min p∈P d X (p, x) 2 + d µ,m (p) 2
That is, the weight of each point is its distance to the empirical measure. If P is close to Supp(µ), we obtain an approximation of d µ,m . Theorem 4.5. Let µ be a probability measure on a metric space X and let m ∈]0, 1] be a mass parameter. Let P be a subset of X. If d H (P, Supp(µ)) ≤ , then

1 √ 2 d µ,m ≤ d P µ,m ≤ √ 5 (d µ,m + ).
A multiplicative approximation implies a multiplicative interleaving of the sublevel sets filtrations that becomes an additive interleaving on a logarithmic scale. Theorem 2.4 thus guarantees that the persistence diagrams are close in the bottleneck distance on a logarithmic scale.

Proof. Let x be a point of X. Using the previous notations we get

d µ,m (x) 2 = 1 m X d X (y, x) 2 µ x,m (y)dy.
Let us now fix a point p ∈ Supp(µ). Since µ p,m is a submeasure of µ of total mass m,

d µ,m (x) 2 = 1 m X d X (y, x) 2 µ x,m (y)dy ≤ 1 m X d X (y, x) 2 µ p,m (y)dy ≤ 1 m X ((d X (y, p) + d X (p, x)) 2 )µ p,m (y)dy ≤ d X (p, x) 2 2 m X µ p,m (y)dy + 2 m X d X (y, p) 2 µ p,m (y)dy = 2(d X (p, x) 2 + d µ,m (p) 2 ).
The third inequality follows from the triangle inequality and the relation (

a + b) 2 ≤ 2(a 2 + b 2 ).
As the above inequality holds for any point p in P we can conclude that

d µ,m (x) ≤ √ 2 d P µ,m (x).
To show the other inequality, let p be a point of P . Then by definition we get:

d P µ,m (x) 2 ≤ d X (x, p) 2 + d µ,m (p) 2 ≤ d X (x, p) 2 + 1 m X d X (p, y) 2 µ x,m (y)dy ≤ d X (x, p) 2 + 1 m X (d X (p, x) + d X (x, y)) 2 µ x,m (y)dy ≤ 3 d X (x, p) 2 + 2 d µ,m (x) 2 .
By the definition of the distance to a measure, d X (x, Supp(µ)) ≤ d µ,m (x). Consequently, there exists a point p ∈ P such that d X (x, p) ≤ d µ,m (x) + . Hence,

d P µ,m (x) 2 ≤ 5(d µ,m (x) + ) 2 .

Measures with finite support

We now assume that the data are given as a finite set of points P in a metric space X. We define the following measure to study the point set P .

Definition 4.6. Given a finite point set P in a metric space X, the empirical measure µ P on P is defined as a normalized sum of Dirac measures:

µ P = 1 |P | p∈P δ p .
Let x be a point of X. We introduce the parameter k = m|P |. To simplify the exposition we will assume that k is an integer. See Remark 1 for the generalization.

We reorder the points of P such that

P = (p 1 (x), • • • , p |P | (x)) and d X (x, p 1 (x)) ≤ • • • ≤ d X (x, p |P | (x)). (3)
If two points are at the same distance of x, we order them arbitrarily. We define the set

N N P k (x) = {p 1 (x), • • • , p k (x)}
and call it the set of k th nearest neighbors of x. The set Λ P k consists of all k-tuples of points of P . Lemma 4.7. Let P be a finite point set in a metric space X then for any x ∈ X:

d µ P ,m (x) = min S∈Λ P k 1 k p∈S d X (p, x) 2 = 1 k p∈N N P k (x) d X (p, x) 2 .
Proof. Since µ P has finite support, all its submeasures also have finite support.

Sub m (µ P ) =    p∈P λ p δ p | ∀p ∈ P, 0 ≤ λ p ≤ 1 |P | and p∈P λ p = m    Let ν = p∈P λ p δ p be an element of Sub m (µ P ). W 2 (mδ x , ν) 2 = p∈P λ p d X (x, p) 2
Combined with the relation (3), we get

S x = p∈N N P k (x) δ p ∈ argmin ν∈Subm(µ P ) W 2 (mδ x , ν).
As S x ∈ Λ P k , we are done. The distance to the empirical measure, d µ P ,m , is thus defined as a lower envelope of quadratic functions. It is generally costly if not impossible to compute its sublevel sets.

However, we can directly use the approximation presented in Section 4.1. Using P in Definition 4.4 and Theorem 4.5, we get the following.

Corollary 4.8. Let P be a finite point set of a metric space X and m ∈]0, 1] be a mass parameter. Then,

1 √ 2 d µ P ,m ≤ d P µ P ,m ≤ √ 5 d µ P ,m .
The multiplicative approximation gives a closeness result between persistence diagrams on a logarithmic scale. Moreover, these bounds cannot be improve. Proof. We are looking for a worst case scenario where inequalities become equalities for at least one point. We consider the space R d with the L 1 -norm, denoted | • |. For any fixed dimension d, we build the set of 2d points whose coordinates have the form (0, • • • , 0, ±1, 0, • • • , 0). These points are marked by triangles in the following drawing in dimension 2.

q p 1 p 2 p 3 p 4 o
We fix k = 2d and we study d µ P ,m and d P µ P ,m at points q(-3, 0 • • • , 0) and o. First we compute the value of d µ P ,m (p i ) for any i:

d µ P ,m (p i ) 2 = 1 2d 2d j=1 |p j -p i | 2 = 4 2d -1 2d = 4 - 2 d
Now we compute the value of d µ P ,m at q and o: dµ P ,m(q) tends to 1 √ 2 . Thus, the bounds of Corollary 4.8 are reached at the limit for a same data set, although at two different points.

d µ P ,m (o) 2 = 1 2d 2d i=1 |p i -o| 2 = 1 d µ P ,m (q) 2 = 1 2d 2d i=1 |p i -q| 2 = 1 2d (|p 1 -q| 2 + (2d -
Remark 1. If k is not an integer, it suffices to do the same construction with a careful weighting of the point p k . The results stay exactly the same after replacing k by k .

Euclidean case

We consider the standard Euclidean space R d with the L 2 -norm. Considering the finite point set P and its empirical measure in R, we are able to express the distance to the empirical measure d µ P ,m as a power distance. This restricted settings allows us to improve the bounds of Corollary 4.8 as follows.

Theorem 4.11. Let P be a finite point set in R d and let m ∈]0, 1] be a mass parameter. Then the following relation is tight.

1 √ 2 d µ P ,m ≤ d P µ P ,m ≤ √ 3 d µ P ,m .
Moreover, it implies a relation between persistence diagrams:

d log B (Dgm(d µ P ,m ), Dgm(d P µ P ,m )) ≤ ln( √ 3).
We first present a way to express the distance to a measure as a power distance to the set of all barycenters of k-tuples of P . Then we prove Theorem 4.11 before comparing it with the previous approximation, called the witnessed k-distance proposed in [START_REF] Guibas | Witnessed k-distance[END_REF]. We improve the bounds on the witnessed k-distance and show that the quality of the approximation is the same for both functions.

Power distance expression of d µ P ,m

For a fixed integer k, the barycenter associated with a point x is the barycenter of its k-nearest neighbors. It is also the center of the cell of the k th -order Voronoi diagram that contains x. Definition 4.12. For a point set P in R d and an integer k ≤ |P |, the barycenter associated with x is bar

(x) = 1 k p∈N N P k (x)
p.

Any subset of k elements from P is uniquely associated with a barycenter. We identify the two objects and define a cell energy that describes how clustered the points are.

E C (q) = 1 k p∈S p -q 2 .
Notice that the set S is not necessarily the set N N P k (q) and that E C (q) ≥ d µ P ,m (q) 2 . We can now write d µ P ,m in the following form. Lemma 4.14. Let P be a finite point set of R d let m ∈]0, 1] be a mass parameter. For any x ∈ R d ,

d µ P ,m (x) = min y∈R d E C (bar(y)) + bar(y) -x 2 = E C (bar(x)) + bar(x) -x 2 .
Proof. Fix S ∈ Λ P k and write q = 1 k p∈S p. We adapt Lemma 4.7 to the Euclidean setting to get

1 k p∈S p -x 2 = E C (q) + q -x 2 .
This requires the inner product as follows.

A = 1 k p∈S p -x 2 = 1 k p∈S p -q 2 + q -x 2 + 2 p -q|q -x = E C (q) + q -x 2 + 2 q -q|q -x .
Lemma 4.7 guarantees that

d µ P ,m (x) = min S∈Λ P k 1 k p∈S p -x 2 = 1 k p∈N N P k (x) p -x 2 ,
and thus,

d µ P ,m (x) = min S∈Λ P k E C (q) + q -x = E C (bar(x)) + x -bar(x) 2 .
In Euclidean space, it is possible to compute the sublevel sets of d µ P ,m exactly. The function is a power distance and its sublevel sets are unions of balls. However, the complexity problem pointed out in section 4.2 is still valid. The number of balls required to describe a sublevel set is Ω(k

d+1 2 n d+1 2
) [START_REF] Kenneth | Applications of random sampling in computational geometry[END_REF].

Proof of Theorem 4.11

Proof. The first inequality is exactly the same as the one from Theorem 4.5. For the second inequality, let x be a point in R d , and let p be a point of P . Thus,

d P µ P ,m (x) 2 ≤ d µ P ,m (p) 2 + p -x 2 .
Using Lemma 4.14, we get,

d P µ P ,m (x) 2 ≤ E C (bar(x)) + p -bar(x) 2 + p -x 2 ,
and with the inner product, this becomes

d P µ P ,m (x) 2 ≤ E C (bar(x)) + x -bar(x) 2 + 2 p -x 2 + 2 < x -bar(x)|p -x > = d µ P ,m (x) 2 + 2 p -x 2 + 2 < x -bar(x)|p -x > . Note that 2 < bar(x) -x|x -p >= bar(x) -p 2 -bar(x) -x 2 -x -p 2 .
Then we can write the following relation.

d P µ P ,m (x) 2 ≤ d µ P ,m (x) 2 + p -x 2 + bar(x) -p 2 -x -bar(x) 2 .
This relation holds for any point of P . In particular it holds for any of the k nearest neighbors of x. If we take the average over the k nearest neighbors of x and eliminate the negative term -x -bar(x) 2 , we obtain

d P µ P ,m (x) 2 ≤ d µ P ,m (x) 2 + 1 k p∈N N P k (x) p -x 2 + 1 k p∈N N P k (x) bar(x) -p 2 .
Using the definitions of the cell energy and of the distance to the measure, we can write:

d P µ P ,m (x) 2 ≤ d µ P ,m (x) 2 + d µ P ,m (x) 2 + E C (bar(x))
where E C (bar(x)) ≤ d µ P ,m (x) 2 . We conclude that

d P µ P ,m (x) ≤ √ 3 d µ P ,m (x).
The relation between persistence diagrams is exactly as in the proof of Corollary 4.9.

Tightness

The tight example is the point set P of two points a and b on the real line with coordinates 1 and -1.

-1 0 1

a b o
Fix the mass parameter m equal to 1 so that k = 2. It follows that

d µ P ,m (a) = d µ P ,m (b) = 1 2 b -a 2 = √ 2,
and

d µ P ,m (o) = 1 2 o -b 2 + o -a 2 = 1.
We now compute the last interesting value:

d P µ P ,m (o) 2 = d µ P ,m (a) 2 + a -o 2 = 3.
We can thus conclude that d P µ P ,m (o) = √ 3 d µ P ,m (o).

Comparison with witnessed k-distance

Another way of approximating d µ P ,m was proposed in [START_REF] Guibas | Witnessed k-distance[END_REF]. Taking advantage of the power distance expression of d µ P ,m , it reduced the set of barycenters to consider. Selecting only the barycenter which are associated with the k nearest neighbors of a point of P gives a set of size at most |P |.

Definition 4.15. Let P be a finite point set of R d and let m ∈]0, 1] be a mass parameter. The witnessed k-distance is defined as

d W µ P ,m (x) = min p∈P E C (bar(p)) + bar(p) -x 2 .
A bound on the quality of the approximation was given in Lemma 3.3 of [START_REF] Guibas | Witnessed k-distance[END_REF]. We improve this bound and prove it to be at least as good as our approximation. We are not able to prove the tightness of this bound. However, we can give a lower bound on the precision. Using d P µ P ,m will not improve the results compared to the witnessed k-distance but will not downgrade the quality either. Moreover it can be used in a more general setting as we do not need the existence of the barycenters. Theorem 4.16. Let P be a finite point set of R d and let m ∈]0, 1] be a mass parameter. Then,

d µ P ,m ≤ d W µ P ,m ≤ √ 6 d µ P ,m .
The previous version of this theorem used a 3 instead of the √ 6.

Proof. The first inequality is obtained by noticing that d W µ P ,m is a minimum over a smaller set than d µ P ,m . We thus get d µ P ,m ≤ d W µ P ,m . Let x be a point in R d . Thus for any p ∈ P ,

d W µ,m (x) 2 ≤ E C (bar(p)) + bar(p) -x 2 ≤ E C (bar(p)) + bar(p) -p 2 + p -x 2 + 2 bar(p) -p|p -x ≤ d µ,m (p) 2 + 2 p -x 2 + bar(p) -p 2 ≤ 2(d µ,m (p) 2 + p -x 2 ).
Thus, d W µ,m (x) ≤ √ 2d P µ,m (x) and using Theorem 4.11 we can conclude that:

d W µ,m (x) ≤ √ 2 d P µ,m (x) ≤ √ 6 d µ,m (x).
Tightness The tightness of the lower bound is obvious as it suffices to take k = 1 to get an equality between d µ P ,m and d W µ P ,m . However, we do not know if the upper bound is tight. The bound √ 6 can not be improved more than to 1 + √ 2, whose value is greater than √ 5.82. Let us introduce the following example in R d . We fix k = 2d and 0 < < √ 2. The point cloud P consists of 4d 2 points located at the coordinates (0, • • • , 0, α, 0, • • • , 0) with multiplicity 1 when α = 1 or α = -1 and multiplicity 2d -

1 when α = 1 + √ 2 -or α = -1 - √ 2.
The following figure is its representation in dimension 2 where the triangles have multiplicity 1 and the circles have multiplicity 3.

The points are placed such that the k nearest neighbors of any triangle are itself and the k -1 points located at the nearest circle. These k nearest neighbors are also the ones from the circles.

Let us now take a look to the value of the functions at the origin o. Each of the k nearest neighbors of o are distance exactly 1 from o. This allows us to conclude that:

d µ P ,m (o) = 1.
The construction induced that the structure is perfectly symmetric and the set of barycenters W we consider in the witnessed k-distance contains exactly 2d points. These points are located at the coordinates (0,

• • • , 0, α, 0, • • • , 0) where α = 1 + 2d-1 2d ( √ 2
-) or the opposite. Let b be a member of W . Thus we can compute its cell energy:

E C (b) = 1 2d 2d -1 2d ( √ 2 -) 2 + (2d -1) 1 2d ( √ 2 -) 2 = 2d -1 (2d) 3 (2d -1)( √ 2 -) 2 + ( √ 2 -) 2 = 2d -1 (2d) 2 ( √ 2 -) 2 .
All of the points of W are located at the same distance to o. Thus, the witnessed k-distance at the point o is

d W µ P ,m (o) 2 = E C (b) + 1 + 2d -1 2d ( √ 2 -) 2 = 2d -1 (2d) 2 ( √ 2 -) 2 + 1 + 2d -1 d ( √ 2 -) + (2d -1) 2 (2d) 2 ( √ 2 -) 2 = 1 2d + 2d -1 2d 1 + 2( √ 2 -) + ( √ 2 -) 2 = 1 2d + 2d -1 2d (1 + √ 2 -) 2 .
Since we can take as small as we want and make the dimension grow, this relation assures us that we cannot find a better constant than 1 + √ 2 in Theorem 4.16.

The Weighted Rips Filtration

Given a weighted set (P, w) and the associated power distance f (as in (2)), one can introduce a generalization of the Rips filtration that is adapted to the weighted setting as has been done in [START_REF] Guibas | Witnessed k-distance[END_REF]. This construction allows us to approximate the persistence diagram of d µ,m in some cases. Moreover, we show that it is stable with respect to perturbation of the underlying sample (Theorem 5.6) and that it gives a guaranteed approximation to the persistence diagram of the distance to an empirical measure (Theorem 5.7). Furthermore, it has an interest of its own as it is stable for close weighted sets and can therefore be used as a shape signature. Let us consider the sublevel set f -1 (] -∞, α]). It is the union of the balls centered on the points p of P with radius r p (α) = α 2 -w 2 p . By convention, we consider that the ball is empty when the radius is imaginary. We can define the nerve of this union: Definition 5.1. Let (P, w) be a weighted set in a metric space X, then the weighted Čech complex C α (P, w) for parameter α is defined as the union of simplices σ such that p∈σ B(p, r p (α)) = 0.

However, the Čech complex can be difficult to compute due the problem of testing if a collection of metric balls has a common intersection. Instead, we define a weighted version of the Rips complex, which only requires distance computations. Definition 5.2. For a weighted set (P, w) in a metric space X, the weighted Rips complex R α (P, w) for a parameter α is the maximal simplicial complex whose 1-skeleton has an edge for each pair (p, q) such that d X (p, q) < r p (α) + r q (α). The weighted Rips filtration is the sequence {R α (P, w)} for all α ≥ 0.

Remark that if all weights are equal to 0, we are in the classical case of balls with equal radii. We use the weighted Rips filtration to approximate the weighted Čech filtration thanks to the following interleaving. For simplicity, the notation (P, w) indicating the point set P with weights w is omitted in the notation. Proposition 5.3. If (P, w) is a weighted set on a metric space X, then for all α ∈ R:

C α ⊆ R α ⊆ C 2α .
Proof. Let α be a real number. The first inclusion is obtained by the definition of the weighted Rips complex that gives C α ⊆ R α .

For the other inclusion, let σ be a simplex of R α . We fix p 0 to be the point of σ with the greatest weight. This implies especially that for any p ∈ P , r p (α) ≥ r p0 (α).

Since σ ∈ R α , we get that, for all p and q in P , we have d X (p, q) ≤ r p (α) + r q (α) with both radius real. To prove that σ ∈ C 2α we need to prove that: p∈σ B(p, r p (2α)) = 0.

It will suffice to prove that p 0 belongs to this intersection. For each p ∈ σ:

d X (p, p 0 ) ≤ r p (α) + r p0 (α) ≤ 2 r p (α) = (2α) 2 -4w 2 p ≤ r p (2α).

Stability

The persistence diagram of a weighted Rips filtration {R α (P, w)} is stable under small perturbations of the set P . It can thus be used in applications like signatures in the spirit of [START_REF] Chazal | Gromov-hausdorff stable signatures for shapes using persistence[END_REF].

Speaking of the persistence diagram of a weighted Rips filtration requires that the filtration is q-tame. This is always the case when the set P is compact as shown in the following proposition. Proposition 5.4. Let P be a subset of a metric space X and let w : X → R be a function. If P is compact, then {R α (P, w)} α∈R is q-tame.

This will be deduced from the following technical lemma. Lemma 5.5. Let P , Q be two subsets of a metric space X and let w : X → R be a t-Lipschitz function. Then H * ({R α (P, w)}) and H * ({R α (Q, w)}) are -interleaved for = (1 + t)d H (P, Q).

Proof. We need to show that the there exists -homomorphisms π P * and π Q * such that π P * π Q * = 1 2 H * (Rα(P,w)) and π Q * π P * = 1 2 H * (Rα(Q,w)) . To do so, we need three steps. First, we build simplicial maps R α (P, w) → R α+ (Q, w) and R α (Q, w) → R α+ (P, w) for every α. Then, we show that these simplicial maps induce -homomorphisms. Finally, we show that the simplicial maps are contiguous and thus the two persistence modules areinterleaved.

The simplicial maps i β α : R α (P, w) → R β (P, w) and j β α : R α (Q, w) → R α (Q, w) for α < β are induced by the canonical inclusion. We consider two maps π P : Q → P and π Q : P → Q such that d X (p, π Q (p)) ≤ d H (P, Q) and d X (q, π P (q)) ≤ d H (P, Q) for any p ∈ P and q ∈ Q. By definition of the Hausdorff distances, such maps always exist. Let us show that these maps induce simplicial maps.

Let us consider the function π P and let us fix α > 0. Let (q , q ) be an edge of R α (Q, w). It means that B(q , r q (α)) ∩ B(q , r q (α)) = ∅. Lemma 4.2 implies that B(q, r q (α)) ⊂ B(π P (q), r π P (q) (α + (1 + t)d H (P, Q))) for any q ∈ Q. Thus, (π P (q ), π ( q )) is an edge of R α+ (P, w) because: B(π P (q ), r q (α + )) ∩ B(π P (q ), r q (α + )) ⊃ B(q , r q (α)) ∩ B(q , r q (α)) = ∅.

As R α (P, w) is a clique complex for any α, this is sufficient to prove that π P induce a family of simplicial maps {π P α+ α }. The roles of P and Q are symmetric. Therefore, the result holds for π Q as well.

Furthermore π P induces an -homomorphism π P * at the homology level. For any α < β, i β+ α+ • π P α+ α =π P β+ β

• j β α because the maps i β+ α+ and j α are induced by the the canonical inclusion while the two others simplicial maps are induced by the same map π P : Q → P . Hence the two compositions are the same map and thus guarantees that π P * is an -homomorphism. Again, this results can be applied to π Q to get an -homomorphism π Q * .

To prove that π P * π Q * = 1 2 H * (Rα(P,w)) , we prove that π P α+ α

• π Q α α-and i α+ α-are contiguous for any α.

Let us fix α and let (p, p ) be an edge of R α-(P, w). By definition, B(p, r p (α-))∩B(p , r p (α-)) = ∅. Moreover, using Lemma 4.2 we get:

B(p, r p (α -)) ⊂ B(π Q (p), r π Q (p) (α)) ⊂ B(π P • π Q (p), r π P •π Q (p) (α + )).
The same holds for p and thus:

B(p, r p (α + )) ∩ B(π P • π Q (p), r π P •π Q (p) (α + )) ∩B(p , r p (α + )) ∩ B(π P • π Q (p ), r π P •π Q (p ) (α + )) = ∅.

Thus the tetrahedron {i

α+ α-(p), i α+ α-(p ), π P α+ α •π Q α α-(p), π P α+ α •π Q α α-(p )} is in C α+ (P, w) ⊂ R α+ (P, w). Lemma 2.7 guarantees that π P α+ α • π Q α α-and i α+ α-are contiguous. From before, {π P α+ α • π Q α α-} induces the 2 -homomorphism π P * π Q * . By definition, {i α+ α-} induces 1 2
H * (Rα(P,w)) . By contiguity of the simplicial maps, we have equality of the 2 -homomorphisms and therefore π P * π Q * = 1 2 H * (Rα(P,w)) . By symmetry of the roles of P and Q, {R α (P, w)} and {R α (Q, w)} are -interleaved.

Proof of Proposition 5.4. We will show that, for any > 0, one can build a finite persistence module which is -interleaved with the persistence module of {R α (P, w)}. A finite persistence module is a fortiori locally finite and Theorem 4.19 of [START_REF] Chazal | The structure and stability of persistence modules[END_REF] induces the q-tameness of {R α (P, w)}.

Let us fix > 0. P is compact. As a consequence, there exists a finite point set Q of P such that d H (P, Q) ≤ 1+t . The persistence module of {R α (Q, w)} is finite and therefore locally finite. Moreover, using Lemma 5.5, {R α (Q, w)} and {R α (P, w)} are -interleaved. Hence Theorem 4.19 of [START_REF] Chazal | The structure and stability of persistence modules[END_REF] induces the q-tameness of {R α (P, w)}.

Notice that the simplicial maps π P and π Q are not necessarily uniquely defined. However, if π P and π P are two maps verifying the construction property, then the induced simplicial maps are contiguous and therefore the induced homomorphisms are identical.

The persistence diagrams of weighted Rips filtrations are related by the following:

Theorem 5.6. Let P and Q be two compact subsets of a metric space X. Let w : X → R be a t-Lipschitz function. Then,

d B (Dgm({R α (P, w)}), Dgm({R α (Q, w)})) ≤ (1 + t)d H (P, Q).
Proof. P and Q are two compact sets and thus the diagrams are well-defined thanks to Proposition 5.4 that guarantees the q-tameness of the filtrations. Lemma 5.5 implies that H * ({R α (P, w)}) and H * ({R α (Q, w)}) are (1 + t)d H (P, Q)-interleaved. The relation between the persistence diagrams is then obtained by applying Theorem 2.6.

Remark 2. When P and Q are two compact metric spaces, Theorem 5.6 can be extended using the notion of correspondence as in [START_REF] Chazal | Persistence stability for geometric complexes[END_REF]. Notice that the correspondence has to induce bounded distortion on the weights as well as on the distances.

Approximation

To use the weighted Rips filtration to approximate the persistence diagram of the distance to a measure, we need to restrict the class of spaces considered. If the intersection of any finite number of balls in X is either contractible or empty, X is said to have the good cover property. Then the Čech complex has the same homology as the union of balls, of which it is the nerve, by the Nerve Theorem [START_REF] Hatcher | Algebraic Topology[END_REF]. We can also compute the persistence diagram thanks to the Persistent Nerve Lemma [START_REF] Chazal | Towards persistence-based reconstruction in Euclidean spaces[END_REF]. We obtain an approximation of Dgm(d µ P ,m ) using the weighted Rips filtration.

Theorem 5.7. Let X be a triangulable metric space with the good cover property and let P be a finite point set of X, then on a logarithmic scale:

d log B (Dgm(d µ P ,m ), Dgm({R α (P, d µ P ,m )})) ≤ ln(2 √ 5).
Proof. Given that X is triangulable, we know that the sublevel sets filtration of d µ P ,m is q-tame by Proposition 3.5. The persistence diagram Dgm(d µ P ,m ) is thus well-defined. Recall that d µ P ,m is a 1-Lipschitz function (see Proposition 3.4). P is a compact subset of X and therefore Dgm(R α (P, d µ P ,m )) is well-defined according to Proposition 5.4.

We approximate d µ P ,m with d P µ P ,m . The result of Theorem 4.5 gives us a √ 5 multiplicative interleaving. For any α ∈ R, By the Persistent Nerve Lemma, the sublevel sets filtration of d P µ P ,m (a union of balls of increasing radii) has the same persistent homology as nerve filtration. Thus, we can use weighted Rips filtration to approximate the persistence diagram:

d µ P ,m (] -∞, α]) ⊂ d P µ P ,m (] -∞, √ 2α]) ⊂ d µ P ,m (] -∞, √ 10
d log B (Dgm(d P µ P ,m ), Dgm({R α (P, d µ P ,m )}) ≤ ln(2).
The triangle inequality for the bottleneck distance gives the desired inequality.

The Sparse Weighted Rips filtration

The weighted Rips filtration presented in the previous section has the desired approximation guarantees, but like the Rips filtration for unweighted points, it usually grows too large to be computed in full. In [START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF], it was shown how to construct a filtration {S α } called the sparse Rips filtration that gives a provably good approximation to the Rips filtration and has size linear in the number of points for metrics with constant doubling dimension (see Section 6.1 for the construction). Specifically, for a user-defined parameter ε, the log-bottleneck distance between the persistence diagrams of the Sparse Rips filtration and the Rips filtration is at most ε. The goal of this section is to extend that result to weighted Rips filtrations. The sparse Rips filtration cannot be used directly here, since the power distance does not induce a metric. Indeed, even the case of setting all weights to some large constant yields a persistence diagram that is far from the persistence diagram of the Rips filtration of any metric space. This follows because individual points in a Rips filtration appear at time zero, but this is not the case in the weighted Rips filtration.

Even if one were to construct a metric whose Rips filtration exactly matched that of the weighted Rips filtration, there are simple examples where that metric would necessarily have very high doubling dimension, making previous methods unsuitable. For example, consider a set of points in the unit interval [0, 1], with a constant weight function that assigns a weight of 1 to every point. Although the points lie in a 1-dimensional space, the weighted distance function has doubling dimension log n because all of the points are within a weighted distance of 2, whereas every pair has weighted distance at least 1. So the doubling constant would be n and the doubling dimension would be log n despite that the input was 1-dimensional. Thus, any construction that depends on low doubling dimension will blowup when confronted with such weighted examples.

For the rest of this section, we fix a weighted point set P in a metric space X, where the weight function w : X → R is t-Lipschitz, for some constant t. To simplify notation, we let R α denote the weighted Rips complex R α (P, w).

The sparse weighted Rips filtration, {T α }, is defined as

T α = S α ∩ R α .
The (unweighted) sparse Rips filtration {S α } captures the underlying metric space and the weighted Rips filtration {R α } captures the structure of the sublevel sets of the power distance function. Computing {T α } can be done efficiently by first computing {S α } and then reordering the simplices according to the birth time in {R α }. This is equivalent to filtering the complex S ∞ . Note that the sparsification depends only on the metric, and not on the weights. Thus, the same sparse Rips complex can be used as the underlying complex for different weight functions. We also simplify the construction of {S α } by using a furthest point sampling instead of the more complex structure of net tree. The technical challenge is to relate the persistence diagram of this new filtration to the persistence diagram of the weighted Rips filtration as in the following theorem. Theorem 6.1. Let (P, w), be a finite, weighted subset of a metric space X with t-Lipschitz weights. Let ε < 1 be a fixed constant used in the construction of the sparse weighted Rips filtration {T α }. Then,

d log B (Dgm({T α }), Dgm({R α })) ≤ ln 1 + √ 1 + t 2 ε 1 -ε .
Since these filtrations are not interleaved, the only hope is to find an interleaving of the persistence modules, which requires finding suitable homomorphisms between the homology groups of the different filtrations. After detailing the construction of the sparse Rips filtration with the furthest point sampling, the rest of this section proves Theorem 6.1.

Sparse Rips complexes

Let (p 1 , . . . , p n ) be a greedy permutation of the points P in a finite metric space X. That is, p i = argmax p∈P \Pi-1 d X (p, P i-1 ), where P i-1 = {p 1 , . . . , p i-1 } is the (i -1) st prefix. We define the insertion radius λ pi of point p i to be λ pi = d X (p i , P i-1 ).

To avoid excessive superscripts, we write λ i in place of λ pi when we know the index of p i . We adopt the convention that λ 1 = ∞ and λ n+1 = 0. The greedy permutation has the nice property that each prefix P i is a λ i -net in the sense that 1. d X (p, P i ) ≤ λ i for all p ∈ P .

2. d X (p, q) ≥ λ i for all p, q ∈ P i .

We extend these nets to an arbitrary parameter γ as

N γ = {p ∈ P | λ p > γ}. N γ = {p ∈ P | λ p ≥ γ}.
Note that for all p ∈ P , d X (p, N γ ) ≤ γ and d X (p, N γ ) < γ.

One way to get a sparse Rips-like filtration is to take a union of Rips complexes on the nets N γ . However, this can add significant noise to the persistence diagram compared to the Rips filtrations. This noise can be diminished by a careful perturbation of the distance. For a point p, the perturbation varies with the scale and is defined as follows:

s p (α) =      0 if α ≤ λp ε α - λp ε if λp ε < α < λp ε(1-ε) εα if λp ε(1-ε) ≤ α 0 0 λp λp (1-) s p = α
Note that s p is 1-Lipschitz. The resulting perturbed distance is defined as f α (p, q) = d X (p, q) + s p (α) + s q (α). Definition 6.2. Given the nets N γ and the distance function f α , we define the sparse Rips complex at scale α as

Q α = {σ ⊂ N ε(1-ε)α | ∀p, q ∈ σ, f α (p, q) ≤ 2α}.
On its own, the sequence of complexes {Q α } does not form a filtration. However, we can build a natural filtration by defining Definition 6.3. The sparse Rips filtration is defined as:

S β = α≤β Q α .

Projection onto Nets

To relate sparse Rips complexes with Rips complexes, we build a collection of projections of the points onto the nets.

π α (p) = p if p ∈ N ε(1-ε)α argmin q∈Nεα d X (p, q) otherwise
For any scale α, the projection π α maps the points of P to the net N ε(1-ε)α . Note that π α is a retraction onto N ε(1-ε)α .

The following are the four main lemmas we will use with respect to the perturbed distance functions and projections. The projections will be used extensively to induce maps between simplicial complexes.

First, we prove that edges do not disappear as the filtration grows.

Lemma 6.4. If f α (p, q) ≤ 2α ≤ 2β then f β (p, q) ≤ 2β.
Proof. The proof follows from the definitions f α and f β , the Lipschitz property of the perturbations s p and s q , and the hypothesis as follows.

f β (p, q) = d X (p, q) + s p (β) + s q (β) ≤ d X (p, q) + s p (α) + (β -α) + s q (α) + (β -α) = f α (p, q) + 2(β -α) ≤ 2α + 2(β -α) = 2β.
Next, we show that the distance between a point and its projection is at most the change in the perturbed distance. Lemma 6.5. For all q ∈ P , d X (q, π α (q)) ≤ s q (α) -s πα(q) (α), and in particular, d X (q, π α (q)) ≤ εα.

Proof. Both statements are trivial if q ∈ N ε(1-ε)α , because that would imply that π α (q) = q. So, we may assume that π α (q) is the nearest point to q in N εα It follows that d X (q, π α (q)) ≤ εα.

Moreover, λ q ≤ ε(1 -ε)α, and thus s q (α) = εα. Also, since π α (q) ∈ N εα , it must be that λ πα(q) > εα and so s πα(q) = 0. Combining these statements, we get d X (q, π α ) ≤ εα = s q (α) -s πα(q) (α). Now, we prove that replacing a point with its projection does not increase the perturbed distance. Lemma 6.6. For all p, q ∈ P and all α ≥ 0, f α (p, π α (q)) ≤ f α (p, q). Proof. The statement follows from the definition of f α , the triangle inequality, and Lemma 6.5 as follows.

f α (p, π α (q)) = d X (p, π α (q)) + s p (α) + s πα(q) (α) ≤ d X (p, q) + d X (q, π α (q)) + s p (α) + s πα(q) (α) ≤ d X (p, q) + s p (α) + s q (α) = f α (p, q).

Sometimes the projections induce contiguous simplicial maps

In this section, we look at the maps between simplicial complexes that are induced by the projection functions π α . We are most interested in the case when a pair of projections π α and π β induce contiguous simplicial maps between sparse Rips complexes (Lemma 6.9) or weighted Rips complexes (Lemma 6.10). First, we need a couple lemmas that describe the effect of different projections on the endpoints of an edge in sparse or weighted Rips complexes. Lemma 6.7. Let α, β, γ, and i be such that λi+1 ε(1-ε) ≤ α ≤ β ≤ γ ≤ λi ε(1-ε) . If an edge (p, q) is in Q ρ for some ρ ≤ γ then the edge (π α (p), π β (q)) ∈ Q γ .

Proof. First, it is easy to check that the conditions on α, β, γ, and i imply that π α (p) and π β (q) are in N ε(1-ε)γ , which is the vertex set of Q γ . So, it will suffice to prove that f γ (π α (p), π β (q)) ≤ 2γ. Next we consider three cases depending on the value of ρ in relation to α and β. Case 1: If α, β ≤ ρ then π α (p) = p and π β (q) = q. So, using Lemma 6.4 and the assumption ρ ≤ γ, we see that f γ (π α (p), π β (q)) = f γ (p, q) ≤ 2γ. Case 2: If α ≤ ρ < β then π α (p) = p and Lemma 6.4 implies that f β (p, q) ≤ 2β.

f γ (π α (p), π β (q)) = f γ (p, π β (q)) ≤ f β (p, π β (q)) + 2(γ -β) ≤ f β (p, q) + 2(γ -β) ≤ 2γ. Case 3: If ρ < α, β then Lemma 6.4 implies that f α (p, q) ≤ 2α. f γ (π α (p), π β (q)) ≤ f β (π α (p), π β (q)) + 2(γ -β) ≤ f β (π α (p), q) + 2(γ -β) ≤ f α (π α (p), q) + 2(γ -β) + 2(β -α) ≤ f α (p, q) + 2(γ -β) + 2(β -α) ≤ 2γ. Lemma 6.8. Let (p, q) be an edge of R δ with α, β ≤ δ 1+ε , then (π α (p), π β (q)) ∈ R κδ , where κ = 1+ √ 1+t 2 ε 1-ε .
Proof. First, note that the projection functions satisfy the following inequalities.

d X (p, π α (p)) ≤ εα ≤ εδ 1 -ε d X (q, π β (q)) ≤ εβ ≤ εδ 1 -ε
So, by applying the triangle inequality, the definition of an edge in R δ , and Lemma 4.2, we get the following.

d X (π α (p), π β (q)) ≤ d X (p, q) + 2εδ 1 -ε ≤ r p (δ) + εδ 1 -ε + r q (δ) + εδ 1 -ε ≤ r p δ 1 -ε + εδ 1 -ε + r q δ 1 -ε + εδ 1 -ε ≤ r πα(p) (κδ) + r π β (q) (κδ).
This is precisely the condition necessary to guarantee that (π α (p), π α (q)) ∈ R κδ as desired.

The following two lemmas follow easily from repeated application of the preceding lemmas. Lemma 6.9. Two projections π α and π β induce contiguous simplicial maps from Q ρ → Q β whenever ρ ≤ β and there exists i so that λi+1

ε(1-ε) ≤ α ≤ β ≤ λi ε(1-ε) . Proof.
Let us fix ρ ≤ β and take (p, q) an edge from Q ρ . Given that Q ρ and Q β are cliques complexes, we can get the result from Lemma 2.7 if we show that the tetrahedron {π α (p), π α (q), π β (p), π β (q)} is in Q β . We only need to prove that all edges of the tetrahedron belongs to Q β .

We apply Lemma 6.7, while replacing γ by β and β by α. Thus we obtain (π α (p), π α (q)) ∈ Q β . Let us repeat this operation with α = β = γ thus we get (π β (p), π β (q)) ∈ Q β . The last two edges are given by replacing γ by β and choosing correctly the role of p and q. Lemma 6.10. Two projections π α and π β induce contiguous simplicial maps from R δ → R κδ , where κ = 1+ √ 1+t 2 ε 1-ε whenever α, β ≤ δ 1-ε . Proof. The previous proof can be applied to get the result, while replacing Lemma 6.7 by Lemma 6.8.

Sparse filtrations and power distance functions

We define a sparse filtration that gives a good approximation to the weighted Rips filtration {R α } in terms of persistent homology. It is simply the intersection of the weighted Rips complex and the union of sparse Rips complexes at different scales.

T α = R α ∩ S α .
Our main goal is to show that the filtration {T α } has a persistence diagram that is similar to that of {R α }. To do this we will demonstrate a multiplicative interleaving between these filtrations, where the interleaving constant is

κ = 1 + √ 1 + t 2 ε 1 -ε .
Specifically, we show that for all α ≥ 0, the following diagram commutes at the homology level.

R α π α 1-ε " " / / R κα T α / / ? O O T κα ? O O
We first need to check that the projection π α 1-ε indeed induces a simplicial map from R δ to T κδ .

Datasets

For the first two parts, we consider the set of points in R 3 obtained by sampling regularly the skeleton of the unit cube with 116 points. Then we add four noise points in the center of four of its faces such that two opposite faces are empty. The diagrams obtained with our various approximations have very similar looks. We only show the one obtained with the sparse Rips filtration with a parameter = 0.5 in Figure 6.

To compare diagrams, we use the bottleneck distances between the diagrams. Figure 7 shows the distance matrix between the various diagrams, while Figure 8 shows some bottleneck distances between persistence diagrams of different dimensions. Note that Dgm(d P ) corresponds to the diagram obtained by using the distance function to the point cloud. The largest difference is between Dgm(Skel) and Dgm(d µ P ,m ). This is partly due to an effect of shifting while using the distance to a measure. After this initial shift, the distance are small compared to the theoretical bounds. Notice that the different steps of the approximation do not have the same effect on all dimensions.

All diagrams obtained by the different approximations are closer to Dgm(Skel) than the persistence diagram of the distance to the point cloud, Dgm(d P ) given in Figure 9. For inference purposes, one crucial parameter is the signal-to-noise ratio. We define it as the ratio between the smallest lifespan of topological feature we aim to infer and the longest lifespan of noise features. A ratio of 1 corresponds to a signal that is not differentiable from the noise and ∞ corresponds to a noiseless diagram. In our example, only the dimensions 1 and 2 are relevant as the dimension 0 diagram corresponding to connected components has only one relevant feature and its lifespan is infinite. Results are listed in Figure 10. Signal-to-noise ratios are clearly better than the one of Dgm(d P ). Some of the approximation steps improve the ratio. This is due to two phenomena.

When one goes from d µ P ,m to d P µ P ,m , the filtration eliminates the cells of the k th order Voronoi diagram that are far from the point cloud. These cells induce local minima that produce noise features in the diagrams. Removing them cleans parts of the diagram. The same phenomenon happens with the witnessed k-distance perviously mentioned.

Using the Rips filtration instead of the Čech also reduces some noise. It eliminates artifacts from simplices that are introduced and almost immediately killed in the Čech complex due to balls that intersect pairwise but have no common intersection.

Stability

The weighted Rips filtration is stable with respect to noise. We illustrate this by studying the effect of an isotropic noise on our skeleton of a cube. We consider three different standard deviations for our noise. Figure 11 shows the bottleneck distances between the persistence diagram of the sparse weighted Rips structure with the Gaussian noise and the one without Gaussian noise. Inferring correctly the homology of the cube skeleton is possible with standard deviation 0.05 and 0.1. Figure 13 shows the persistence diagram obtained with a standard deviation of 0.1. The ∞ in the 0.5 case in dimension 2 is not relevant as there is no noise but the feature is too small compared to the rest of the diagram as shown in Figure 14. Note that 0.5 corresponds to half of the side of the cube, and thus, it is logical to be unable to retrieve any useful information. Some structure appears even with standard deviation as large as 0.5. The three bigger features in dimension 1 are relevant. However, we miss two elements and it is difficult to decide where to draw the frontier between relevant and irrelevant features.

Sparsification efficiency

We introduced sparsification in Section 6.4 to reduce the size of the Rips filtration. The method introduced a new parameter , and the size of the filtration depends heavily on . The evolution of the size of the filtration depending on the parameter is given in Figure 15. The minimum size is reached around = .86. This minimum depends on the structure of the dataset. For example, considering a set of points uniformly sampled in a square, we obtain filtrations with monotonously decreasing size. While theoretical results depend on the doubling dimension of the ambient apces, experimental results strongly suggests that it depends on the intrinsic doubling dimension, which can be vary at different scales.

The filtration size is nearly constant after a rapid decrease. In this example, the size is of order 10 7 simplices for an input of 10 5 vertices. Computing persistent homology is tractable for any value in this range. Structure in the data helps reduce the complexity of the sparse filtration.

Conclusion

In this paper, we generalize several aspects of the existing theory on the persistent homology of distances to measures from Euclidean space to general metric spaces. Then, we showed how to efficiently approximate the sublevels these distance functions with a linear number of metric balls. We gave a detailed analysis of the tightness of this approximation.

We then showed how to give a sparse filtration that gives a guaranteed close approximation to the persistent homology of the distance to the measure. This last construction was given in the more general context of power distances. Thus, we have given a way to efficiently compute the persistent homology of the sublevel set filtration of any power distance function built on points in metric space of low doubling dimension. Since power distances can be used to approximate many different kinds of functions, we expect this technique will find many more uses in the future.

A different perspective on our approach is that we use the sparse Rips filtration analogously to how one might use a grid in Euclidean space. It provides a structure over which one can go on to study many different functions.

Lastly, we showed that this approach can be made practical, by providing some experimental results and analysis.

Figure 1 :

 1 Figure 1: From left to right, two sublevel sets for d P , d µ P ,m , and d P µ P ,m with m = 3 |P | .The first is too sensitive to noise and outliers. The second is smoother, but substantially more difficult to compute. The third is our approximation, which is robust to noise, efficient to compute, and compact to represent.

Theorem 3 .

 3 1 is now obtained by combining Theorem 2.4 and Proposition 3.5.Proof of Theorem 3.1. Theorem 3.3 guarantees that:

Corollary 4 . 9 . 2 )

 492 Let P be a finite point set of a triangulable metric space X and m ∈]0, 1] be a mass parameter. Then,d log B (Dgm(d µ P ,m ), Dgm(d P µ P ,m )) ≤ ln( √5). Proof. Corollary 4.8 implies that ln(d µ P ,m ) -ln( √ ≤ ln(d P µ P ,m ) ≤ ln( √ 5) + ln(d µ P ,m ). The sublevel sets of ln(d µ P ,m ) and ln(d P µ P ,m ) are thus ln( √ 5)-interleaved and Theorem 2.4 applies.

Proposition 4 . 10 .

 410 The bounds of Corollary 4.8 are tight.

1 ) 16 ) = 16 - 6 d 2 d

 11662 All the points p i have the same value for d µ P ,m . It is easy to compute d P µ P ,m at q and o d P µ P ,m (o) 2 = d µ P ,m (p 1 ) 2 + |p 1 -o| 2 = 5 -2 d d P µ P ,m (q) 2 = d µ P ,m (p 1 ) 2 + |p 1 -q| 2 = 8 -When d increases, the ratio d P µ P ,m (o) dµ P ,m (o) tends to √ 5, while d P µ P ,m (q)

Definition 4 . 13 .

 413 Let P be a point set of R d and let k ≤ |P |. Given S ∈ Λ P k , we fix q = 1 k p∈S p and define the cell energy as

  d P µ P ,m ]). So, Theorem 2.4 implies d log B (Dgm(d µ P ,m ), Dgm(d P µ P ,m )) ≤ ln(

Figure 2 :

 2 Figure 2: Skeleton of a cube with outliers

Figure 3 :

 3 Figure 3: Persistence diagram of a cube skeleton without noise

Figure 4 :

 4 Figure 4: Spiral on a torus

Figure 5 :

 5 Figure 5: Dgm(d µ P ,m ) for the cube skeleton with outliers with k = 5

Figure 6 :

 6 Figure 6: Dgm({T α }) for the cube skeleton with outliers with k = 5 and = .5 Dgm(Skel) Dgm(d µ P ,m ) Dgm(d P µ P ,m ) Dgm(R α ) Dgm(T α ) Dgm(d P ) Dgm(Skel) 0 .1528 .1473 .1473 .1817 .25 Dgm(d µ P ,m ) .1528 0 .09872 .0865 .1183 .2543 Dgm(d P µ P ,m ) .1473 .09872 0 .0459 .1084 .2642 Dgm(R α ) .1473 .0865 .0459 0 .1128 .2598 Dgm(T α ) .1817 .1183 .1084 .1128 0 .2484 Dgm(d P ) .25 .2543 .2642 .2598 .2484 0

Figure 9 : 1 Figure 10 :

 9110 Figure 9: Dgm(d P ) for the cube skeleton with outliers Diagram dim 1 dim 2 Dgm(Skel) ∞ ∞ Dgm(d µ P ,m ) 247 2.74 Dgm(d P µ P ,m ) 69.8 43 Dgm(R α (P, d µ P ,m )) ∞ ∞ Dgm(T α (P, d µ P ,m )) 132 ∞ Dgm(d P ) 5.66 1 Figure 10: Signal to noise ratios

Figure 11 :

 11 Figure 11: d B between Dgm({T α }) with and without Gaussian noiseUnsurprisingly, the bottleneck distance is increasing with standard deviation of the noise. The signalto-noise ratio shown in Figure12is more interesting. Standard deviation 0 .05 .1 .5 Ratio in dimension 1 132 8.27 3.17 1.04 Ratio in dimension 2 ∞ ∞ 100.2 ∞

Figure 12 :

 12 Figure 12: Signal to noise ratio of Dgm({T α }) depending on noise intensity

Figure 13 : 1 Figure 14 :

 13114 Figure 13: Persistence diagram of {Tα} with k = 5, = 0.5 and a Gaussian noise with standard deviation 0.1

Figure 15 :

 15 Figure 15: Size of the filtration depending on for the spiral with a Gaussian noise of standard deviation .05

  ) Dgm(R α ) Dgm(T α ) Dgm(d P )

	Dgm(Skel)	0	.1528	.1473	.1473	.1817	.25
	Dgm(d µ P ,m )	.1528	0	.09872	.0865	.1183	.2543
	Dgm(d P µ P ,m )	.1473	.09872	0	.0459	.1084	.2642
	Dgm(R α )	.1473	.0865	.0459	0		.1128	.2598
	Dgm(T α )	.1817	.1183	.1084	.1128	0	.2484
	Dgm(d P )	.25	.2543	.2642	.2598	.2484	0
		Figure 7: Matrix of distances for the bottleneck distance
		Dgm(A)		Dgm(B)	dim 0 dim 1 dim 2
		Dgm(Skel)		Dgm(d µ P ,m )	.05202 .1528 .1495
		Dgm(d µ P ,m ) Dgm(d P µ P ,m )	Dgm(d P µ P ,m ) Dgm(R α (P, d µ P ,m )) .0007 .09872 .0195 .0972 .0044 .0459
	Dgm(R α (P, d µ P ,m )) Dgm(T α (P, d µ P ,m ))	.0872	.1128 .0026
		Dgm(Skel)		Dgm(d P µ P ,m )	.0405	.1473 .0982
		Dgm(Skel)	Dgm(T α (P, d µ P ,m ))	.1026	.1817	.098
		Dgm(Skel)		Dgm(d P )	.25	.2071 .1481
		Figure 8: Bottleneck distances between diagrams

Acknowledgements

The authors acknowledge the support of the ANR TopData (ANR-13-BS01-0008) and the ERC Grant GUDHI. The authors also wish to thank the anonymous referees for their helpful that contributed to the improve of the paper.

 Lemma 6.11. For all α > 0, the projection π α 1-ε induces a simplicial map from R α → T κα , where κ = 1+ √ 1+t 2 ε 1-ε .

Proof. We show that for each edge (p, q) ∈ R α , there is a corresponding edge (π α 1-ε (p), π α 1-ε (q)) ∈ R κα ∩ Q α 1-ε . Since the latter complex is a clique complex, this will imply that for all σ ∈ R α , we have

Next, we need to show that (π α

Now, we give conditions when two projections induce contiguous simplicial maps between the sparse weighted Rips complexes T δ and T κδ . Lemma 6.12. Two projections π α and π β induce contiguous simplicial maps from T δ → T κδ , where

Proof. We simply observe that for any σ ∈ T δ , σ ∈ Q ρ for some ρ ≤ δ. If ρ ≤ β then Lemma 6.9 implies

Now, by Lemma 6.10, we have that π α (σ)∪π β (σ) ∈ R κδ . So, we have that π α (σ)∪π β (σ) ∈ R κδ ∩S κδ = T κδ as desired.

We can now give the proof of the interleaving which will imply the desired approximation of the persistent homology. Lemma 6.13. For all α > 0, the following diagram commutes the homology level.

Proof. By Lemma 6.10, the projection π α 1-ε and the inclusion π 0 are contiguous and thus produce identical homomorphisms at the homology level. For the lower triangle it will suffice to show that homomorphism induced by π α 1-ε commutes with that produced by the inclusion π 0 . Let φ i = π λ i 1-ε for i = 1, . . . , n + 1. Now, Lemma 6.12 implies that φ i and φ i+1 are contiguous. So, choosing k such that λ k ≤ εα < λ k-1 , we can apply Lemma 6.12 repeatedly to conclude that

Numerical illustration

In this section, we illustrate our results from three different perspectives: the quality of the approximation, the stability of the diagrams with respect to noise, and the size of the filtration after sparsification. We used the ANN library [START_REF] Mount | ANN: Library for approximate nearest neighbour searching[END_REF] for the k-nearest neighbors search and code from Zomorodian following [START_REF] Zomorodian | Computing persistent homology[END_REF] for the persistence. The topology of the union of balls is acquired through the α-shapes implementation from the CGAL library [START_REF] Kai | 3D alpha shapes[END_REF].