Claire Brécheteau
email: claire.brecheteau@inria.frurl

A statistical test of isomorphism between metric-measure spaces using the distance-to-a-measure signature *

Keywords: MSC 2010 subject classifications: Primary 62G10; secondary 62G09 statistical test, subsampling, metric-measure spaces, distance to a measure, (Gromov)-Wasserstein distances

We introduce the notion of DTM-signature, a measure on R that can be associated to any metric-measure space. This signature is based on the function distance to a measure (DTM) introduced in 2009 by Chazal, Cohen-Steiner and Mérigot. It leads to a pseudo-metric between metric-measure spaces, that is bounded above by the Gromov-Wasserstein distance. This pseudo-metric is used to build a statistical test of isomorphism between two metric-measure spaces, from the observation of two N -samples.

The test is based on subsampling methods and comes with theoretical guarantees. It is proven to be of the correct level asymptotically. Also, when the measures are supported on compact subsets of R d , rates of convergence are derived for the L 1 -Wasserstein distance between the distribution of the test statistic and its subsampling approximation. These rates depend on some parameter ρ > 1. In addition, we prove that the power is bounded above by exp(-CN 1/ρ ), with C proportional to the square of the aforementioned pseudo-metric between the metric-measure spaces. Under some geometrical assumptions, we also derive lower bounds for this pseudo-metric.

An algorithm is proposed for the implementation of this statistical test, and its performance is compared to the performance of other methods through numerical experiments.

Introduction

Very often data comes in the form of a set of points from a metric space. A natural question, given two such sets of data, is to decide whether they are similar. For example, do they come from the same distribution? Are their shapes similar? From the seminal two-samples tests of Kolmogorov-Smirnov specific to measures on R or even on R d , to the more recent kernel two-sample tests by Gretton et al. [START_REF] Gretton | A Kernel Two-Sample Test[END_REF], where the data are sent into a reproducing kernel Hilbert space and then compared through the maximum mean discrepancy, the literature is abundant and proficient on the subject of two-sample testing. Note that an overview of Wasserstein-distance-based two-sample tests appears in [START_REF] Ramdas | On Wasserstein Two Sample Testing and Related Families of Nonparametric Tests[END_REF].

Unfortunately, testing equality of two measures from samples may be compromised when the data are not embedded into the same space, or if the two systems of coordinates in which

The signature we introduce in this paper is based on the distance to a measure, which is defined in [START_REF] Chazal | Geometric Inference for Probability Measures[END_REF] as a generalisation of the function distance to a compact set and can be defined as follows.

Let (X , δ) be a metric space, equipped with a Borel probability measure µ. Given m in [0, 1], the pseudo-distance function is defined at any point x of X , by This function can be easily computed when the measure of interest is uniform on a finite set of N points: μN = 1 N N i=1 δ Xi with the X i s in a metric space (X , δ). Indeed, in this case, δ μN ,l (x) is the distance between x and its lN nearest neighbour, denoted by X ( lN ) . As a consequence, the distance to the measure μN with mass parameter m = k N for some k in {1, . . . , N } at a point x of X satisfies:

d μN ,m (x) = 1 k k i=1 δ(X (i) , x).
The distance to the measure μN at x ∈ X is thus equal to the mean of the distances to its k-nearest neighbours in {X 1 , X 2 . . . , X N }.

The DTM-signature is then defined as follows.

Definition 1.3 (DTM-signature). The DTM-signature associated to some mm-space (X , δ, µ), denoted d µ,m (µ), is the distribution of the real-valued random variable d µ,m (X ) where X is some random variable from the distribution µ.

More generally, it will be of interest in this paper to consider the push-forward of a measure with the distance-to-a-measure function associated to another measure. Notation 1.1. Let µ and µ be two Borel probability measures on the same metric space (X , δ). We denote by d µ,m (µ ) the distribution of the random variable d µ,m (X ), where X is some random variable from the distribution µ .

An important example consists of approximating the DTM-signature associated to some mm-space (X , δ, µ) with an estimator built from a N -sample from µ. In principle, we would like to approximate d µ,m (µ) with the measure d μN ,m (μ N ). But unfortunately, the distribution of the test statistic (see Section 2) based on the measure d μN ,m (μ N ) is difficult to approximate by bootstrapping or subsampling methods. This is why the methods proposed in this paper rely on a test statistic based on the measure d μN ,m (μ n ) for some n smaller than N . Indeed, choosing a n smaller than N helps introduce more randomness in the subsampling distribution, allowing a better approximation of the distribution of the test statistic under the hypothesis of isomorphism. We propose to compare two DTM-signatures or empirical DTM-signatures by means of the L 1 -Wasserstein distance W 1 , which is defined in the following way; see [START_REF] Villani | Topics in Optimal Transportation[END_REF]. Definition 1.5 (Wasserstein distance). The L 1 -Wasserstein distance between two Borel probability measures µ and ν over the same metric space (X , δ) is defined as:

Note that it corresponds to the discrete distribution

W 1 (µ, ν) = inf π∈Π(µ,ν) X ×X δ(x, y)dπ(x, y),
where Π(µ, ν) stands for the set of transport plans between µ and ν, that is the set of Borel probability measures π on X × Y satisfying π(A × Y) = µ(A) and π(X × B) = ν(B) for all Borel sets A in X and B in Y.

For two probability measures µ and ν over R, the L 1 -Wasserstein distance can be rewritten as the L 1 -norm between the cumulative distribution functions of the measures, F µ : t → µ((-∞, t]) and F ν , or equivalently, as the L 1 -norm between the quantile functions, F -1 µ : s → inf{x ∈ R | F (x) ≥ s} and F -1 ν ; see for instance [8, Theorem 2.9 and Theorem 2.10] and the references therein. Thus, for empirical measures on R, its computation is easy.

Its complexity is the same as the complexity of a sort. Then, the computation of the statistic and the subsampling distribution, see Section 2, will also be easy.

As mentioned above, the strategy we use to build the test is subsampling, which is close to bootstrap. Such methods were first introduced by Efron [START_REF] Efron | Bootstrap Methods: Another Look at the Jackknife[END_REF] in 1979, mainly to derive confidence intervals, but were often used since then even in the domain of topological data analysis for the function distance to a measure [START_REF] Chazal | Robust Topological Inference: Distance To a Measure and Kernel Distance[END_REF] ; see [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes Springer Series in Statistics[END_REF] for a main reference on asymptotic bootstrap and [START_REF] Arlot | Rééchantillonnage et Sélection de Modèles PhD thesis[END_REF] for non-asymptotic bootstrap. But as aforementioned, the choice of n = N is unsuccessful and bootstrap fails experimentally and theoretically at least for our choice of statistic. Just as Politis and Romano in [START_REF] Politis | Large sample confidence regions based on subsamples under minimal assumptions[END_REF], we decide alternatively to use only a small part of the sample to approximate the distribution of the statistic, although we also use only a small part of the points to build the statistic. Thus, this method relates to subsampling.

In order to prove that the distribution of the statistic and the subsampling distribution are close, we derive an upper-bound for the Wasserstein distance between the two. Such a method was already used in the paper [START_REF] Del Barrio | A statistical analysis of a deformation model with Wasserstein barycenters : estimation procedure and goodness of fit test[END_REF]. It is then enough to prove the convergence of the distribution of the statistic to some continuous distribution to establish that our test is asymptotically of the proper level, meaning that it is valid.

The paper is organized as follows. In Section 2, we construct the statistical test and provide the main results of the paper. In there, we state assumptions under which the test is proven to be asymptotically of the correct level. As well, we derive some non-asymptotic bounds for the expectation of the L 1 -Wasserstein distance between the distribution of the statistic and the subsampling distribution. We also provide a lower-bound for the power of the test. This lower bound depends on some discriminative quantity, a pseudo-distance between mm-spaces, which is studied in Section 3 in different contexts. In this section, the pseudo-distance is proven to be bounded above by the Gromov-Wasserstein and by L 1 -Wasserstein distances. Thus, the statistical test is stable under Wasserstein noise. In Section 4, we propose an algorithm to implement the test. Moreover, some numerical experiments illustrate the fact that our method works. We give an example for which our method even performs better than some other method. Finally, in Section 5 we expose three ideas of imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: [START_REF] Arlot | Rééchantillonnage et Sélection de Modèles PhD thesis[END_REF] isomorphism testing methods linked to our test, and show that one does not work at all whereas the other two could lead to major improvements.

Main results

Let (X , δ, µ) and (Y, γ, ν) be two mm-spaces.

In this section, we build statistical tests of the null hypothesis H 0 "The mm-spaces (X , δ, µ) and (Y, γ, ν) are isomorphic", against its alternative: H 1 "The mm-spaces (X , δ, µ) and (Y, γ, ν) are not isomorphic".

The statistical tests we propose are based on the observation of two samples, an N -sample from µ and an N -sample from ν. To simplify notation, we assume that N = N , but the methods proposed also work when N is different from N . More importantly, we have to keep the same n in both cases, as defined below.

Given an N -sample X 1 , X 2 ,. . . X N from the measure µ, we denote μN = 1 N N i=1 δ Xi and μn = 1 n n i=1 δ Xi for some n ≤ N . As well, we define νN and νn from an N -sample from ν. (Xi ) , and that we compare signatures with W 1 , the L 1 -Wasserstein distance.

We recall that d μN ,m (μ n ) is the discrete distribution 1 n n i=1 δ d μN ,m
The test statistic is then defined as

T N,n,m (µ, ν) = √ nW 1 (d μN ,m (μ n ), d νN ,m (ν n )) ,
and its distribution is denoted by L N,n,m (µ, ν).

Note that for two isomorphic mm-spaces (X , δ, µ) and (Y, γ, ν), the following distributions L N,n,m (µ, µ), L N,n,m (ν, ν), and

1 2 L N,n,m (µ, µ)+ 1 2 L N,n,m (ν, ν) are equal. The notation 1 2 L 1 + 1 2 L 2 stands
for the distribution of a random variable that is generated according to L 1 with probability 1 2 and according to L 2 with probability 1 2 . The three aforementioned distributions correspond to the distribution of the test statistic T N,n,m (µ, ν); see Lemma C.1 in the Appendix.

For some α ∈ (0, 1), we denote by q The test we deal with in this paper is then The null hypothesis H 0 is rejected if φ N,n,m = 1, that is if the L 1 -Wasserstein distance between the two empirical signatures d μN ,m (μ n ) and d νN ,m (ν n ) is too high.

1 -α = inf{x ∈ R | F (x) ≥ 1 -α}, the 1 -α-quantile of a distribution with cumulative distribution function F . The 1 -α-quantile q 1 -α,N ,n,m of 1 2 L N,n,m (µ, µ) + 1 2 L N,n,m (ν, ν) will be approximated by the 1-α-quantile q1-α,N,n,m of 1 2 L * N,n,m (μ N , μN )+ 1 2 L * N,n,m (ν N , νN ). Here L * N,n,m (μ N , μN ) stands for the distribution of √ nW 1 (d μN ,m (µ * n ), d μN ,m (µ * n ))
φ N,n,m = 1 T N,n,m (µ,ν)≥q
Note that it is equivalent to compute a p-value pN,n,m from the subsampling distribution and the test statistic:

pN,n,m = 1 -F * (T N,n,m (µ, ν)), with F * (t) = P(T ≤ t) for T a random variable from the distribution 1 2 L * N,n,m (μ N , μN ) + 1 2 L * N,n,m (ν N , νN ).
The statistical test consists in rejecting the hypothesis H 0 if the p-value is not larger than α, that is

φ N,n,m = 1 pN,n,m ≤α .

A test of asymptotic level α

In this section, we consider two isomorphic mm-spaces (X , δ, µ) and (Y, γ, ν) (we may write (µ, ν) ∼ H 0 ). In order to assert the validity of the test φ N,n,m , the probability P (µ,ν)∼H0 (φ N,n,m = 1) of rejecting H 0 must be bounded above by α. In this section, under mild assumptions, we prove that the test φ N,n,m is of asymptotic level α, that is such that lim sup

N →∞ P (µ,ν)∼H0 (φ N,n,m = 1) ≤ α.
We will prove (Lemma 2.1 and Lemma 2.2) that the test is of asymptotic level α when the distribution L N,n,m (µ, µ) converges weakly to some atomless distribution L, and when its approximation L * N,n,m (μ N , μN ) from the sample satisfies that W 1 (L * N,n,m (μ N , μN ), L) converges in probability to 0.

Let G µ,m and G µ,m be two independent Gaussian processes with covariance kernel κ(s, t) = F dµ,m (µ) (s) 1 -F dµ,m (µ) (t) for s ≤ t, with F dµ,m (µ) the cumulative distribution function of d µ,m (µ). The limit distribution L is actually given by the distribution of G µ,m -G µ,m 1 , the integral on R of the absolute value of the difference between the two Gaussian processes. When the distributions µ and ν are compactly supported, these convergences occur under assumptions outlined in the following theorem. Theorem 2.1. Let (X , δ, µ) and (Y, γ, ν) be two mm-spaces, with µ and ν compactly supported. Let n be such that n N = o(1) and assume that when N goes to infinity,

√ nE[ d µ,m - d μN ,m ∞,X ] goes to 0. Then, if L( G µ,m -G µ,m 1 ) is atomless, the statistical test φ N,n,m = 1 √ nW1(d μN ,m (μn ),d νN ,m (νn ))≥q 1 -α,N ,n,m is of asymptotic level α.
The first assumption of Theorem 2.1 can be readily checked in some specific case. Among the distributions supported on compact subsets of R d , Theorem 2.2 deals with distributions that are regular in the following sense. We say that a measure µ is (a, b)-standard with positive parameters a and b, if for any positive radius r and any point x of the support of µ, we have that µ(B(x, r)) ≥ min{1 , ar b }, with B(x, r) = {y ∈ X | δ(x, y) < r}. The assumption of (a, b)-standardness has been widely used in the context of set estimation and Topological Data Analysis [START_REF] Chazal | Rates Of Convergence For Robust Geometric Inference[END_REF][START_REF] Cuevas | Set estimation: another bridge between statistics and geometry[END_REF][START_REF] Cuevas | On boundary estimation[END_REF][START_REF] Chazal | Convergence rates for persistence diagram estimation in topological data analysis[END_REF][START_REF] Chazal | Subsampling methods for persistent homology[END_REF][START_REF] Fasy | imsart-ejs ver[END_REF] Uniform measures on regular compact submanifolds are also standard. In [START_REF] Niyogi | Finding the Homology of Submanifolds with High Confidence from Random Samples[END_REF] (Lemma 5.3), the authors give a bound for a depending on the reach of the submanifold. More generally, distributions supported on regular open subsets of R d or manifolds, with density bounded from below by some positive constant, are (a, b)-standard distributions.

For compactly-supported distributions on R d and among them, for (a, b)-standard distributions, assumptions of Theorem 2.1 are satisfied as soon as n remains small enough with respect to N , as follows.

Theorem 2.2. Let µ and ν be two Borel probability measures supported on compact subsets of R d . We set N = cn ρ with some c > 0 and ρ > 1.

The statistical test

φ N,n,m = 1 √ nW1(d μN ,m (μn ),d νN ,m (νn ))≥q 1 -α,N ,n,m is of asymptotic level α • in the general case, if ρ > max{d,2} 2 , • in the (a, b)-standard case, if ρ > 1,
with the additional assumption that L( G µ,m -G µ,m 1 ) is atomless.

Morally, checking the assumption "L( G µ,m -G µ,m 1 ) is atomless" boils down to verify the following assumption:

A m : "d µ,m (µ) is not a Dirac mass".
The reason of this assertion is the following. The process (G µ,m (t) -G µ,m (t)) t∈R is a Gaussian process with covariance kernel given by 2F dµ,m (µ) (s) 1 -F dµ,m (µ) (t) for s ≤ t. Set I, the smallest interval containing the support of the measure d µ,m (µ). Note that for every t / [START_REF] Johnson | An Explicit Formula for the C.D.F. of the L 1 Norm of the Brownian Bridge The[END_REF] derived an expression for the cumulative distribution function of L( B 1 ) that depends on the Airy function and is continuous, and Rice [START_REF] Rice | The Integral of the Absolute Value of the Pinned Wiener Process-Calculation of Its Probability Density by Numerical Integration The[END_REF] derived an expression for its density.

∈ I, G µ,m (t) -G µ,m (t) = 0 since then its variance 2F dµ,m (µ) (t) 1 -F dµ,m (µ) (t) is equal to 0. As a consequence, G µ,m -G µ,m 1 is the integral of |G µ,m (t) -G µ,m (t)| over the interval I. This interval is reduced to a single point when d µ,m (µ) is a Dirac mass. In this case, G µ,m -G µ,m 1 is constant equal to 0.
The measures µ for which assumption A m is satisfied for no m ∈ [0, 1] are such that d µ,m (x) = d µ,m (y) for every x, y ∈ Supp(µ) and m ∈ [0, 1], that is:

∀x, y ∈ Supp(µ), ∀r ≥ 0 , µ(B(x, r)) = µ(B(y, r)).
(2.1)

For instance, discrete distributions for which A m is never satisfied are exactly the distributions that are uniform on a finite set of points (Equation (2.1) with r = 0) and that satisfy that: "For every x, y ∈ Supp(µ), for every d > 0, the number of points in Supp(µ) at distance d to y is the same as the number of points in Supp(µ) at distance d to x". Another example of measure µ such that A m is never satisfied is given by any uniform distribution on a sphere in R d . In this case, (2.1) is trivially satisfied.

Characterizing all distributions for which A m is not satisfied for some fixed m ∈ [0, 1] is not simple. The examples are more abundant than the above-mentioned ones. For instance, µ = 0.2δ 0 + 0.2δ 1 + 0.3δ 5 + 0.3δ 7 does not satisfy A 0.4 . For such examples, the isomorphism test on two samples from µ with parameter m will not work. Nonetheless, it is possible to circumvent this issue by modifying the datasets, as follows.

Set D, a continuous and compactly-supported isotropic distribution on R d ; for instance, the restriction of the normal distribution N (0, 1) to a ball centered at 0. Then, the convolution of two isomorphic distributions µ and ν (in R d ) with D will be isomorphic and will satisfy assumption A m for every m ∈ (0, 1). For practice, this strategy consists in replacing the sample (X i ) i∈[ [1,N ]] from µ with the sample (X i + Z i ) i∈[ [1,N ]] for Z i ∼ D independent random variables, independent from (X i ) i∈[ [1,N ]] . For the testing purpose, the same procedure should be applied to the sample from ν.

As aforementioned, the proof of Theorem 2.1 consists in showing that the distribution of the test statistic

1 2 L N,n,m (µ, µ) + 1 2 L N,n,m (ν, ν)
under the hypothesis H 0 converges weakly to the fixed distribution

L = 1 2 L( G µ,m -G µ,m 1 ) + 1 2 L( G ν,m -G ν,m 1 )
when n and N go to ∞. But also, that the L 1 -Wasserstein metric between the subsampling distribution 1 2

L * N,n,m (μ N , μN ) + 1 2 L * N,n,m (ν N , νN )
and L converges to 0 in probability. Note that it is sufficient to prove these convergences for L N,n,m (µ, µ) and L * N,n,m (μ N , μN ). Indeed, the L 1 -Wasserstein distance W 1 is a metric for weak convergence and satisfies that for any distributions

L 1 , L 1 , L 2 and L 2 , W 1 ( 1 2 L 1 + 1 2 L 1 , 1 2 L 2 + 1 2 L 2 ) ≤ 1 2 W 1 (L 1 , L 1 ) + 1 2 W 1 (L 2 , L 2 )
. This is a straightforward consequence of the definition of the L 1 -Wasserstein distance with transport plans. Then, Theorem 2.1 follows from the following two lemmas.

L N,n,m (µ, µ) L G µ,m -G µ,m 1 , (2.2)
and

W 1 L * N,n,m (μ N , μN ), L G µ,m -G µ,m 1 → 0 in probability, (2.3)
when N goes to infinity.

Proof. Proof in the Appendix, in Section C.3.

Convergence of the distribution of the statistic and convergence of its approximation via subsampling to a fixed distribution is not sufficient to prove that the test has the correct level. Continuity of the limit distribution L is also required. Proof. This proposition is based on rates of convergence for the Wasserstein distance between a measure µ on R d and its empirical version μN ; see [START_REF] Fournier | On The Rate Of Convergence In Wasserstein Distance Of The Empirical Measure[END_REF] for general dimensions and [START_REF] Bobkov | One-Dimensional Empirical Measures, Order Statistics And Kantorovich Transport Distances. the Memoirs of the AMS -American Mathematical Society[END_REF] Moreover, a bound for the expectation of

Lemma 2.2. If the two convergences in Lemma 2.1 occur, and if the

1 -α-quantile q 1 -α of the distribution 1 2 L( G µ,m -G µ,m 1 ) + 1 2 L( G ν,m -G ν,m 1 )
W 1 L N,n,m (µ, µ), L * N,n,m (μ N , μN ) is of order N 1 2ρ -1 2 up to a logarithmic term.
Proof. This proposition is based on rates of convergence for the infinity norm between the distance to a measure and its empirical version; see [START_REF] Chazal | Rates Of Convergence For Robust Geometric Inference[END_REF]. Proof in the Appendix, in Section C.5.

Note that we can achieve a rate close to the parametric rate for standard measures, whereas for general measures, the rate gets worse when the dimension increases. In any case, we need ρ to be as large as possible for the subsampling distribution to be a good enough approximation of the distribution of the statistic, that is, to have a type I error close enough to α, keeping in mind that n should go to ∞ with N .

The power of the test

The power of the test φ N,n,m = 1 √ nW1(d μN ,m (μn ),d νN ,m (νn ))≥q 1-α,N,n,m is defined for two mm-spaces (X , δ, µ) and (Y, γ, ν) by 1 -P (µ,ν) (φ N,n,m = 0) , where P (µ,ν) (φ N,n,m = 0) stands for the probability that φ N,n,m = 0 when the test is built from samples from two general mm-spaces (X , δ, µ) and (Y, γ, ν).

If the spaces are not isomorphic, we want the test to reject H 0 with high probability. It means that we want the power to be as large as possible. Here, we give a lower bound for the power, or more precisely an upper bound for P (µ,ν) (φ N,n,m = 0), the type II error. Theorem 2.3. Let µ and ν be two Borel measures supported on X and Y, two compact subsets of R d . We assume that the mm-spaces (X , δ, µ) and (Y, γ, ν) are non-isomorphic and that the DTM-signature is discriminative for some m in (0, 1], meaning that the pseudometric

W 1 (d µ,m (µ), d ν,m (ν)) is positive. We choose N = n ρ with ρ > 1.
Then for all positive , there exists N 0 depending on µ and ν such that for all N ≥ N 0 , the type II error

P (µ,ν) √ nW 1 (d μN ,m (μ n ), d νN ,m (ν n )) < q1-α,N,n,m
is bounded above by

4 exp - W 2 1 (d µ,m (µ), d ν,m (ν)) (2 + ) max D 2 µ,m , D 2 ν,m N 1 ρ
, with D µ,m the diameter of the support of the measure d µ,m (µ). Proof. Proof in the Appendix, in Section C.6.

In order to have a high power, that is to reject H 0 more often when the mm-spaces are not isomorphic, we need n to be big enough, that is ρ small enough. Recall that n has to be small enough for the law of the statistic and its subsampling version to be close. This means that some compromise must be made. Moreover, the choice of m for the test should depend on the geometry of the mm-spaces. The tuning of these parameters from the data is still an open question.

Moreover, note that the power of the test is strongly related to

W1(dµ,m (µ),dν,m (ν)) max{D 2 µ,m ,D 2 ν,m }
. The test is powerful when the pseudo-metric is high with respect to the diameters of the signatures supports and does not discriminate between measures when it is low. In the following section, we derive some upper-bounds and lower-bounds for the pseudo-metric

W 1 (d µ,m (µ), d ν,m (ν)),
under some geometric assumptions.

Stability and discriminative properties of the DTM-signatures

Stability of the DTM-signatures

In this section, we prove stability results for the DTM-signature. These results all rely on the stability of the distance-to-a-measure function itself.

Proposition 3.1 (Stability, in [START_REF] Chazal | Geometric Inference for Probability Measures[END_REF] for R d , in [START_REF] Buchet | Topological Inference From Measures[END_REF] for metric spaces). For two mm-spaces (X , δ, µ) and (Y, δ, ν) embedded into the same metric space, we have that

d µ,m -d ν,m ∞,X ∪Y ≤ 1 m W 1 (µ, ν).
In [START_REF] Mémoli | Gromov-Wasserstein Distances and the Metric Approach to Object Matching[END_REF], Mémoli proposes a metric on the quotient space of mm-spaces by the relation of isomorphism, the Gromov-Wasserstein distance.

Definition 3.1 (Gromov-Wasserstein distance). The Gromov-Wasserstein distance between two mm-spaces (X , δ, µ) and (Y, γ, ν) denoted GW (X , Y) is defined by the expression

inf π∈Π(µ,ν) 1 2 X ×Y X ×Y Γ X ,Y (x, y, x , y ) π(dx × dy)π(dx × dy ), with Γ X ,Y (x, y, x , y ) = |δ(x, x ) -γ(y, y )|.
Here Π(µ, ν) stands for the set of transport plans between µ and ν, that is the set of Borel probability measures

π on X × Y satisfying π(A × Y) = µ(A) and π(X × B) = ν(B) for all Borel sets A in X and B in Y.
The DTM-signature turns out to be stable with respect to this Gromov-Wasserstein distance.

Proposition 3.2. We have that:

W 1 (d µ,m (µ), d ν,m (ν)) ≤ 1 m GW (X , Y).
Proof. Proof in the Appendix, in Section B. The proof is relatively similar to the ones given by Mémoli in [START_REF] Mémoli | Gromov-Wasserstein Distances and the Metric Approach to Object Matching[END_REF] for other signatures.

It follows directly that two isomorphic mm-spaces have the same DTM-signature. Whenever the two mm-spaces are embedded into the same metric space, we also get stability with respect to the L 1 -Wasserstein distance.

W 1 (µ, ν) + min d µ,m -d ν,m ∞,Supp(µ) , d µ,m -d ν,m ∞,Supp(ν) ,
and more generally by

1 + 1 m W 1 (µ, ν).
Proof. First notice that:

W 1 (d µ,m (µ), d ν,m (µ)) ≤ X |d µ,m (x) -d ν,m (x)| dµ(x) ≤ d µ,m -d ν,m ∞,Supp(µ) .
Then, for all π in Π(µ, ν):

W 1 (d ν,m (µ), d ν,m (ν)) ≤ X ×Y |d ν,m (x) -d ν,m (y)| dπ(x, y).
Thus, since d ν,m is 1-Lipschitz:

W 1 (d ν,m (µ), d ν,m (ν)) ≤ W 1 (µ, ν).
Then, the result follows from Proposition 3.1.

According to [START_REF] Bobkov | One-Dimensional Empirical Measures, Order Statistics And Kantorovich Transport Distances. the Memoirs of the AMS -American Mathematical Society[END_REF], a measure µ and its empirical version μN are close in terms of the Wasserstein metric W 1 . As a consequence, Proposition 3.3 entails that the signature d µ,m (µ) and the empirical signature d μN ,m (μ N ) are close when N gets large. This property is essential for the purpose of testing. The signature δ µ,m (µ), built from the pseudo-metric δ µ,m , does not satisfy this stability property. Indeed, for m < 1 2 -, the measures µ = (m+ )δ 0 +(1-m-)δ 1 and ν = (m -)δ 0 + (1 -m + )δ 1 are very close in terms of W 1 , nonetheless, their signatures δ µ,m (µ) = δ 0 and δ ν,m (ν) = (1 -m + )δ 0 + (m -)δ 1 are very different. This explains why, in this paper, we consider the DTM d µ,m and not the pseudo-metric δ µ,m .

Discriminative properties of the DTM-signatures

The DTM-signature is stable but unfortunately does not always discriminate between mmspaces. Indeed, in the following counter-example from [START_REF] Mémoli | Gromov-Wasserstein Distances and the Metric Approach to Object Matching[END_REF] (example 5.6), there are two non-isomorphic mm-spaces sharing the same signatures for all values of m. Example 3.1. We consider two graphs made of 9 vertices each, clustered in three groups of 3 vertices, such that each vertex is at distance 1 exactly from each vertex of its group and at distance 2 from any other vertex. We assign a mass to each vertex; the distribution is the following, for the first graph (Figure 1): The mm-spaces ensuing are not isomorphic since any one-to-one and onto measure-preserving map would send at least one pair of vertices at distance 1 from each other to a pair of vertices at distance 2 from each other, and thus it would not be an isometry. Moreover, note that the DTM-signatures associated to the graphs are equal since the total mass of each cluster is exactly equal to 1 3 .

µ = 23
Figure 1. µ Figure 2. ν
Nevertheless, the signature can be discriminative in some cases. In the following, we give lower bounds for the L 1 -Wasserstein distance between two signatures under different alternatives.

We will prove in Proposition 3.4 that this pseudo-distance is proportional to |1 -λ| when we consider a metric space (X , δ, µ) and its dilatation (X , λδ, µ) with a factor λ > 0. More generally, it is possible to discriminate between two uniform distributions that are supported on compact subsets of R d , with different Lebesgue volumes Leb d (O) and Leb d (O ).

In Proposition 3.5 we provide a lower bound for the distance between such signatures, that is proportional to |Leb d (O)

1 d -Leb d (O ) 1 d |.
Note that this bound is kind of optimal, since we recover the factor |1 -λ| of Proposition 3.4 when O is the image of O with a dilatation of parameter λ.

Moreover, two uniform distributions on compact sets with the same Lebesgue volume might also have different signatures, as enhanced by Example 3.3. Indeed, according to Proposition 3.6, whenever the inner offsets O = {x ∈ O | inf y∈∂O x -y 2 ≥ } and O have different Lebesgue volume for some > 0, the signatures associated with some parameter m, depending on , will be different. Consequently, it is possible to discriminate between a "thin" subset of R d or a set with not regular boundary and a "fat" set or a set with a regular boundary (for instance, a set with a large reach, as defined in Section 3.2.3) such as a ball.

The signatures are also sensitive to the density of distributions. A distribution with density bounded above by some constant C (a uniform distribution for instance) can be discriminated from distributions which density is larger than C on some sets that are large enough. Lower bounds for the distance between such signatures are derived in Proposition 3.7, Proposition 3. positive ν-measure. One might use such a strategy to prove that two signatures are different in many other situations than the following situations handled in this paper.

When the distances are multiplied by some positive real number λ

Let λ be some positive real number. The DTM-signature discriminates between two mmspaces isomorphic up to a dilatation of parameter λ, for λ = 1. Proposition 3.4. Let (X , δ, µ) and (Y, γ, ν) = (X , λδ, µ) be two mm-spaces. We have

W 1 (d µ,m (µ), d ν,m (ν)) = |1 -λ| E µ [d µ,m (X )],
for X a random variable of law µ.

Proof. First notice that F -1 dν,m (ν) = λF -1 dµ,m (µ) . Then, W 1 (d µ,m (µ), d ν,m (ν)) = 1 0 F -1 dµ,m (µ) (s) -F -1 dν,m (ν) (s) ds = |1 -λ| 1 0 F -1 dµ,m (µ) (s) ds = |1 -λ| E µ [d µ,m (X )] .

The case of uniform measures on non-empty bounded open subsets of R d

The DTM-signature discriminates between two uniform measures over two non-empty bounded open subsets of R d with different Lebesgue volume, provided that m is small enough.

(B) = Leb d (B∩O)
Leb d (O) for all Borel set B. Proof. Proof in the Appendix, in Section A.2.

If Leb d (O) ≤ Leb d (O ), then, a lower bound for W 1 (d µ O ,m (µ O ), d µ O ,m (µ O )) is given by µ O O (m,O) d d + 1 m ω d 1 d Leb d (O ) 1 d -Leb d (O) 1 d . Here, O = {x ∈ O | inf y∈∂O x -y 2 ≥ } with ∂O the boundary of O, (m, O) = mLeb d (O)
Proposition 3.5 states that two uniform distributions on compact sets with different Lebesgue volume have different signatures. Nonetheless, when these Lebesgue volumes are equal, it might also be possible to detect difference between the measures by considering the volumes of the inner offsets.

Proposition 3.6. Set O, a subset of R d . Then, the set of points x in R d for which d µ O ,m (x) is minimal is given by the inner offset O (m) , with (m) = mLeb d (O) ω d 1 d . As a consequence, if O and O are two subsets of R d such that Leb d (O) = Leb d (O ) but Leb d (O (m) ) = Leb d (O (m) ), then the signatures d µ O ,m (µ O ) and d µ O ,m (µ O ) are different.
Proof. This proposition is a direct consequence of Proposition A.1 in the Appendix. This proposition can be applied to the following simple cases.

Example 3.3. The uniform distributions on the rectangle

O = [0, 1] × [0, π] and the ball O = B(0, 1) in R 2 have a different signature for every m ∈ (0, 1). Proof. The volume of O is given by Leb 2 (O ) = π(1 -) 2 for ≤ 1. The volume of O is given by Leb 2 (O ) = (1 -2 )(π -2 ) for ≤ 1 2 . For 1 > > 1 2 , Leb 2 (O ) = 0 < Leb 2 (O ). Moreover, for ∈ [0, 1 2 ), Leb 2 (O ) > Leb 2 (O ).
In this example, m = 2 . More generally, "thin" sets and "fat" sets can be discriminated:

O = [0, ] × 0, 1 in R 2 have a different signature for m such that m π ∈ [ , ]. Proof. For m ∈ π 2 2 , π 2 2 , we get that (m) = m π ∈ 2 , 2 . For such values of m, O (m) is empty but O (m) is not empty.
The signatures of two sets that have the same volume and are very close (in terms of the Hausdorff metric for instance) might be different provided that the boundary of the first set is regular whereas the boundary of the second set is not. For instance, a rectangle and a biscuit-nantais-shaped rectangle have different signatures since the inner-offsets of the biscuit-nantais-shaped rectangle have smaller Lebesgue volume than the inner-offsets of the rectangle.

The aforementioned examples deal with measures with a support of dimension d in R d .

Nonetheless, sometimes, it is also possible to prove that uniform distributions on submani-

folds of dimension d < d of R d have different signatures.
Proof. We can compute δ µ O ,l (x) = 2 sin( πl 2 ) for x ∈ Supp(µ O ) and δ µ O ,l (x) ≥ πl for x ∈ Supp(µ O ). Then, sup x∈Supp(µ O ) d µ O ,m (x) < inf x∈Supp(µ O ) d µ O ,m (x) for every m ∈ (0, 1].
For the same reason, a segment and a spiral with the same length have different signatures, whatever the value of m. This kind of example is investigated in the simulations part. In the following, we highlight the fact that signatures catch the density variation of distributions. (O) and ν a measure absolutely continuous with respect to µ O . Thanks to the Radon-Nikodym theorem, there is some

The case of two measures on the same open subset of R d where one of them is uniform

Let (O, • 2 , µ O ) and (O, • 2 , ν) be two mm-spaces with O a non-empty bounded open subset of R d , µ O = Leb d (.∩O) Leb d
µ O -measurable function f on O such that, for all Borel sets A in O, ν(A) = A f (ω)dµ O (ω).
We can consider the λ-super-level sets of the function f denoted by {f ≥ λ}. Again, we will denote by {f ≥ λ} the set of points belonging to {f ≥ λ} whose distance to ∂{f ≥ λ} is at least .

Then we get the following lower bound for the L 1 -Wasserstein distance between the two signatures: Proposition 3.7. Under these hypotheses, a lower bound for It should be noted that when ν = µ O , f is constant, equal to 1. Then, for λ > 1, the sets {f ≥ λ } are empty. As a consequence, the lower bound obtained in Proposition 3.7 is zero. Another simple example is the following.

W 1 (d µ O ,m (µ O ), d ν,m (ν)) is given by d min d Leb d (O) ∞ λ=1 1 λ d+1 d max λ ≥λ λ Leb d {f ≥ λ } m ω d Leb d (O) λ 1 d dλ, with d min = mLeb d (O)

Example 3.7. The distribution µ with density

1 π on the ball O = B(0 , 1 ) = {x ∈ R 2 |
x < 1 }, and the measure ν with density 1 2π on B(0 , 1 )\B(0 , 1 2 ) and 5 2π on B(0

, 1 2 ) have different signatures if m ≤ 5 8 . Moreover, a lower bound for W 1 (d µ,m (µ), d ν,m (ν)) is given by 2 √ m 3 1 -2 5 √ 5 2 √ 2 - √ m 2 . Proof. We have that Leb 2 (O) = π, d min = 2 3 √
m. The density of ν with respect to µ is given by f which is equal to 1 2 on B(0 , 1 )\B(0 , 1 2 ) and 5 2 on B(0 , 1 2 ). As a consequence, {f ≥ λ} is empty as soon as λ ≥ 5 2 . For λ ∈ 1,

B 0 , 1 2 -m ω d Leb d (O) λ 1 d = B 0 , 1 2 -m λ .
This set is non-empty if and only if λ ≥ 4m.

Then, λ Leb 2 (B 0 , 1 2 -m λ ) = π √ λ 2 - √ m 2 .
It is maximal at λ = 5 2 . Note that we must assume that 5 2 ≥ 4m, that is, m

≤ 5 8 . Then, W 1 (d µ,m (µ), d ν,m (ν)) ≥ 2 √ m 3 1 -2 5 √ 5 2 √ 2 - √ m 2 .
The proof of Proposition 3.7 extends to non-uniform distributions in R d , that are not necessarily supported on the same set.

When the density f is Hölder

In order to get additional results about discrimination, we need to define a quantity characterising the complexity of the set O. This is the notion of reach of an open set, defined from its medial axis. Its reach, Reach(O), is then defined as the distance between its boundary ∂O and its medial axis M(O). That is,

Reach(O) = inf{ x -y 2 | x ∈ ∂O, y ∈ M(O)}.
In the following, we assume that Reach(O) > 0 and that f is Hölder on O, with positive parameters χ ∈ (0, 1] and L > 0, that is:

∀x, y ∈ O, |f (x) -f (y)| ≤ L x -y χ 2 .
Then for m small enough, the DTM-signature is discriminative.

Proposition 3.9. Under the assumptions of Proposition 3.7, if one of the following conditions is satisfied, then the quantity

W 1 (d µ O ,m (µ O ), d ν,m (ν)) is positive: m < ω d Leb d (O) min Reach(O) d , f ∞,O -1 2L d χ ; m ∈ ω d Leb d (O) (Reach(O)) d , ( f ∞,O -2L(Reach(O)) χ ) (Reach(O)) d ω d Leb d (O) ; m ∈ ω d Leb d (O) d χ d χ (2L) -d χ , min m 0 , ω d Leb d (O) (Reach(O)) d+χ χ d 2L , with m 0 = f d χ +1 ∞,O ω d Leb d (O) d χ d χ (2L) -d χ χ d+χ χ d+χ .
Moreover, under any of these conditions, we get the following lower bound on the pseudodistance

W 1 (d µ O ,m (µ O ), d ν,m (ν)): 1 1 + d mLeb d (O) ω d 1 d ∞ λ=1 1 λ 1+ 1 d sup λ ≥λ ν {f ≥ λ + L (λ ) χ } ∩ O (λ ) dλ, with (λ ) = λ -1 d mLeb d (O) ω d 1 d .
Here, ω d stands for Leb d (B(0 , 1 )), the Lebesgue volume of the unit d-dimensional ball.

Proof. Proof in the Appendix, in Section A.3.

This proposition displays different intervals of values for m for which the DTM-signatures are discriminative. These intervals depend on the reach of O. Indeed, if m is small enough with respect to Reach(O), then the distance to the measure µ O is easier to approximate on the whole set O, and is even known on most of the set (see Proposition A.1), and thus easier to compare with the distance to the measure ν.

The Hölder hypothesis provides some continuity of the density. Then, the function distance to the measure µ O will take close values at any two points close enough. The main idea is to use the fact that the density of ν is not constant. Then, we can, for particular values of m, reveal a set of points of positive µ O -measure for which the distance to the measure ν is smaller than the minimum of the distance to the measure µ O .

Morally, this proposition consists in proving that

W 1 (d µ O ,m (µ O ), d ν,m (ν)) is positive whenever: f ∞,O > inf {λ + 2L (λ) χ | λ ≥ 1, (λ) ≤ Reach(O)} . Note that (λ) ≤ Reach(O) is equivalent to λ ≥ mLeb d (O) ω d Reach(O) d .
For each of the three intervals (a, b), the value of a or b is computed from the inequality f ∞,O > λ + 2L (λ) χ for some λ well chosen, as follow. For the first interval, we take λ = 1; for the second one, we take λ such that (λ) = Reach(O); for the last one, we take the λ that minimizes the function λ → λ + 2L (λ) χ on R + . The second value b or a is computed according to the additional constraint for the λs: λ ≥ 1 and (λ) ≤ Reach(O).

In particular, the first interval is empty when

mLeb d (O) ω d Reach(O) d > 1 and the second one is empty when mLeb d (O) ω d Reach(O) d < 1.
The last interval is empty when the function λ + 2L (λ) χ attains its minimum at a point λ that is smaller than 1 or smaller than mLeb d (O) ω d Reach(O) d . Since λ → λ + 2L (λ) χ is decreasing and then increasing, there is at least one non-empty interval if and only if

f ∞,O > inf {λ + 2L (λ) χ | λ ≥ 1, (λ) ≤ Reach(O)}.
This proposition can be applied to concrete cases, proving the existence of some mass parameters m for which the DTM-signature is discriminative. Proof. The density f of the multivariate normal distribution N (0, σ 2 I) restricted to B(0 , 1 ) is Lipschitz, as a consequence, it is possible to apply Proposition 3.9 with the parameter χ = 1. The proof is deferred to the Appendix, in Section A.3.

The previous examples provide several relevant cases where the DTM-signature turns out to be discriminative. Thus, the test of isomorphism will be powerful for some distributions.

Numerical experiments

In this section, we first describe the procedure to implement the statistical test of isomorphism. Then, we illustrate the validity of the method by providing some numerical approximations of the type-I error and the power of the test for various examples. We also compare our test to a more basic statistical test of isomorphism.

The algorithm

The procedure for the statistical test is as follows.

In the code, if Z = {Z 1 , Z 2 , . . . , Z n }, then we use the notation 1 Z for the measure # Compute T the test statistic Let σ be a random permutation of {1, 2, . . . , N } ; Let σ be a random permutation of {1, 2, . . . , N } independent of σ ;

1 n n i=1 δ Zi . Algorithm 1. Test Procedure Input : X = {X 1 , X 2 , . . . , X N } N -sample from µ; Y = {Y 1 , Y 2 , . . . , Y N } N -
Define X n = {X σ(1) , X σ(2) , . . . , X σ(n) } ; Define Y n = {Y σ (1) , Y σ (2) , . . . , Y σ (n) } ; Define the test statistic T = √ nW 1 (d 1 X ,m (1 Xn ), d 1 Y ,m (1 Yn )) ; # Compute W sub , a N sub -sample from the subsampling law Compute dtmX = {d 1 X ,m (X 1 ), d 1 X ,m (X 2 ), . . . , d 1 X ,m (X N )} ; Compute dtmY = {d 1 Y ,m (Y 1 ), d 1 Y ,m (Y 2 ), . . . , d 1 Y ,m (Y N )} ;
Let W sub be empty ; f o r j in 1 . . N sub /2 : Let dtmX 1 and dtmX 2 be two independent n-samples from dtmX with replacement ; Let dtmY 1 and dtmY 2 be two independent n-samples from dtmY with replacement ; Add √ nW 1 (1 dtmX1 , 1 dtmX2 ) and

√ nW 1 (1 dtmY1 , 1 dtmY2 ) to W sub ;
# Compute pval, the p-value of the statistical test Let pval be equal to the mean number of elements in W sub bigger than T ;

Output :

The hypothesis retained is

H 1 if pval ≤ α, H 0 if not.
Recall that the L 1 -Wasserstein distance W 1 is simply equal to the L 1 -norm of the difference between the cumulative distribution functions, which is easy to implement in the discrete case. As explained in the Introduction, in order to compute the distance to an empirical measure on a N -sample at a point x, it is sufficient to search for its k = mN -nearest neighbours in the sample, where m ∈ [0, 1] is the mass parameter. The distance to the empirical measure can also be implemented by the R function dtm with tuning parameter r = 1, from the package TDA [START_REF] Fasy | Introduction to the R package TDA[END_REF].

An example in R 2

In this subsection, we will compare the statistical test of this paper (DTM) with the statistical test (KS) which consists in applying a Kolmogorov-Smirnov two-sample test to the

N 2 -sample {δ(X 1 , X 2 ), δ(X 3 , X 4 ), . . . , δ(X N -1 , X N )} and the N 2 -sample {γ(Y 1 , Y 2 ), γ(Y 3 , Y 4 ), . . . , γ(Y N -1 , Y N )}
given an N -sample X = {X 1 , X 2 , . . . , X N } from an mm-space (X , δ, µ) and an N -sample Y = {Y 1 , Y 2 , . . . , Y N } from an mm-space (Y, γ, ν).

We apply our isomorphism test to measures supported on spirals in R 2 . For some shape parameter v ∈ R + , the measure µ v is the distribution of the random vector (R sin(vR) + 0.03S, R cos(vR) + 0.03S ), with R, S and S independent random variables, S and S from imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019 the standard normal distribution N (0, 1) and R uniform on (0, 1). In the following experiments, we choose µ = µ 10 and ν = µ v for v ∈ {15, 20, 30, 40, 100}. This leads to the empirical measures μN and νN . In Figure 4, we plot the cumulative distribution function of the measure d μN ,m (μ N ), that is, the function F defined for all t in R by the proportion of the X i in X satisfying d μN ,m (X i ) ≤ t. It approximates the true cumulative distribution function associated to the DTM-signature d µ,m (µ). As well, we plot the cumulative distribution function of the measure d νN ,m (ν N ).

The signatures are different. Thus, for the choice of parameter m = 0.05, the DTMsignature discriminates well between the measures µ = µ 10 and ν = µ 20 . The signature with parameter m = 0.05 provides a local information about the measure µ v . The spiral with v = 10 is less coiled that the spiral with v = 20. It means that at a point of the spiral, catching 5 percent of points requires a larger radius for v = 20 than for v = 10. As a consequence, d µ10 ,0 .05 (µ 10 ) takes smaller values than d µ20 ,0 .05 (µ 20 ), as illustrated by Figure 4. Note that a m close to 1 would not be relevant in such an example. Indeed, d µ,1 (x) roughly corresponds to the distance of point x to the expectation of the measure µ. Since the spirals have the same diameter, the signatures would be very close for m close to 1.

Note that a small m would not be appropriated to discriminate between a spiral and its uncoiled version (a noisy sample generated around a segment). Indeed, the local behavior of the measure would be the same. In this case, a large choice of m would be more appropriate.

In Figure 5, for m = 0.05 and n = 20, we first generate 1000 independent realisations of the random variable

√ nW 1 (d μN ,m (μ n ), d μ N ,m (μ n ))
, where μN and μ N are independent empirical measures from µ 10 , N = 2000, and μn and μ n are the empirical measures associated to the n first points of the samples. We plot the empirical cumulative distribution function associated to this 1000-sample.

As well, from two fixed N -samples from µ 10 , leading to two empirical distributions μN and μ N , we generate a set of N sub = 1000 random variables

√ nW 1 (d μN ,m (µ * n ), d μ N ,m (µ * n )
), as explained in the Algorithm in Section 4.1, and we plot its cumulative distribution function. Note that the two cumulative distribution functions are close. This means that the 1 -α-quantile of the distribution of the test statistic is well approximated by the 1 -αquantile of the subsampling distribution. In order to approximate the type-I error and the power, we repeat the procedure of test DTM described in Section 4.1 1000 times independently. At each step, we sample N = 2000 points from the measures µ = µ 10 and ν = µ v to approximate the power, or twice µ v to imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019 approximate for the type-I error. We select the parameters α = 0.05, m = 0.05, n = 20, and repeat subsampling N sub = 1000 times. Then, we retain either H 0 or H 1 . The type-I error or power approximation is simply equal to the mean number of times the hypothesis H 0 was rejected among the 1000 independent experiments. We also approximate the power for the method KS after repeating this test procedure 1000 times independently. Note that by construction, the test KS is truly of level α = 0.05. Figure 8 contains the numerical values we obtained using the R software. It turns out that our isomorphism test DTM is of level close to α = 0.05 and is powerful. For parameters v ≥ 20, our test is even more discriminative than the test KS.

An example in R 28×28

In this subsection, we use our statistical test of isomorphism to compare the distribution of the digits "2" and the distribution of the digits "5" from the MNIST handwritten digits database. Each digit is represented by a picture of 28 × 28 pixels with grey levels, meaning that each digit X = (x 1 , x 2 , . . . , x 28×28 ) can be seen as an element of R 28×28 , where x i is equal to the grey level of the i-th pixel. We equip R 28×28 with the Euclidean metric. The interest of the statistical test here is not to test whether a "2" and a "5" are isometric, but whether the distribution of the "2"s and the distribution of the "5"s (which are distributions on compact subsets of R 28×28 ) are equal up to an isomorphism. These distributions are clearly not equal, since their supports are different, but it is not clear that there is no rigid transformation between the set of "2" and the set of "5" preserving the measures, as for instance a simple permutation of the pixels.

The statistical test is based on the observation of N = 5958 "2" and N = 5421 "5". In order to prove the validity of the test, we repeat 1000 times the experiment consisting in randomly splitting the set of "2" in two parts and applying the statistical test to these two samples. The type-I error approximation is equal to the mean number of times the hypothesis H 0 was rejected. We do the same with the set of "5". And we repeat these experiments for different values of n ∈ {10, 20, 30, 50, 75, 100, 200} and for a fixed m = 0.1, we repeat subsampling N sub = 1000 times.

These results are encouraging since they prove that the test does not discriminate between two samples of "2" (respectively, between two samples of "5") with probability 0.95. Thus, the type-I error is of order 0.05. We choose the parameter n = 100 to make the test between the sample of "2" and the sample of "5". We get a p-value equal to 0. It means that we reject H 0 at any level α. So we can conclude that the distribution of the "2" and the distribution of the "5" in the MNIST database are not isomorphic.

Unlike the spirals, there is a priori no intuition about how to choose a parameter m that discriminates between the distribution of the "2" and the distribution of the "5". In this case, one may choose some intermediate parameter m (for instance m = 0.1), which does not contains too local or global information about µ. A better idea is to refer to Theorem 2.3 and the remarks below. One may plot

W1(d μN ,m (μ N ),d νN ,m (ν N )) max D 2 μN ,m ,D 2 νN ,m
as a function of m. A suitable choice of m to discriminate between the distributions would be any maximum m of this function.

A discussion of other methods

The Kolmogorov-Smirnov test applied to empirical DTM-signatures

In order to test isomorphism between two mm-spaces (X , δ, µ) and (Y, γ, ν) from two Nsamples {X 1 , X 2 , . . . , X We repeated the experiment 1000 times independently, and the proportion of rejected hypotheses H 0 was equal to 0.926, instead of 0.05 for a statistical test of level 0.05. Thus, applying a Kolmogorov-Smirnov test to empirical DTM-signatures is to be avoided.

A different value of n for the test statistic and for the subsampling distribution

In [START_REF] Politis | Large sample confidence regions based on subsamples under minimal assumptions[END_REF], Politis and Romano propose subsampling methods consisting in approximating the distribution of a statistic with values of the statistic built from smaller subsets of the data. For our statistical test, since the distribution of the statistic and the subsampling distribution converge weakly to the same distribution under some assumptions, see Lemma 2.1, we can imagine fixing some parameters n and l smaller than N , choosing as a test statistic

T = √ lW 1 (d μN ,m (μ l ), d νN ,m (ν l ))
and approximating its distribution with the subsampling distribution

1 2 L * N,n,m (μ N , μN ) + 1 2 L * N,n,m (ν N , νN ).
If we do so, consider (a, b)-standard measures supported on compact subsets of R d and choose N = n ρ and l = n β with 1 < β < ρ, then the test is asymptotically of level α, provided that the cumulative distribution function of G µ,m -G µ,m 1 is continuous.

Indeed, the hypothesis of Lemma 2.1,

√ l E[ d µ,m -d μN ,m ∞,X ]
→ 0 , will be satisfied then.

Moreover, the proof of Theorem 2.3, which provides an upper-bound for the type-II error, can be generalised to this case, leading to the upper-bound

4 exp - W 2 1 (d µ,m (µ), d ν,m (ν)) (2 + ) max D 2 µ,m , D 2 ν,m n β
for the type-II error of the test φ N,n,m = 1 √ lW1(d μN ,m (μ l ),d νN ,m (ν l ))≥q 1-α,N,n,m if n is big enough. Note that it is a real improvement for the power.

Nonetheless, the upper-bounds for the L 1 -Wasserstein distance between the test statistic distribution and the subsampling distribution in Proposition 2.1 and Proposition 2.2 cannot be generalised easily.

The following experiments emphasize the fact that the subsampling distribution does not necessarily well approximate the distribution of the test statistic if n and l are different. For the parameters n = 20 and l ∈ {20, 50, 200}, we have repeated 1000 times the experiment consisting of computing the p-value of our statistical test from two 2000-samples on a spiral with shape parameter v = 10, subsampling N sub = 1000 times and with mass parameter m = 0.05. We sorted these p-values and plotted the associated cumulative distribution function. In this experiment, the hypothesis H 0 is satisfied, so the p-values should be uniformly distributed. Moreover they are independent. Thus, the curve we obtained should lie close to the diagonal. This is not the case when l is too far from n.

However, we get a power equal to 1 when choosing l = 200 or l = 50 instead of l = 20, which is much better than 0.884 which was obtained in Section 4.2 from the same experiment but with l = n = 20. Such a procedure should not be used, despite the improvement of power. Indeed, we have not proved the existence of a non-asymptotic control of a distance between the distribution of the test statistic and the subsampling distribution. Moreover, the experiments emphasize that these distributions are too different to get a test of type-I error not greater than α.

The one-sample Kolmogorov-Smirnov test of uniformity applied to p-values

A major problem of the statistical test proposed in this paper is that the hypothesis retained truly depends on the arbitrary selection of the two n-samples to build the test statistic among the N n 2 possible pairs of n-samples. Indeed, the p-value defined in Section 2 is random in the sense that different p-values can be associated to the same two N -samples. Moreover, the power is not that high because of n, which can be very small in comparison to N .

As an example, in Figure 13, we split an N = 2000-sample X = {X 1 , X 2 , . . . , X N } from the distribution µ 10 on the spiral with shape parameter v = 10, into N n = 100 disjointed subsets

X 1 = {X 1 , X 2 , . . . , X n }, X 2 = {X n+1 , X n+2 , . . . , X 2n }, . . . XN n = {X N -n+1 , X N -n+2 , . . . , X N },
T i = √ nW 1 (d 1 X ,m (1 Xi ), d 1 Y ,m (1 Yi )).
Note that the N n p-values would be independent if we replaced d 1 X ,m by d µ10 ,m in the computation of the test statistic, and if the subsampling distribution was replaced with the true distribution of the statistic. In practice, when N is big enough, we are close to these assumptions. Then the p-values p1 , p2 ,. . . p N n should behave like independent random variables uniformly distributed on [0, 1].

In figure 13, we have sorted these N n = 100 p-values, which were built after repeating subsampling N sub = 1000 times and with mass parameter m = 0.05. They seem to be uniform on [0, 1]; indeed their associated cumulative distribution function lies close to the diagonal.

We use this randomness to propose the following method (DTM-KS) to improve the power of our statistical test. We apply a one-sample Kolmogorov-Smirnov test of uniformity on [0, 1] to the sample p1 , p2 ,. . . p N n . Then we get a p-value p KS . Thanks to the previous imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019 heuristic, this p-value should be close to uniform on [0, 1] if the hypothesis H 0 of the isomorphism test was satisfied, and should be small if most of the p-values p1 , p2 ,. . . p N n were small. We can hope for a power improvement. In Figure 16, we evaluate the type-I error and the power for this new method, with the same procedure as in Section 4.2 and the same parameters.

In Figure 17, we evaluate the type-I error and the power for the testing method (DTM-KS2) consisting in applying a one-dimensional Kolmogorov-Smirnov test of uniformity on [0, 1] to the p-values p 1 , p 2 ,. . . p 100 , where p i is obtained from the test statistic

T i = √ nW 1 (d 1 X ,m (1 X i ), d 1 Y ,m (1 Y i ))
with X 1 , X 2 ,. . . X 100 and Y 1 , Y 2 ,. . . Y 100 independent n-samples without replacement from X and Y respectively. The procedure is the same as in Section 4.2 and the parameters are the same as well. These procedures lead to major improvements for the power, but the type-I error degrades.

Concluding remarks and perspectives

This paper opens a new horizon of statistical tests based on shape signatures. It could be of interest to adapt these kind of methods to other signatures, if possible. In future it could even be interesting to build statistical tests based on many different signatures, leading to an even better discrimination. Regarding the test proposed in this paper itself, the geometric and statistical problem of the choice of the best parameters to use in practice is still an open, tough and engaging question.

A.1. The distance to uniform measures

Here, we derive some properties of the spaces (O, • 2 , µ O ). We give a lower bound for the minimum of the distance to the measure µ O and give a description of the points attaining this bound. First, we state some technical lemma proposed by Lieutier in [START_REF] Lieutier | Any Open Bounded Subset of R n Has the Same Homotopy Type Than Its Medial Axis[END_REF].

M(O) ⊂ Sk(O) ⊂ M(O).

Now we can formulate some technical lemma:

Lemma A.2. For any x in O, there exist a maximal ball for the inclusion, included in O and containing x.

Proof. Let us consider the class S = {B(y, r) | r > 0 and x ∈ B(y, r) ⊂ O} of all non-empty open balls included in O and containing x. We are going to show that this class contains a maximal element by using the Zorn's lemma. For this, we need to show that the partiallyordered set S is inductive, which means that any non-empty totally-ordered subclass T of S is bounded above by some element of S. Let T be a non-empty totally-ordered subclass of S. Set R = sup{r > 0 | ∃ y ∈ O, B(y, r) ∈ T } the supremum of the radii of all balls in T . Since T is non-empty and O is bounded, R is positive and finite. Let (y k ) k∈N be a sequence of centres of balls in T converging to a point y in R d such that the sequence of associated radii (r k ) k∈N is non decreasing with R as a limit. Since T is totally-ordered and the radii non decreasing, for every K ∈ N, k≤K B(y k , r k ) = B(y K , r K ) . Then, the union k∈N B(y k , r k ) is equal to B(y, R). Thus, B(y, R) belongs to S and upper bounds T . So the class S is inductive and thanks to the Zorn's lemma, it contains a maximal element.

Proof of Example 2.1:

For any point x in O and r > 0, thanks to Lemma A.2 there exist a maximal ball B(x , r ) included in O ∩ B(x, r) which contains x. Assume for the sake of contradiction that r < min r 2 , Reach(O) . Since r < r 2 , the ball B(x , r ) is included in B(x, r) thus B(x , r ) is maximal in O. So x belongs to Sk(O), and thanks to Lemma A.1, to M(O). But r < Reach(O); this is a contradiction.

It follows that:

µ O (B(x, r)) ≥ µ O B x , min Reach(O), r 2 .
So, for r ≤ 2Reach(O), since 2Reach(O) ≤ D(O) by considering a point on Sk(O), we get:

µ O (B(x, r)) ≥ r d Reach(O) D(O) d ω d Leb d (O) , which is also true for r in [2Reach(O), D(O)], whereas for r ≥ D(O) we have µ O (B(x, r)) = 1 .
The choice of a in the lemma is thus relevant.

We now focus on the set of points in R d minimizing the distance to the measure µ O . For this, we need some lemma.

Lemma A.3. If x in R d satisfies µ O (B(x, )) = ω d d Leb d (O) , then B(x, ) ⊂ O.
O (m,O) .
Proof. Note that for all positive l smaller than m, we have:

δ µ,l (x) ≥ lLeb d (O) ω d 1 d
.

Moreover, these inequalities are equalities for all points x in O (m,O) . By integrating, we get the lower bound d min for x → d µ,m (x), and it is attained on O (m,O) . Now take some point x in R d satisfying d µ,m (x) = d min . For almost all l smaller than m, we have:

δ µ,l (x) = lLeb d (O) ω d 1 d
. In particular we get for these values of l that:

µ B x, mLeb d (O) ω d 1 d > l. So, µ B x, mLeb d (O)
{x ∈ R d | d µ,m (x) = d min } (m,O) = O,
where for any set A, the notation A stands for x∈A B(x, ), the -offset of A.

Proof. Recall that, thanks to Proposition A. Then, definition of the L 1 -Wasserstein metric as the L 1 -norm between the cumulative distribution functions yields that:

1 that {x ∈ R d | d µ,m (x) = d min } = O (m,O) . Moreover, O (m,O) (m,
W 1 (d µ O ,m (µ O ), d µ O ,m (µ O )) ≥ max(dmin,d min) min(dmin,d min) F dµ O ,m (µ O ) (x) -F dµ O ,m (µ O ) (x)
F dµ O ,m (µ O ) (x) -F dµ O ,m (µ O ) (x) dx ≥ (d min -d min )µ O O (m,O) .

A.3. The DTM-signature to discriminate between uniform and non uniform measures.

Proof of Proposition 3.7: As for Proposition A. , that:

W 1 (d µ O ,m (µ O ), d ν,m (ν)) ≥ dmin t=0 ν {f ≥ λ(t)} λ(t) -1 d mLeb d (O) ω d 1 d
dt.

Since a cumulative distribution function is non decreasing, we get:

W 1 (d µ O ,m (µ O ), d ν,m (ν)) ≥ dmin t=0 sup t ≤t ν {f ≥ λ(t )} λ(t ) -1 d mLeb d (O) ω d 1 d dt = ∞ λ=1 d min 1 d 1 λ 1 d 1 λ sup λ ≥λ ν {f ≥ λ } λ -1 d mLeb d (O) ω d 1 d dλ ≥ 1 d + 1 mLeb d (O) ω d 1 d ∞ λ=1 1 λ 1+ 1 d sup λ ≥λ λ µ O {f ≥ λ } mLeb d (O) λ ω d 1 d
dλ. we have:

Proof of

{f ≥ λ + L (λ) χ } ∩ O (λ) ⊂ {f ≥ λ} (λ) .
According to Proposition 3.7, the aim is thus to show that for some λ bigger than 1, the set {f ≥ λ + L (λ) χ } ∩ O (λ) is non-empty. We thus focus on the supremum of f over O (λ) , which we denote by f ∞, (λ) and try to prove that it is bigger than λ + L (λ) χ .

Remind that if Reach(O) ≥ (λ), then thanks to Proposition A.2, the set O (λ) (λ) equals O. Since f is Hölder, we can thus build some sequence (

y n ) n∈N in O (λ) , such that f (y n ) ≥ f ∞,O -1 n -L (λ) χ .
Finally we get:

f ∞, (λ) ≥ f ∞,O -L (λ) χ . So the quantity W 1 (d µ O ,m (µ O ), d ν,m (ν)) is positive whenever: f ∞,O > inf {λ + 2L (λ) χ | λ ≥ 1, (λ) ≤ Reach(O)} . With λ 0 = 1, we have λ 0 + 2L (λ 0 ) χ = 1 + 2L mLeb d (O) ω d χ d .
With λ 1 satisfying (λ 1 ) = Reach(O), we have:

λ 1 + 2L (λ 1 ) χ = 1 (Reach(O)) d mLeb d (O) ω d + 2L(Reach(O) χ ).
We also have that It proves the first part of the proposition.

The second part is a straightforward consequence of the proof of Proposition 3.7.

Proof of Example 3.8:

The measure ν is absolutely continuous with respect to µ O with density f defined by

f (x) = C σ 1 (2π) d 2 σ d exp - x 2 2 2σ 2 , with C σ = 1 B(0 ,1 ) 1 (2π) d 2 σ d exp - x 2 2 2σ 2 dx
.

Thanks to the previous proposition, we can prove that the signatures are discriminative provided that σ is small enough, for all m smaller than 0.

m ∈ σ d 2 +d d 2 d (2π) d 2 2 C d σ exp d 2 , min 1, C σ exp d 2 d 2 d 1 d + 1 1 d+1 , 2 d C σ exp -1 2 (2π) d 2 σ d+1 .
When σ is small enough, this last assumption can be rewritten as follows In order to get these results, we use Proposition 3.9. Thanks to the mean value theorem on B(0 , 1 ), which is a convex subset of R d , the density f is Lipschitz with parameter Note that when σ goes to zero, the scaling parameter C σ goes to 1.

m ∈ σ d 2 +d d 2 d (2π) d 2 2 C d σ exp d 2 , min {1, C σ C d } , with C d = 2 d exp -1 2 (2π)
L = C σ exp -1 2 (2π)
The lemma follows from the equality:

W 1 (d μN ,m (μ n ), d νN ,m (ν n )) = +∞ 0 1 n n i=1 1 d μN ,m (Xi )≤s - n i=1
1 d νN ,m (Yi )≤s ds, with (X 1 , X 2 , . . . , X N ) a N -sample from µ.

C.2. L 1 -Wasserstein distance between the laws of interest

Lemma C.2. The quantity

W 1 L N,n,m (µ, µ), L * N,n,m (μ N , μN ) is bounded above by 2 √ n (E[ d μN ,m -d µ,m ∞,X ] + W 1 (d µ,m (µ), d µ,m (μ N )) + d µ,m -d μN ,m ∞,X ) .
Proof. Let (X 1 , X 2 , . . . X N ) be a N -sample of law µ, and μN the associated empirical measure. We can upper bound the L 1 -Wasserstein distance between the subsampling distribution

L * ( √ nW 1 (d μN ,m (µ * n ), d μN ,m (µ * n ))|μ N )
and the distribution of interest

L( √ nW 1 (d μN ,m (μ n ), d μ N ,m (μ n ))), by W 1 L √ nW 1 (d μN ,m (µ * n ) , d μN ,m (µ * n )) |μ N , L √ nW 1 (d µ,m (µ * n ) , d µ,m (µ * n )) |μ N (C.1) + W 1 L √ nW 1 (d µ,m (µ * n ) , d µ,m (µ * n )) |μ N , L √ nW 1 (d µ,m (μ n ) , d µ,m (μ n )) (C.2) + W 1 L √ nW 1 (d µ,m (μ n ) , d µ,m (μ n )) , L √ nW 1 d μN ,m (μ n ) , d μ N ,m (μ n ) . (C.3)
We bound the term C.1 by

2 √ n d µ,m -d μN ,m ∞,X . the term C.2 by 2 √ nW 1 (d µ,m (µ), d µ,m (μ N )) and the term C.3 by 2 √ nE[ d µ,m -d μN ,m ∞,X ].
This is proved in the three following lemmas.

Lemma C.3 (Study of term C.3).

We have Proof. To bound this L 1 -Wasserstein distance, we choose as a transport plan the law of the random vector

W 1 L( √ nW 1 (d μN ,m (μ n ), d μ N ,m (μ n ))), L( √ nW 1 (d µ,m (μ n ), d µ,m (μ n ))) ≤ 2 √ nE[ d µ,m -d μN ,m ∞,X ].
( √ nW 1 (d μN ,m (μ n ), d μ N ,m (μ n )), √ nW 1 (d µ,m (μ n ), d µ,m (μ n ))),
with μn , μ n , μN-n and μ N -n independent empirical measures of law µ. Then the L 1 -Wasserstein distance is bounded by

E[| √ nW 1 (d μN ,m (μ n ), d μ N ,m (μ n )) - √ nW 1 (d µ,m (μ n ), d µ,m (μ n ))|],
which is not bigger than:

√ nE[W 1 (d μN ,m (μ n ), d µ,m (μ n )) + W 1 (d μ N ,m (μ n ), d µ,m (μ n ))]. We bound the term E[W 1 (d μN ,m (μ n ), d µ,m (μ n ))] by E[ d µ,m -d μN ,m ∞,X ], thanks to Lemma C.6.
Lemma C.4 (Study of term C.2). We have

W 1 L( √ nW 1 (d µ,m (μ n ), d µ,m (μ n )), L( √ nW 1 (d µ,m (µ * n ), d µ,m (µ * n ))|μ N ) ≤ 2 √ nW 1 (d µ,m (µ), d µ,m (μ N )).
Proof. Let π be the optimal transport plan associated to W 1 n δ Zi , we have:

W 1 (d µ,m (μ n ), d µ,m (µ * n )) = +∞ t=0 1 n n i=1 1 dµ,m (Yi )≤t - 1 n n i=1 1 dµ,m (Zi )≤t dt ≤ 1 n n i=1 +∞ t=0 1 dµ,m (Yi )≤t -1 dµ,m (Zi )≤t dt = 1 n n i=1 |d µ,m (Y i ) -d µ,m (Z i )| . So, the L 1 -Wasserstein distance is not bigger than 2 √ nE[|d µ,m (Y ) -d µ,m (Z )|],
with (d µ,m (Y ), d µ,m (Z )) of law π, so we get the upper bound: Lemma C.5 (Study of term C.1). We have

2 √ n (W 1 (d µ,m (µ), d µ,m (μ N )) . imsart-
W 1 L( √ nW 1 (d µ,m (µ * n ), d µ,m (µ * n ))|μ N ), L( √ nW 1 (d μN ,m (µ * n ), d μN ,m (µ * n ))|μ N ) ≤ 2 √ n d µ,m -d μN ,m ∞,X .
Proof. It is the same proof as for the first lemma, except that μN is fixed.

Lemma C.6. Let ν, µ and µ be some measures over some metric space (X , δ), we have:

W 1 (d µ,m (ν), d µ ,m (ν)) ≤ X |d µ,m (x) -d µ ,m (x)|dν(x) ≤ d µ,m -d µ ,m ∞,Supp(ν) .
Proof. We chose the transport plan (d µ,m (Y ), d µ ,m (Y )) for Y of law ν.

Thanks to Proposition 3.1 and to the fact that the distance to a measure is 1-Lipschitz, we can derive another upper bound depending only on the L 1 -Wasserstein distance between the measure µ and its empirical versions:

Corollary C.1. The quantity W 1 L N,n,m (µ, µ), L * N,n,m (μ N , μN ) is bounded above by 2 √ n m E [W 1 (μ N , µ)] + 2 √ n 1 + 1 m W 1 (μ N , µ).
The rates of convergence of the L 1 -Wasserstein distance between a Borel probability measure on the Euclidean space R d and its empirical version are faster when the dimension d is low; see [START_REF] Fournier | On The Rate Of Convergence In Wasserstein Distance Of The Empirical Measure[END_REF]. Thus, we prefer to use the first bound for regular measures. In this case, we use rates of convergence for the distance to a measure, derived in [START_REF] Chazal | Rates Of Convergence For Robust Geometric Inference[END_REF]. For regular measures, in some cases, the bound in Lemma C.2 is better than the bound in Corollary C.1.

C.3. An asymptotic result with the convergence to the law of G µ,m -G µ,m 1

Proof of Lemma 2.1: The random function √ n F dµ,m (µ) -F dµ,m (μn ) converges weakly in L 1 to some Gaussian prossess G µ,m with covariance kernel

κ(s, t) = F dµ,m (µ) (s) 1 -F dµ,m (µ) (t)
for s ≤ t; see [START_REF] Del Barrio | Central Limit Theorems For The Wasserstein Distance Between The Empirical And The True Distributions[END_REF] or part 3.3 of [START_REF] Bobkov | One-Dimensional Empirical Measures, Order Statistics And Kantorovich Transport Distances. the Memoirs of the AMS -American Mathematical Society[END_REF]. Thanks to Theorem 2.8, p.23, in [START_REF] Billingsley | Convergence of Probability Measures[END_REF], since L 1 × L 1 is separable and μn and μ n are independent, the random vector

√ n F dµ,m (µ) -F dµ,m (μn ) , √ n F dµ,m (µ) -F dµ,m (μ n )
converges weakly to (G µ,m , G µ,m ) with G µ,m and G µ,m independent Gaussian processes.

Since the map (x, y) → x -y is continuous in L 1 , the mapping theorem states that √ n F dµ,m (μ n ) -F dµ,m (μn ) converges weakly to the Gaussian process G µ,m -G µ,m in L 1 .

Once more we use the mapping theorem with the continuous map x → x 1 and the definition of the L 1 -Wasserstein distance as the L 1 -norm of the cumulative distribution functions to get that:

√ nW 1 (d µ,m (μ n ), d µ,m (μ n )) G µ,m -G µ,m 1 .
We then get the convergence of moments following the same method as for Theorem 2.4 in [START_REF] Del Barrio | Central Limit Theorems For The Wasserstein Distance Between The Empirical And The True Distributions[END_REF]. We have the bound

E[ t → 1 dµ,m (Xi )≤t -1 dµ,m (Yi )≤t 1 ] ≤ D µ < ∞.
E[ √ nW 1 (d µ,m (μ n ), d µ,m (μ n ))] → E[ G µ,m -G µ,m 1 ].
We deduce that:

W 1 L √ nW 1 (d µ,m (μ n ) , d µ,m (μ n )) , L G µ,m -G µ,m 1 → 0.
Moreover, we have the bound:

W 1 L √ nW 1 (d µ,m (μ n ) , d µ,m (μ n )) , L N,n,m (µ, µ) ≤ 2 √ nE[ d µ,m -d μN ,m ∞,X ]. So, if √ nE [ d µ,m -d μN ,m ∞,X ] → 0 when N → ∞,
we have that:

W 1 L N,n,m (µ, µ), L G µ,m -G µ,m 1 → 0.
Finally, with the same arguments as for Lemma C.2, we get that:

W 1 L * N,n,m (μ N , μN ), L G µ,m -G µ,m 1 ≤ W 1 L √ nW 1 (d µ,m (μ n ) , d µ,m (μ n )) , L G µ,m -G µ,m 1 + 2 √ nW 1 (d µ,m (µ), d µ,m (μ N )) + 2 √ n d µ,m -d μN ,m ∞,X .
Since µ is compactly-supported d µ,m (µ) is also compactly supported. Moreover, Theorem 3.2 of Bobkov and Ledoux [START_REF] Bobkov | One-Dimensional Empirical Measures, Order Statistics And Kantorovich Transport Distances. the Memoirs of the AMS -American Mathematical Society[END_REF] states that for any probability P on R with cumulative distribution function given by F P , √

N E [W 1 (P, P N )] ≤ +∞ -∞ F P (s)(1 -F P (s))ds. As a consequence, since n N = o(1), the expectation √ nE [W 1 (d µ,m (µ), d µ,m (μ N ))] converges to zero. Finally, if E [ √ n d µ,m -d μN ,m ∞,X
] converge to 0, using the Markov inequality, we get that W 1 L * N,n,m (μ N , μN ), L G µ,m -G µ,m 1 converges to 0 in probability.

Proof of Lemma 2.2: Let < α and η be two positive numbers.

The probability P (µ,ν) (φ N,n,m = 1) is bounded above by

P √ nW 1 (d μN ,m (μ n ), d νN ,m (ν n )) ≥ q 1 -(α+ ) -η + P q1-α < q 1 -(α+ ) -η .
For convenience, we use the notation

L = L 1 2 G µ,m -G µ,m 1 + 1 2 G ν,m -G ν,m 1 and L * = 1 2 L * N,n,m (μ N , μN ) + 1 2 L * N,n,m (ν N , νN ). Then, q 1 -(α+ ) is the 1 -(α + )-quantile of L and q1-α , the 1 -α-quantile of L * . If q1-α < q 1 -(α+ ) -η, then, W 1 (L, L * ) ≥ q 1 -(α+ ) q1-α |F L (x) -F L * (x)| dx ≥ (q 1 -(α+ ) -q1-α )((1 -α) -(1 -α -)) ≥ η
since for x ≥ q1-α , F L * (x) ≥ 1 -α, and for x < q 1 -(α+ ) , F L (x) ≤ 1 -α -.

Then, it comes that P (q 1-α < q 1 -α+ -η) is bounded above by P (W 1 (L, L * ) ≥ η). it comes that P (q 1-α < q 1 -α+ -η) ≤ P (B N,n ≥ η), which goes to zero when N goes to ∞, since the second convergence in Lemma 2.1 is satisfied. Finally, under the H 0 hypothesis, the distribution of √ nW 1 (d μN ,m (μ n ), d νN ,m (ν n )) is given by L N,n,m (µ, µ), L N,n,m (ν, ν) or equivalently by 1 2 L N,n,m (µ, µ)+ 1 2 L N,n,m (ν, ν). Then, the fact that the first convergence in Lemma 2.1 occurs and the Portmanteau lemma entail that lim sup N →∞ P (µ,ν) (φ N,n,m = 1) is bounded above by P Z ≥ q 1 -(α+ ) -η , with Z a random variable from the distribution 1 2 L( G µ,m -G µ,m 1 ) + 1 2 L( G ν,m -G ν,m 1 ), which has the same distribution as L( G µ,m -G µ,m 1 ) and L( G ν,m -G ν,m 1 ) under hypothesis H 0 .

We now make η and go to zero and under the continuity assumption, lim sup

N →∞ P (µ,ν) (φ N,n,m = 1) ≤ α.
As well, we get that lim inf N →∞ P (µ,ν) (φ N,n,m = 1) ≥ α. Proof of part 2 of Proposition 2.1: We may assume that the diameter D µ of the support of the measure µ equals 1. Indeed, if we apply a dilatation to the measure to make the diameter of its support be equal to 1, then the quantity W 1 L N,n,m (µ, µ), L * N,n,m (μ N , μN ) is simply multiplied by the parameter of the dilatation. By using Corollary C.1 and Theorem 1 of [START_REF] Fournier | On The Rate Of Convergence In Wasserstein Distance Of The Empirical Measure[END_REF], we have a bound for the expectation:

C.4. The case of measures supported on a compact

E W 1 L N,n,m (µ, µ), L * N,n,m (μ N , μN ) ≤      C √ n m N -1 d if d>2 C √ n m N -1 2 log(1 + N ) if d=2 C √ n m N -1 2 if d<2
for some positive constant C depending on µ. Proof. The idea is to put a grid on the hypercube containing X with edges of length D µ . The grid is a union of small hypercubes with edges of length equal to λ √ d , so that the number of such small hypercubes into which the big one is split is not superior to

Dµ √ d λ + 1 d .
Then, we decide that each time the intersection between X and some small hypercube is non-empty, we keep one of the elements of the intersection. We denote x i the element associated to the i-th hypercube. Finally, each point x in X belongs to a small hypercube, and its distance to the corresponding x i is smaller than In order to get upper bounds for E[ d μN ,m -d µ,m ∞,X ], we use the same trick as used in [START_REF] Chazal | Rates Of Convergence For Robust Geometric Inference[END_REF], which is:

Lemma C.9. Let X a random variable such that: P(X ≥ λ) ≤ 1 ∧ Dλ -q exp(-cλ s )

for some integers q and s and some D > 0.

We have:

E[X] ≤ ln c c 1 s q s 1 s
1 + D q s -q-s s (ln c) -q-s s s .

More particularly, if c ≥ exp D Proof. For any λ 0 > 0, that we can choose as λ 0 = [ln K] We need to notice that with similar arguments as for Lemma C.2, we have:

  δ µ,m (x) = inf{r > 0 | µ(B(x, r)) > m}, with B(x, r) = {y ∈ X | δ(x, y) ≤ r}. The function distance to the measure (DTM) µ with mass parameter m and denoted d µ,m is then defined for all x in X by d µ,m (x

Definition 1 . 4 (

 14 empirical DTM-signature). Given a N -sample X 1 , X 2 ,. . . X N from a Borel probability measure µ, with the notation μN = 1 N N i=1 δ Xi and μn = 1 n n i=1 δ Xi for some n ≤ N , we define the empirical DTM-signature as the discrete Borel probability measure on R, d μN ,m (μ n ).

  conditionally to μN , where µ * n and µ * n are two empirical measures from independent n-samples from μN .

Example 2 . 1 ..

 21 . Uniform measures on open subsets of R d are particular cases of such regular distributions: Let O be a non-empty bounded open subset of R d . Then, the uniform measure on O, µ O is (a, d)-standard with Here, D(O) stands for the diameter of O, ω d for Leb d (B(0 , 1 )), the Lebesgue volume of the unit d-dimensional ball, and Reach(O) is the reach of the open set O as defined in Section 3.2.3. Proof. Proof in the Appendix, in Section A.1.

Proposition 3 . 3 .

 33 imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019 If (X , δ, µ) and (Y, δ, ν) are two metric measure spaces embedded into some metric space (Z, δ), then we can bound W 1 (d µ,m (µ), d ν,m (ν)) above by

  8 and Proposition 3.9. The proofs are based on the fact that two signatures d µ,m (µ) and d ν,m (ν) are different whenever the set {x | d ν,m (x) > inf x∈Supp(µ) d µ,m (x)} has imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019

ω d 1 d

 1 is the radius of any ball B ⊂ O such that µ O (B) = m, and ω d equals Leb d (B(0 , 1 )), the Lebesgue volume of the unit d-dimensional ball. Proof. Proof in the Appendix, in Section A.2. This proposition can be applied to a simple case. imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019 Example 3.2. Let O be the open unit ball in R d , and O the hypercube of radius 1 in R d . Then, the DTM-signature discriminates between µ O and µ O whenever m < ω d 2 d .

Example 3 . 4 .

 34 Set > 1. The uniform distributions on the rectangle O = [0, ] × 0, π and the ball O = B(0, 1) in R 2 have a different signature for m = 2 . Proof. The set O is empty but O is not empty. Example 3.5. Set 1 > > > 0. The uniform distributions on the rectangle O = [0, ] × 0, 1 and the rectangle

Example 3 . 6 .

 36 imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019 The uniform distributions on the circle O = {x ∈ R 2 | x = 1} and on the segment O = [0, 2π] × {0} have a different signature for every m ∈ (0, 1].

ω d 1

 1 d d d+1 and ω d stands for Leb d (B(0 , 1 )), the Lebesgue volume of the unit d-dimensional ball. Proof. Proof in the Appendix, in Section A.3.

Proposition 3 . 8 .

 38 Let µ and ν be two distributions on R d with respective densities g and f with respect to the Lebesgue measure Leb d . Assume that g(x) ≤ g max for every x ∈ R d . Then, a lower bound for W 1 (d µ,m (µ), d ν,m (ν)) is given by d min g lower bound for the function d µ,m . Proof. Proof in the Appendix, in Section A.3. Actually, Proposition 3.7 is a consequence of Proposition 3.8. It suffices to replace g max with 1 Leb d (O) , the value of the density of µ O with respect to the Lebesgue measure, on O. In the following, we work with the framework of Proposition 3.7.

Figure 3 .

 3 Figure 3. Medial Axis and Reach of an open set

Example 3 . 8 .

 38 Let O be the open unit ball B(0 , 1 ) in R d , µ O the uniform measure on O and ν the multivariate normal distribution N (0, σ 2 I) restricted to B(0 , 1 ).The signatures are discriminative, provided that σ is small enough, for all m smaller than 0.23 if d = 1; 0.30 if d = 2; 0.68 if d = 3; and for all values of m if d ≥ 4.

First, from the

  measure µ = µ 10 we get an N = 2000-sample X = {X 1 , X 2 , . . . , X N }. As well, we get an N = 2000-sample Y = {Y 1 , Y 2 , . . . , Y N } from the measure ν = µ 20 .

Figure 4 .

 4 Figure 4. DTM-signature estimates, m = 0.05

Figure 5 .

 5 Figure 5. Subsampling validity, v = 10, m = 0.05

Figure 6 .

 6 Figure 6. Type-I error and power approximations

Figure 7 .

 7 Figure 7. MNIST database of handwritten digits

  N } and {Y 1 , Y 2 , . . . , Y N }, the idea of applying a Kolmogorov-Smirnov test to the set of points D P = {d μN ,m (X 1 ), d μN ,m (X 2 ), . . . , d μN ,m (X N )} on one hand, and the set of points D Q = {d νN ,m (Y 1 ), d νN ,m (Y 2 ), . . . , d νN ,m (Y N )} on the other fails drastically. Indeed, using a Kolmogorov-Smirnov test requires independence in the data, which the data D P and D Q do not satisfy.In the following figure, we have plotted the cumulative distribution functions associated to the uniform measures on D P and D Q , where µ and ν are equal and defined as in Section 4.2, with v = 10. The p-value was equal to 4.10 -6 ≤ 0.05, thus the hypothesis H 0 was rejected.

Figure 9 .

 9 Figure 9. DTM-signature estimates, m = 0.05

Figure 11 .Figure 12 .

 1112 Figure 10. l = 20

with n = 20 .

 20 As well, we split Y, an N = 2000-sample from µ 10 into N n = 100 disjointed subsets Y 1 , Y 2 ,. . . YN n . Then, with the notation in the algorithm in Section 4.1, we consider the p-values p1 , p2 ,. . . p N n with pi associated to

Figure 13 .Figure 14 .Figure 15 .

 131415 Figure 13. Sorted p-values p1 , p2 ,. . . p N n

Lemma A. 1 .

 1 If we define the skeleton Sk(O) of the open set O as the set of centres of maximal balls (for the inclusion) included in O, then we get:

Proposition A. 1 . 1 d

 11 imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019 Proof. If x in R d satisfies µ O (B(x, )) = ω d d Leb d (O) , then, Leb d (O c ∩ B(x, )) = 0 . Assume for the sake of contradiction that the set O c ∩ B(x, ) is not empty. Since O • = O, then the open subset (O c ) • ∩ B(x, ) of O c ∩ B(x, ) is not empty, thus of positive Lebesgue measure, which is absurd. So B(x, ) ⊂ O. The constant d min = d d+1 mLeb d (O) ω d is a lower bound for the distance to the measure µ O over R d . Moreover, the set of points attaining this bound is exactly

ω d 1 dProposition A. 2 .

 12 = m, and thanks to Lemma A.3, we get that x ∈ O (m,O) . If Reach(O) ≥ (m, O), then:

Proof of Proposition 3 . 5 :+ 1 mLeb

 351 O) ⊂ O. Assume for the sake of contradiction that the set O\O (m,O) (m,O) is non-empty. Take a point x in this set and consider B(x , r ) a maximal ball containing x and included in O given by Lemma A.2. Since x / ∈ O (m,O) (m,O) , we get that r < (m, O). Moreover, x belongs to Sk(O) and so, thanks to Lemma A.1, to M(O). Then, by continuity of the function distance to the compact set ∂O, r = d ∂O (x ) ≥ Reach(O) ≥ (m, O), which is a contradiction. So, O (m,O) (m,O) = O.A.2. The DTM-signature to discriminate between two uniform measures withdifferent density. This proposition comes from the fact that for m small enough, for both mm-space, the distance-to-a-measure function will attain its minimum on a set of positive measure. Moreover, the two minima are different since the Lebesgue measure of the open sets are different. More precisely, if the set O (m,O) is non-empty, then the minimal value of the distance to a measure is given by min x∈R d (d µ O ,m (x)) = d min := d d points at minimal distance are exactly the points of O (m,O) . This is Proposition A.1. So, F dµ O ,m (µ O ) (d min ) = µ O O (m,O) and F dµ O ,m (µ O ) (x) = 0 for every x < d min . The same holds for O : F dµ O ,m (µ O ) (d min ) = µ O O (m,O ) and F dµ O ,m (µ O ) (x) = 0 for every x < d min :=

Proof of Example 3 . 2 : 1 d 1 d

 3211 Since Leb d (O) = ω d , (m, O) = m , and O (m,O) is the ball of radius 1 -(m, O), thus, µ O O (m,O) = 1 -m 1 d d . Also, Leb d (O ) = 2 d , (m, O ) = 2 m ω d , and O (m,O ) is the hypercube of radius 1 -(m, O ), thus, µ O O (m,O ) = 1m is smaller than ω d 2 d , the DTM-signature discriminates between µ O and µ O . Moreover, the L 1 -Wasserstein distance between the signatures is bounded below by 1

Proposition 3 . 8 : 1 d 1 d m ω d 1 d 1 d 9 :

 3811119 Since µ(B(x, r)) ≤ ω d r d g max , for every x ∈ R d , d µ,m (x) ≤ d min . For every x ∈ {f ≥ λ} λ , ν B x, λ -≥ m, thus, d ν,m (x) ≤ d min . W 1 (d µ,m (µ), d ν,m (ν)) thatthe density f is Hölder over O with parameters χ in [0, 1] and L positive. imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019 Proof of Proposition 3.First notice that for all positive λ, with (λ) = λ -1 d mLeb d (O) ω d 1 d

  inf {λ + 2L (λ) χ | λ > 0} = (2L)

  23 if d = 1; 0.30 if d = 2; 0.68 if d = 3; and for all value of m is d ≥ 4. More precisely, the signatures are discriminative when m ≤ σ d exp d ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019 or when

d 2 σ

 2 d+1 . Note that C d is much bigger than 1 when d ≥ 4. Also, C 1 0.23, C 2 0.30, C 3 0.68.

d 2 σ d+1 .

 d+1 Thus we use χ = 1 since f is Lipschitz. Moreover, the reach of a ball is equal to its radius, thus Reach(O) = 1 , and Leb d (O) = ω d by definition.

Since W 1

 1 (L, L * ) ≤ B N,n with B N,n := 1 2 W 1 (L * N,n,m (μ N , μN ), G µ,m -G µ,m 1 )+ 1 2 W 1 (L * N,n,m (ν N , νN ), G ν,m -G ν,m1 ), imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019

1 : 2 ,

 12 subset of R d Proof of part 1 of Proposition 2.We need to show that under the assumptionρ > max{d,2} √ nE[ d µ,m -d μN ,m ∞,X ] → 0 . First consider d > 2.Thanks to Theorem 1 of[START_REF] Fournier | On The Rate Of Convergence In Wasserstein Distance Of The Empirical Measure[END_REF], there is some positive constant C depending on µ such that for N big enough:E[W 1 (μ N , µ)] ≤ CN -1 d .Then, according to Proposition 3.1,√ nE d µ,m -d μN ∞ ≤ √ n m CN -1 d . It converges to 0 when ρ > d 2 .For d ≤ 2, we use the other bounds from Fournier and Guillin, the condition is then ρ > 1.

Proof of part 3 of Proposition 2 . 1 :

 21 First notice that for λ > 1,P W 1 L N,n,m (µ, µ), L * N,n,m (μ N , μN ) ≥ λ = 0under the assumption D µ = 1. We thus focus on values of λ not bigger than 1. In this case, with the Theorem 2 of[START_REF] Fournier | On The Rate Of Convergence In Wasserstein Distance Of The Empirical Measure[END_REF], we get easily that: imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date:[START_REF] Arlot | Rééchantillonnage et Sélection de Modèles PhD thesis[END_REF]

d k=1 λ 2 dλ 2 2 ,C. 5 . 2 .

 22252 = λ. We thus derive upper bounds for d μN ,m -d µ,m ∞,X :Proposition C.1 (Upper bound for d μN ,m -d µ,m ∞,X ). We have, λ d 2 4D µ √ d + λ d P( d μN ,m -d µ,m ∞,X ≥ λ) + expa 2 2b-1 N b+1 2 m b λ b + exp -a Since the function distance to a measure is 1-Lipschitz, we get that:d μN ,m -d µ,m ∞,X ≤ λ 2 + sup i {|d μN ,m (x i ) -d µ,m (x i )|},for the family (x i ) i associated to a grid which sides are of length equal to λ 4 √ d . We can thus bound the probability P( d μN ,m -d µ,m ∞,X ≥ λ) by N (µ, λ 4 ) i=1 P |d μN ,m (x i ) -d µ,m (x i )| ≥ λ Upper bounds for the expectation E[ d μN ,m -d µ,m ∞,X ]

  ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019

10 .C. 5 . 3 . 2 :W 1 1 2 L 2 L

 1053222 We have, E[ d μN ,m -d µ,m ∞,X ] ≤ for some constants depending on a and b. And hence, √ nE[ d μN ,m -d µ,m ∞,X ] Upper bounds for the expectation of W 1 L N,n,m (µ, µ), L * N,n,m (μ N , μN ) Proof of part 2 of Proposition 2.For all λ > 0, for any (a, b)-standard measure µ supported on a connected compact subset of R d , we can use Lemma C.2 and Lemma C.10 imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019As noticed in the proof of Lemma 2.1, the law of√ nW 1 (d µ,m (μ n ), d µ,m (μ n )) converges to L( G µ,m -G µ,m 1), there is also the convergence of the first moments. So, for n big enough, we have:W 1 (L √ nW 1 (d µ,m (μ n ), d µ,m (μ n )) , L( G µ,m -G µ,m 1 )) ≤ 1.Then, under the assumptionW 1 (L √ nW 1 (d µ,m (μ n ), d µ,m (μ n )) , L * N,n,m (μ N , μN )) ≤ κ,we haveW 1 (L( G µ,m -G µ,m 1 ), L * N,n,m (μ N , μN )) ≤ κ + 1.We can do the same thing for ν. Thus we get that for n big enough and under the previous assumptions:( G µ,m -G µ,m 1 ) + 1 ( G ν,m -G ν,m 1 ), 1 2 L * N,n,m (μ N , μN ) + 1 2 L * N,n,m (ν N ,νN ) is bounded above with κ + 1. And thanks to Lemma C.11, q1-α ≤ q1α 2 + 2 κ + 1 α , with q1-α the 1 -α-quantile of the law 1 2 L( G µ,m -G µ,m 1 ) + 1 2 L( G ν,m -G ν,m 1 ).

W 1 L √ nW 1 2 √ 2 √ n m W 1

 1221 (d µ,m (μ n ), d µ,m (μ n )) , L * N,n,m (μ N , μN ) ≤ nD µ F dµ,m (µ) -F dµ,m (μ N ) ∞,(0,Dµ) + (µ, μN ). Now notice that √ nW 1 (d μN ,m (μ n ), d νN ,m (ν n )) ≥ √ nW 1 (d µ,m (µ), d ν,m (ν)) -√ nW 1 (d μN ,m (μ n ), d µ,m (µ)) -√ nW 1 (d νN ,m (ν n ), d ν,m (ν)) ,but as well, thanks to Lemma C.6, the definition of the L 1 -Wasserstein distance as the L 1 -norm between the cumulative distribution functions and to Proposition 3.1:√ nW 1 (d μN ,m (μ n ), d µ,m (µ)) ≤ √ n m W 1 (µ, μN ) + √ nD µ,m F dµ,m (μn ) -F dµ,m (µ) ∞,(0,Dµ) , with D µ,m the diameter of the support of the measure d µ,m (µ). So, we can finally upper imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019

  This interval is non trivial as soon as d µ,m (µ) is not a Dirac mass. In this case, L( G µ,m -G µ,m 1 ) is atomless, as the distribution of the integral of continuous random variables. A rigorous proof of this intuitive result is out of the scope of this paper. Even so, it should be noted that (G µ,m (t) -G µ,m (t)) t∈R has is the Brownian bridge. Continuity of B 1 follows from former work in the literature. Indeed, Johnson and Killeen

	the same distribution as	√	2B(F dµ,m (µ) (t)) t∈R , where (B(s)) s∈[0,1]
	imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019

  for d = 1. Proof in the Appendix, in Section C.4.

	2.1.2. The case of (a, b)-standard measures supported on a compact subset of R d
	The test is asymptotically valid for two (a, b)-standard measures supported on compact
	connected subsets of R d provided that ρ > 1:
	Proposition 2.2. Let µ be an (a, b)-standard measure supported on a connected compact
	subset of R d . The two convergences of Lemma 2.1 occur if the assumption ρ > 1 is satisfied.

  dx. Assume for instance that d min ≤ d min . Since cumulative distribution functions are nondecreasing, it comes that

	max(dmin,d min)
	min(dmin,d min)

  1, we get that for any point x in O: -ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019We will lower bound the L 1 -Wasserstein distance between d µ O ,m (µ O ) and d ν,m (ν) by the integral of F dν,m (ν) over the interval [0, d min ], since F dµ O ,m (µ O ) equals zero on this interval. We thus need to lower bound F dν,m (ν) (t) for all t ≤ d min .As for Proposition A.1, for λ ≥ 1, any point x of {f ≥ λ}

								λ -1 d	ω d mLeb d (O)	1 d satisfies
	d ν,m (x) ≤ dmin d λ 1	. Thus,
		F dν,m (ν)	d min λ 1 d	≥ ν {f ≥ λ} λ	-1 d	ω d mLeb d (O)	1 d	.
	And we get by denoting λ(t) the real number λ satisfying t = dmin 1 λ d
							1
		d µ O ,m (x) ≥ d min :=	mLeb d (O) ω d	d	d 1 + d	.

imsart

  Independently, from another n-sample of law π, we get d µ,m (μ n ) and d µ,m (µ * n ). The L 1 -Wasserstein distance is then bounded by √ nE π ⊗n ⊗π ⊗n [W

	Now notice that, if we denote μn =	n i=1	1 n δ Yi and µ * n =	n i=1

1 (d µ,m (µ), d µ,m (μ N )); see the definition of the L 1 -Wasserstein with transport plans. From a n-sample of law π, we get two empirical distributions d µ,m (μ n ) and d µ,m (µ

* n ). 1 (d µ,m (μ n ), d µ,m (µ * n )) + W 1 (d µ,m (μ n ), d µ,m (µ * n ))].

  dµ,m (μ n ) -F dµ,m (μn ) converges weakly to the Gaussian process G µ,m -G µ,m in L 1 . So, thanks to Theorem 5.1 in[START_REF] De Acosta | Convergence Of Moments And Related Functionals In The Central Limit Theorem In Banach Spaces[END_REF] (cited in[START_REF] Araujo | The Central Limit Theorem for Real and Banach Valued Random Variables[END_REF] p.136), we have:

	the random function	√	n F

Moreover, imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date: February 19, 2019

L( G µ,m -G µ,m 1 ) + 1 2 L( G ν,m -G ν,m 1 ) and L( G µ,m -G µ,m 1) are equal. Thus, the second assumption of Lemma 2.2 may be replaced by "the 1 -α-quantile of the distribution L( G µ,m -G µ,m 1 ) is a point

imsart-ejs ver. 2014/10/16 file: DTM_sample_comparison_Claire_Brecheteau_new_version.tex date:[START_REF] Arlot | Rééchantillonnage et Sélection de Modèles PhD thesis[END_REF]

Acknowledgements The author is extremely grateful to Frédéric Chazal, Pascal Massart and Bertrand Michel for introducing her to the distance to a measure, for their valuable comments and advise, and for proofreading. Many thanks also to Małgorzata Bogdan for her interest and pertinent comments. As well, Eddie Aamari, Marc Glisse, Clément Levrard and members of the Datashape and Select Inria teams should be thanked for their interest, and Cormac Walsh for the english. Last but not least, the author is extremely grateful to the anonymous referees for their valuable comments and suggestions.

This work was partially supported by the ANR project TopData and GUDHI; the Inria teams Datashape and Select; and the LMO at

We also define the medial axis of O, M(O) as the set of points in O having at least two projections onto ∂O. That is,

Its reach, Reach(O), is the distance between its boundary ∂O and its medial axis

If K is a compact subset of R d , it is standard to define its reach as Reach (K c ), the reach of its complement in R d . See [START_REF] Federer | Curvature Measures[END_REF] to get more familiar with these notions.

In the following, ω d stands for Leb d (B(0 , 1 )), the Lebesgue volume of the unit d-dimensional ball. . This is the radius of a ball included in O, with µ O measure equal to m. For some positive , O stands for the set of points in O which distance to ∂O is not smaller than : The proof is relatively similar to the ones given by Mémoli in [START_REF] Mémoli | Gromov-Wasserstein Distances and the Metric Approach to Object Matching[END_REF] for other signatures.

Appendix

For any map plan π between µ and ν Borel measures on (X , δ) and (Y, γ), we get:

Appendix C: The test

C.1. A lemma

Lemma C.1 (Equality of empirical signatures under the isomorphic assumption). If (X , δ, µ) and (Y, γ, ν) are two isomorphic mm-spaces, then the distributions of the random variables

are equal. Here the empirical measures are all independent and the measures μ N and μ n are from samples from µ.

Proof. Note that for (X 1 , X 2 , . . . , X N ) a N -sample of law µ and φ an isomorphism between (X , δ, µ) and (Y, γ, ν), the tuple (φ

It follows that the distances and the nearest neighbours are preserved. Thus, the distributions of (d μN ,m (X i )) i∈[ [1 ,n]] and (d νN ,m (Y i )) i∈[ [1 ,n]] are equal.

for some positive constants C, C and C depending on µ.

We conclude the proof with the Borel-Cantelli Lemma.

C.5. The case of (a, b)-standard measures

Let µ be a Borel probability measure supported on a connected compact subset X of R d . We assume this measure to be (a, b)-standard for some positive numbers a and b. In this part, we derive rates of convergence in probability and in expectation for the quantity d μN ,md µ,m ∞,X . Thanks to these results, we can derive upper bounds and rates of convergence in expectation for

We finally propose a choice for the parameter N depending on n for which the weak convergence

zero occur.

C.5.1. Upper bounds for P(

We use the bounds given in Theorem 1 of [START_REF] Chazal | Rates Of Convergence For Robust Geometric Inference[END_REF], with the bound for the modulus of continuity given by Lemma 3 in [START_REF] Chazal | Rates Of Convergence For Robust Geometric Inference[END_REF]:

. We directly get the following lemma:

Lemma C.7 (Upper bound for |d μN ,m (x) -d µ,m (x)|). Let x be a fixed point in X and λ a positive number. We have,

In order to derive an upper bound for d μN ,m -d µ,m ∞,X , like in [START_REF] Chazal | Rates Of Convergence For Robust Geometric Inference[END_REF], we use the fact that the function distance to a measure is 1-Lipschitz and that X is compact, which means that we can compute a bound by upper-bounding the difference |d μN ,m (x) -d µ,m (x)| over a finite number of points x of X . Thanks to the following lemma, the minimal number of points needed for this purpose is not bigger than

Then, we have: together with the rates of convergence of the L 1 -Wasserstein distance between empirical and true distribution in [START_REF] Bobkov | One-Dimensional Empirical Measures, Order Statistics And Kantorovich Transport Distances. the Memoirs of the AMS -American Mathematical Society[END_REF] to get the following result.

If m ≥ 1 2 , then for n big enough we have, for some constants depending on a and b:

Proof of part 1 of Proposition 2.2: In order to get these two results, we use Lemma 2.1.

The convergence to zero of

C.6. The power of the test

Proof of Theorem 2.3

Lemma C.11. Let α, κ be two positive numbers and L and L * two laws of real random variables. We denote q 1 -α (respectively q * 1 -α ) the 1 -α-quantile of the law L (respectively L * ). If W 1 (L, L * ) < κ then:

In this part we assume that m is fixed in [0, 1] and N = cn ρ for some ρ > 1 and c > 0.

Recall that our aim is to bound above the type II error, that is:

For some κ = n γ with γ in 0, 1 2 to be chosen later, we first bound above the quantile q1-α with high probability.

For all positive , for n big enough, note that the sum of the last two terms can be bounded thanks to the DKW-Massart inequality [START_REF] Massart | The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality[END_REF], by

Note also that thanks to the DKW-Massart inequality, the first term can be bounded above by