The k-PDTM : a coreset for robust geometric inference∗

arXiv:1801.10346v1 [math.ST] 31 Jan 2018

Brécheteau, Claire
claire.brecheteau@inria.fr
Université Paris-Saclay – LMO & Inria
Levrard, Clément
levrard@math.univ-paris-diderot.fr
Université Paris Diderot – LPMA
February 1, 2018

Abstract

R

Analyzing the sub-level sets of the distance to a compact sub-manifold of d is
a common method in TDA to understand its topology. The distance to measure
(DTM) was introduced by Chazal, Cohen-Steiner and Mérigot in [7] to face the
non-robustness of the distance to a compact set to noise and outliers. This function
makes possible the inference of the topology of a compact subset of d from a noisy
cloud of n points lying nearby in the Wasserstein sense. In practice, these sub-level
sets may be computed using approximations of the DTM such as the q-witnessed
distance [10] or other power distance [6]. These approaches lead eventually to
compute the homology of unions of n growing balls, that might become intractable
whenever n is large.
To simultaneously face the two problems of large number of points and noise,
we introduce the k-power distance to measure (k-PDTM). This new approximation
of the distance to measure may be thought of as a k-coreset based approximation
of the DTM. Its sublevel sets consist in union of k-balls, k << n, and this distance
is also proved robust to noise. We assess the quality of this approximation for k
1
possibly dramatically smaller than n, for instance k = n 3 is proved to be optimal
for 2-dimensional shapes. We also provide an algorithm to compute this k-PDTM.

R

Keywords : distance to a measure, geometric inference, coreset, power function,
weighted Voronoï tesselation, empirical approximation

1

Introduction

1.1

Background on robust geometric inference

Let M ⊂ Rd be a compact set included in the closed Euclidean ball B(0, K), for
K > 0, whose topology is to be inferred. A common approach is to sample Xn =
{X1 , X2 , . . . , Xn } on M , and approximate the distance to M via the distance to the
sample points. As emphasized in [7], such an approach suffers from non-robustness to
outliers. To face this issue, [7] introduces the distance to measure as a robust surrogate
of the distance to M , when Xn = {X1 , X2 , . . . , Xn } is considered as a n-sample, that is
n independent realizations of a distribution measure P whose support Supp(P ) is M ,
possibly corrupted by noise. Namely, for a Borel probability measure P on Rd , a mass
∗ This

work was partially supported by the ANR project TopData and GUDHI

1

parameter h ∈ [0, 1] and x ∈ Rd , the distance of x to the measure P , dP,h (x) is defined
by
Definition 1 (DTM).
d2P,h (x) =

1
h

Z

h
2
δP,l
(x) dl,

δP,l (x) = inf{r > 0 | P(B(x, r)) > l},

with

l=0

where B(x, r) denotes the closed Euclidean ball with radius r. When P is uniform
enough on a compact set with positive reach ρ, this distance is proved to approximate
well the distance to M ([7, Proposition 4.9]) and is robust to noise ([7, Theorem 3.5]).
The distance to measure is usually inferred from Xn via its empirical counterpart,
also
Pn
called empirical DTM, replacing P by the empirical distribution Pn = n1 i=1 δXi , where
δx is the Dirac mass on x.
Mérigot
 et al noted in [10] that the sublevel sets of empirical DTM are union of
around nq balls with q = hn, which makes their computation intractable in practice.
To bypass this issue, approximations of the empirical DTM have been proposed in [10]
(q-witnessed distance) and [6] (power distance). Up to our knowledge, these are the
only available approximations of the empirical DTM. The sublevel sets of these two
approximations are union of n balls. Thus, it makes the computation of topological
invariants more tractable for small data sets, from alpha-shape for instance; see [9].
Nonetheless, when n is large, there is still a need for a coreset allowing to efficiently
compute an approximation of the DTM, as pointed out in [13]. In [12], Mérigot proves
that such a coreset cannot be too small for large dimension.

1.2

Contribution

This paper aims at providing such a coreset for the DTM, to face the case where there
are many observations, possibly corrupted by noise. We introduce the k-power distance
to a measure P (k-PDTM), which is defined as the square root of one of the best kpower functions approximating the square of the DTM from above, for the L1 (P ) norm.
Roughly, we intend to approximate the DTM of a point x with a power distance dP,h,k (x)
of the form
r
2 (θ ),
dP,h,k (x) =
min kx − θi k2 + ωP,h
i
i∈[[1 ,k]]

where the θi ’s and corresponding ω’s are suitably chosen. Its sub-level sets are union of k
balls. Thus, the study of the associated topological invariants gets tractable in practice,
even for massive data.
We begin by providing some theoretical guarantees on the k-PDTM we introduce.
For instance, we prove that it can be expressed as a power distance from a coreset of k
points that are local means of the measure P . The proofs rely on a geometric study of
local sub-measures of P with fixed mass h ∈ [0, 1], showing that such a coreset makes
sense whenever P is supported on a compact set. In particular, we prove that the set
of means of local sub-measures of P is convex. The discrete case relies on the duality
between a weighted Delaunay diagram and its associated weighted Voronoï diagram.
Once the k-PDTM properly defined, the main contribution of our paper are the
following. First we assess that the k-DTM is a good approximation of the DTM in the
L1 sense (Proposition 18), showing for instance that whenever M has dimension d0

2
P d2P,h,k (u) − d2P,h (u) ≤ CP,h k − d0 ,

2

where P f (u) stands for the integration of f with respect to measure P . As mentioned in
Proposition 22, this allows to infer topological guarantees from the sublevel sets of the
k-PDTM.
Second we prove that this k-PDTM shares the robustness properties of the DTM with
respect to Wasserstein deformations (Proposition 21). Namely, if Q is a sub-Gaussian
deformation of P such that the Wasserstein distance W2 (P, Q) ≤ σ ≤ K, it holds

P d2Q,h,k (u) − d2P,h (u) ≤ P d2P,h,k (u) − d2P,h (u) + CP,h σK,
ensuring that the approximation guarantees of our k-PDTM are stable with respect to
Wasserstein noise. Similar to the DTM, this also guarantees that an empirical k-PDTM,
that is built on Xn , is a consistent approximation of the true k-PDTM.
At last, we provide more insights on the construction of the empirical k-PDTM from
a point cloud Xn , facing the practical situation where only a corrupted sample is at
hand. We expose a k-means like algorithm with complexity O(n2 hkd), and we analyze
the approximation performance of such an empirical output. Theorem 24 shows that,
with high probability,
√

P d2Pn ,h,k (u) − d2P,h,k (u) ≤ CP,h

3

k (log(n)) 2
√
.
n

Combining this estimation result with the approximation results between k-PDTM and
d0

DTM mentioned above suggest that an optimal choice for k is k = n d0 +4 , whenever M
has dimension d0 , resulting in a deviation between empirical k-PDTM and DTM of order
0
0
n−1/(d +4) . This has to be compared with the n−1/d approximation that the empirical
0
DTM achieves in such cases. In the case where n is large, this n−1/(d +4) approximation
suffices for topological inference. Thus, topological inference built on significantly less
points might provide almost similar guarantees than the DTM.

1.3

Organization of the paper

This paper is organized as follows. In Section 2, we recall some definitions for the DTM
that can be expressed as a power distance, and study the set of local means. Section 3 is
devoted to the k-PDTM, a k-power distance which approximates the DTM. We make
the link with two equivalent definitions for the k-PDTM, derive some stability results,
prove its proximity to the DTM highlighting its interest for topological inference. The
case of noisy point clouds is addressed in Section 4, where an algorithm to approximate
the k-PDTM comes up with theoretical guarantees.

2
2.1

Some background about the DTM
Notation and definitions for the DTM

In the paper, we denote by Rd = {x = (x1 , x2 , . . . , xd ) | ∀i ∈ [[1, d]], xi ∈ R} the
d-dimensional space equipped with the Euclidean norm k.k. For k ∈ N∗ and any
space A, A(k) stands for {t = (t1 , t2 , . . . , tk ) | ∀i ∈ [[1, k]], ti ∈ A}, where two elements
are identified whenever they are equal up to a permutation of the coordinates. Also,
S(0 , r) = {x ∈ Rd | kxk = r} denotes the Euclidean sphere of radius r, B(x, r) = {y ∈
Rd | kx − yk < r} the Euclidean ball centred at x, and for c ∈ R and v ∈ S(0 , 1 ),
H(v, c) denotes the half-space {x ∈ Rd | hx, vi > c}. Also, for any subset A of Rd , A
stands for its closure, A◦ for its interior, ∂A = A\A◦ its boundary and Ac = Rd \A its
complementary set in Rd .

3

In the following, P(Rd ) stands for the set of Borel probability distributions P ,
with support Supp(P) ⊂ Rd , and, for any P -integrable function f , P f (u) denotes the
expectation of f with respect to P . The following sets of distributions are of particular
interest: we denote by P K (Rd ) = P ∈ P(Rd ) | Supp(P) ⊂ B(0 , K ) for K > 0, and
P K,h (Rd ) is the set of P ∈ P K (Rd ) which put mass neither on the boundaries of
balls nor on the half-spaces of P -mass h. We also allow perturbations of measures in
P K,h (Rd ). A sub-Gaussian measure Q with variance V 2 > 0 is a measure Q ∈ P(Rd )
t2
such that Q(B(0 , t)c ) ≤ exp(− 2V
2 ) for all t > V . The set of such measures is denoted
(V )
by P (Rd ). As well we can define P (V ),h (Rd ). The set P (V ),h (Rd ) might be thought
of as perturbations of P K,h (Rd ). Indeed, if X = Y + Z, where X has distribution in
P K,h (Rd ) and Z is Gaussian with variance σ 2 , then Z has distribution in P (V ),h (Rd ),
with V = K + σ. All these sets of distributions are included in P2 (Rd ), that denotes the
set of distributions with finite second moment.
For all P ∈ P(Rd ) and n ∈ N∗ , Xn = {X1 , X2 , . . . , Xn } denotes a n-sample from
P ,Pmeaning that the Xi ’s are independent and sampled according to P . Also, Pn =
n
1
i=1 δXi denotes the empirical measure associated to P , where δx ∈ P(Rd ) is such
n
that δx ({x}) = 1. Then Pn (Rd ) is the set of P ∈ P(Rd ) uniform on a set of n ∈ N∗
points.
An alternative definition to Definition 1, for the distance to measure, might be stated
in terms of sub-measures. Let x ∈ Rd . We define Px,h (P ) as the set of distributions
Px,h = h1 Q, for Q a sub-measure of P coinciding with P on B(x, δP,h (x)), and such
that Q(Rd ) = h and Supp(Q) ⊂ B(x, δP,h (x)). Note that when P ∈ P K,h (Rd ), Px,h (P )
is reduced to a singleton {Px,h } with Px,h defined for all Borel sets B by Px,h (B) =
1
d
h P (B ∩ B(x, δP,h (x))). From [7, Proposition 3.3], it holds, for any x ∈ R and Px,h ∈
Px,h (P ),
d2P,h (x) = Px,h kx − uk2 = kx − m(Px,h )k2 + v(Px,h ),
(1)
with m(Px,h ) = Px,h u the mean of Px,h and v(Px,h ) = Px,h ku − m(Px,h )k2 its variance.
For convenience, we denote by M (Px,h ) = Px,h kuk2 the second moment of Px,h , so that
M (Px,h ) = km(Px,h )k2 + v(Px,h ). Whenever P is in P (V ) (Rd ), M satisfies the following
property.
Lemma 2.
Let P ∈ P (V ) (Rd ), then ∀ x ∈ Rd and h ∈ (0, 1], M (Px,h ) ≤

2V 2
h .

The proof of Lemma 2 is deferred to Section A.1.

2.2

From balls to half-spaces: structure of the local means set

In the previous part, we have seen that the DTM dP,h is built from sub-measures of P
supported on balls of P -mass h. Now, by making the center of a ball go to ∞ along a
direction v ∈ S(0 , 1 ) such that the ball keeps a fixed mass h, we obtain a sub-measure of
P supported on a half-space, as follows.
For v ∈ S(0 , 1 ), we denote by v∞ the infinite point associated to
S the direction v. It
can be seen as a limit point limλ→+∞ λv. Then, we denote Rd = Rd {v∞ | v ∈ S(0 , 1 )}.
Note that we can equip Rd with the metric dRd defined by dRd (x, y) = kφ(x) − φ(y)k,
with φ(x) = √ x 2 when x ∈ Rd and φ(v∞ ) = v for all v ∈ S(0 , 1 ). Also, for this
1+kxk

metric, a sequence (xn )n∈N of Rd converges to v∞ if and only if limn→+∞ kxn k = +∞
w∞
and limn→+∞ kxxnn k = v with the convention kw
= w for all w ∈ S(0 , 1 ).
∞k
Let v ∈ S(0 , 1 ), set cP,h (v) = sup{c ∈ R | P ({x ∈ Rd | hx, vi > c}) > h}. Then,
H(v, cP,h (v)) corresponds to the largest (for the inclusion order) half-space directed by v
with P -mass at most h, which contains all the λv’s for λ large enough.
4

Lemma 3.
Let v ∈ S(0 , 1 ) and P ∈ P(Rd ). Assume that P (∂H(v, cP,h (v))) = 0 . If xn = nv for all
n ∈ N, then for P -almost all y ∈ Rd , we have:
lim

n→+∞

If (xn )n∈N is a sequence of
holds up to a subsequence.

1B(xn ,δP,h (xn )) (y) = 1H(v,cP,h (v)) (y).

Rd such that limn→+∞ dRd (xn , v∞ ) = 0 , then, the result

The proof of Lemma 3 is given in the Appendix, Section A.2. For all P ∈ P2 (Rd ),
we can generalize the definition of Px,h (P ), Px,h , m(Px,h ), v(Px,h ) and M (Px,h ) to
the elements x = v∞ ∈ Rd \Rd for all v ∈ S(0 , 1 ). Note that when P ∈ P K,h (Rd ),
Pv∞ ,h (P ) is reduced to the singleton {Pv∞ ,h } with Pv∞ ,h equal to h1 P (B ∩ H(v, cP,h (v)))
for all Borel set B. Intuitively, he distributions Pv∞ ,h behave like extreme points
of {Px,h | x ∈ Rd }. This intuition is formalized by the following Lemma. Denote
Mh (P ) = m(Px,h ) | x ∈ Rd .
Lemma 4.
T
Let P ∈ P2 (Rd ), the set Conv(Mh (P)) is equal to v∈S(0 ,1 ) H c (v, hm(Pv∞ ,h ), vi).
A straightforward consequence of Lemma 4 is the following Lemma 5.
Lemma 5.
Let P ∈ P2 (Rd ), then
∀ 0 < h < h0 ≤ 1, Conv (Mh 0 (P)) ⊂ Conv (Mh (P)) .
The proofs of Lemmas 4 and 5 are to be found in Section A.3 and A.4. A key property
of the local means sets Mh (P ) is convexity. This will be of particular interest in Section
3.1. We begin with the finite-sample case.
Lemma 6.
Let Pn ∈ Pn (Rd ) such that Supp(Pn ) is a set of n points in general position, as described
in [3, Section 3.1.4], meaning that any subset of Supp(Pn ) with size at most d + 1 is a
set of affinely independent points, set q ∈ [[1, n]]. Then, the set M nq (Pn ) is convex.
Proof
[Proof of lemma 6] Let


1
M̂h (Pn ) = x̄ =

q

X
p∈NNq,Xn (x)



p | x ∈ Rd , NNq,Xn (x) ∈ N N q,Xn (x) ,


with N N q,Xn (x) the collection of all sets of q-nearest neighbors associated to x. Note
that different x̄ may be associated to the same x, and also note that M̂h (Pn ) ⊂ Mh (Pn ).
Moreover, Conv(Mh (Pn )) = Conv(M̂h (Pn )) since any m(Pn x,h ), for Pn x,h ∈ Px,h (Pn ),
can be expressed as a convex combination of the x̄’s.
Then, Rd breaks down into a finite number of weighted Voronoï cells CPn ,h (x̄) =
2
{zP∈ Rd | kz − x̄k2 + ω̂ 2 (x̄) ≤ kz − ȳk2 + ω̂ 2 (ȳ), ∀ȳ ∈ M̂h (Pn )},
P with ω̂ (x̄) =
1
1
2
p∈NNq,X (x) kp − x̄k the weight associated to any point x̄ = q
p∈NNq,X (x) p in
q
n

n

M̂h (Pn ). According to [3, Theorem 4.3], the weighted Delaunay triangulation partitions
the convex hull of any finite set of weighted points X in general position by d-dimensional
simplices with vertices in X, provided that the associated weighted Voronoï cells of all
the points in X are non empty. By duality, (also see [3, Lemma 4.5]) these vertices are
associated to weighted Voronoï cells that have non-empty common intersection. Thus,
5

Pd
any θ ∈ Conv(Mh (Pn )) satisfies θ = i=0 λi x̄i for some x̄i ’s in M̂h (Pn ) and some non
Pd
∗
negative λi ’s such that i=0 λi = 1. Also,
 there exists some x in the intersection of the
d + 1 weighted Voronoï cells, CPn ,h (x̄i ) i∈[[0,d]] .
Pd
P
P
Set Pn x∗ ,h := i=0 λi Pi , with Pi = 1q p∈NNi (x ∗ ) δ{p} when x̄i = 1q p∈NNi (x ∗ ) p.
q,

Xn

q,

Xn

Then, Pn x∗ ,h is a probability measure such that hPn x∗ ,h (h = nq ) coincides with Pn
on B(x, δPn ,h (x)) and is supported on B(x, δPn ,h (x)). Thus it belongs to Px∗ ,h (Pn ).
Moreover, its mean m(Pn x∗ ,h ) = θ. Thus, θ ∈ Mh (Pn ). 
If P ∈ P K (Rd ), convexity of Mh (P ) might be deduced from the above Lemma 6
using the convergence of the empirical distribution Pn towards P in a probabilistic sense.
This is summarized by the following Lemma.
Lemma 7.
Let P ∈ P K (Rd ) and θ ∈ Conv(Mh (P)). There exists sequences qn ∈ N, αn → 0,
Pn ∈ Pn (Rd ) with the points in Supp(Pn ) in general position, and yn ∈ Conv(M qnn (Pn ))
such that
i)

qn
n

→ h,

ii) kyn − θk ≤ αn ,
iii) supx∈Rd km(Pnx, qnn ) − m(Px,h )k ≤ αn .
Lemma 7 follows from probabilistic arguments when Xn is sampled at random. Its
proof can be found in Section A.5. Equipped with Lemma 7, we can prove the convexity
of Mh (P ).
Proposition 8.
If P ∈ P K (Rd ) for K > 0 is such that P (∂H(v, c)) = 0 and P (∂B(x, r)) = 0 for all
v ∈ S(0 , 1 ), x ∈ Rd , c ∈ R, r ≥ 0, then for all h ∈ (0, 1], Mh (P ) is convex.
Proof
[Proof of Proposition 8] Let θ ∈ Conv(Mh (P)), Pn , qn , αn , yn as in Lemma 7 and for
short let hn = qnn .
Since M(Pn , hn ) is convex, there is a sequence (xn )n≥N in Rd such that yn =
m(Pn xn ,hn ) converges to θ. If (xn )n≥N is bounded, then up to a subsequence we have
xn → x, for some x ∈ Rd . If not, considering kxxnn k , up to a subsequence we get xn → v∞ .

In any case xn → x, for x ∈ Rd . Combining Lemma 7 and Lemma 3 yields θ = m(Px,h ).
Thus, θ ∈ Mh (P ). 

2.3

The DTM defined as a power distance

A power distance indexed on a set I is the square root of a power function fτ,ω defined
on Rd from a family of centers τ = (τi )i∈I and weights ω = (ωi )i∈I by fτ,ω : x 7→
inf i∈I kx − τi k2 + ωi 2 . A k-power distance is a power distance indexed on a finite set
of cardinal |I| = k.
In [7, Proposition 3.3], the authors point out that Px,h kx − uk2 ≤ Qkx − uk2 for
all Q ∈ P(Rd ) such that hQ is a sub-measure of P . This remark, together with (1),
provides an expression for the DTM as a power distance.
Proposition 9 ([7, Proposition 3.3]).
If P ∈ P2 (Rd ), then for all x ∈ Rd , we have:
d2P,h (x) = inf

inf

y∈Rd Py,h ∈Py,h (P)

kx − m(Py,h )k2 + v(Py,h ),

and the infimum is attained at y = x and any measure Px,h ∈ Px,h (P ).
6

As noted in Mérigot et al [10], this expression holds for the empirical DTM dPn ,h . In
this case, m(Pn,x,h ) corresponds to the
Pbarycentre of the q = nh nearest-neighbors of x
in Xn , NNq,Xn (x), and v(Pn,y,h ) = 1q p∈NNq,X (x) kx − pk2 , at least for points x whose
n
set of q nearest neighbors is uniquely defined.

2.4

Semiconcavity and DTM

In the following, we will often use the following lemma connected to the property of
concavity of the function x 7→ d2P,h (x) − kxk2 .
Lemma 10 ([7, Proposition 3.6]).
If P ∈ P(Rd ), then for all x, y ∈ Rd and Px,h ∈ Px,h (P ),
d2P,h (y) − kyk2 ≤ d2P,h (x) − kxk2 − 2 hy − x, m(Px,h )i,
with equality if and only if Px,h ∈ Py,h (P ).

3

The k-PDTM: a coreset for the DTM

In Proposition 9, we have written the DTM as a power distance. This remark has already
been exploited in [10] and [6], where the DTM has been approximated by n-power
distances. In this paper, we propose to keep only k centers.
Definition 11.
For any P ∈ P2 (Rd ), we define Opt(P, h, k) by:


(k)
Opt(P, h, k) = arg min P min ku − m(Pti ,h )k2 + v(Pti ,h ) | t = (t1 , t2 , . . . tk ) ∈ Rd
.
i∈[[1,k]]

A closely related notion to Definition 11 is the following weighted Voronoï measures.
Definition 12.
(k)
A set of weighted Voronoï
measures associated to a distribution P ∈ P2 (Rd ), t ∈ Rd

and h ∈ (0, 1] is a set P̃t1 ,h , P̃t2 ,h , . . . P̃tk ,h of k ∈ N∗ positive sub-measures of P such
Pk
that i=1 P̃ti = P and
∀x ∈ Supp(P̃ti ,h ), kx − m(Pti ,h )k2 + v(Pti ,h ) ≤ kx − m(Ptj ,h )k2 + v(Ptj ,h ), ∀j ∈ [[1 , k]].
We denote by m̃(P̃ti ,h ) =
0 when P̃ti ,h (Rd ) = 0.

P̃ti ,h u
P̃ti ,h (Rd )

the expectation of P̃ti ,h , with the convention m̃(P̃ti ,h ) =

Note that a set of weighted Voronoï measures can always be assigned to any P ∈
(k)
P2 (Rd ) and t ∈ Rd , it suffices to split Rd in weighted Voronoï cells associated to the
centers (m(Pti ,h ))i∈[[1,k]] and weights (v(Pti ,h ))i∈[[1,k]] , see [3, Section 4.4.2], and split the
remaining mass on the border of the cells in a measurable arbitrary way.
Theorem 13.
For all h ∈ (0, 1], k ∈ N∗ and P ∈ P K (Rd ) for some K > 0, such that P (∂H(v, cP,h (v))) =
0 for all v ∈ S(0 , 1 ), the set Opt(P, h, k) is not empty. Moreover, there is some
s ∈ Opt(P, h, k) ∩ B(0, K)(k) such that si = m̃(P̃si ,h ) for all i ∈ [[1, k]].

7

Proof

(k)
[Sketch of proof] For s ∈ Rd , set fs : x ∈ Rd 7→ mini∈[[1,k]] kx − m(Psi ,h )k2 + v(Psi ,h ) .
Then, Lemma 3 and the dominated convergence theorem yield inf t∈Rd P ft (u) = inf t∈Rd P ft (u).
Let (tn )n∈N be a sequence in Rd such that P ftn (u) ≤ inf t∈Rd P ft (u)+ n1 , and denote

by m∗ the limit of a converging subsequence of m̃(P̃tn,1 ,h ), m̃(P̃tn,2 ,h ), . . . , m̃(P̃tn,k ,h ) n∈N
in the compact space B(0, K)(k) . Then, Lemma 10 and (1) yield P fm∗ (u) = inf t∈Rd P ft (u).
Set si = m̃(P̃m∗i ,h ) for all i ∈ [[1, k]], then m̃(P̃si ,h ) = si and P fm∗ (u) = P fs (u). 
(k)

The detailed proof of Theorem 13 is given in Section B.1. Note that the distributions
in P K,h are in the scope of Theorem 13.

3.1

Two equivalent definitions for the k-PDTM

Definition 14.
Let P ∈ P2 (Rd ), the k-power distance to a measure (k-PDTM) dP,h,k is defined for
any s ∈ Opt(P, h, k) by:
d2P,h,k (x) = min kx − m(Psi ,h )k2 + v(Psi ,h ).
i∈[[1 ,k]]

An -approximation of the k-PDTM, denoted by an d2P,h,k, is a function defined by
the previous expression but for some s ∈ Rd

(k)

satisfying

P min ku − m(Psi ,h )k2 + v(Psi ,h ) ≤ inf P min ku − m(Pti ,h )k2 + v(Pti ,h ) + .
t∈Rd

(k)

i∈[[1,k]]

i∈[[1,k]]

Theorem 13 states that the k-PDTM is well defined when P ∈ P K (Rd ) and satisfies
P (∂HP,h (v, cP,h (v))) = 0 for all v ∈ S(0 , 1 ). Nonetheless, whenever Opt(P, h, k) is not
a singleton, the k-PDTM is not unique. Note that for all x ∈ Rd , dP,h,k (x) ≥ dP,h (x).
Definition 15.
The set OPT(P, h, k) is defined by:


(k)
2
2
OPT(P, h, k) = arg min P min ku − τi k + ωP,h (τi ) | τ = (τ1 , τ2 , . . . τk ) ∈ Rd
,
i∈[[1 ,k]]

n
o
with ωP,h (τ ) = inf ω > 0 | ∀x ∈ Rd , kx − τ k2 + ω 2 ≥ d2P,h (x) for τ ∈ Rd , that is:
2
ωP,h
(τ ) = sup d2P,h (x) − kx − τ k2 .

(2)

x∈Rd

The following Lemma shows that OPT(P, h, k) is included in Conv(Mh (P))(k) .
Lemma 16.
Let P ∈ P K (Rd ) ∪ P (V ) (Rd ). Then θ ∈ Conv(Mh (P)) if and only if ωP,h (θ) < +∞.
Proof
[Proof of Lemma 16] According to Proposition 9, for all x ∈ Rd , d2P,h (x) − kx − θk2 may
be written as

inf
inf
km(Py,h )k2 + v(Py,h ) − kθk2 + 2hx, θ − m(Py,h )i ,
y∈Rd Py,h ∈Py,h (P )

which is lower-bounded by

inf
inf
km(Py,h )k2 + v(Py,h ) − kθk2 +
y∈Rd Py,h ∈Py,h (P )

8

inf

τ ∈Mh (P )

{2hx, θ − τ i} .

Assume θ ∈
/ Conv(Mh (P)). According to Lemma 4, Conv(Mh (P)) is a convex and
compact subset of Rd . The Hahn-Banach separation theorem thus provides some vector
v ∈ Rd and C > 0 such that ∀τ ∈ Mh (P ), hθ − τ, vi < C. Setting xn = −nv for n ∈ N∗
yields limn→+∞ inf τ ∈Mh (P ) hxn , θ − τ i = +∞. Thus, supx∈Rd d2P,h (x) − kx − θk2 = +∞.
Pd
Now, let θ ∈ Conv(Mh (P)), we can write θ = i=0 λi m(Pi ) for Pi = Pxi ,h with the
xi ’s in Rd . We have:
sup d2P,h (x) − kx − θk2 = sup

x∈Rd

d
X

x∈Rd i=0

≤ sup

d
X

x∈Rd i=0

= sup

d
X

x∈Rd i=0

=

d
X

λi (d2P,h (x) − kx − θk2 )
λi kx − m(Pi )k2 + v(Pi ) − kx − θk2



λi v(Pi ) + 2hx, θ − m(Pi )i + km(Pi )k2 − kθk2




λi v(Pi ) + km(Pi )k2 − kθk2 ,

i=0

according to Proposition 9. Thus, we get that
2
ωP,h
(θ) + kθk2 ≤

d
X

λi (v(Pi ) + km(Pi )k2 ) ≤ sup

x∈Rd

i=0


v(Px,h ) + km(Px,h )k2 .

(3)

2
Lemma 2 yields ωP,h
(θ) < +∞. 

Theorem 17.
If P ∈ P K,h (Rd ) for some h ∈ (0, 1] and K > 0, or P ∈ Pn (Rd ) such that Supp(Pn )
is a set of n points in general position as described in Lemma 6, for some h = nq with
q ∈ [[1, n]], then, any function dP,h,k satisfies for some θ ∈ OPT(P, h, k):
2
d2P,h,k (x) = min kx − θi k2 + ωP,h
(θi ), ∀x ∈ Rd .
i∈[[1 ,k]]

Conversely, for all θ ∈ OPT(P, h, k), x 7→
PDTM.

q

2 (θ ) is a kmini∈[[1,k]] kx − θi k2 + ωP,h
i

Proof
(k)
[Proof of Theorem 17] For all τ ∈ Rd , for all i ∈ [[1, k]], if τi ∈
/ Conv(Mh (P)), then
according to Lemma 16, ωP,h (τi ) = +∞. In this case, τ ∈
/ OPT(P, h, k).
Thus, for all τ ∈ OPT(P, h, k), for all i, τi ∈ Conv(Mh (P)). According to Proposition 8
and Lemma 6, Mh (P ) is convex. Thus,


2
2
(k)
OPT(P, h, k) = arg min P min ku − τi k + ωP,h (τi ) | τ = (τ1 , τ2 , . . . τk ) ∈ Mh (P)
.
i∈[[1 ,k]]

2
Moreover, according to Proposition 9, and (2), ωP,h
(m(Pt,h )) = v(Pt,h ), for all t ∈ Rd .
Thus,
2
inf P min kx − m(Pti ,h )k2 + v(Pti ,h ) = inf P min ku − τi k2 + ωP,h
(τi ).

t∈Rd

(k)

τ ∈ Rd

(k)

i∈[[1,k]]

i∈[[1,k]]


Therefore, Theorem 17 allows to consider the function dP,h,k as the square root of
a minimizer of the L1 (P ) norm f 7→ P |f − d2P,h |(u) among all the k-power functions f
which graph lies above the graph of the function d2P,h .

9

3.2

Proximity to the DTM

Here we show that the k-PDTM approximates the DTM in the following sense.
Proposition 18.
Let P ∈ P K (Rd ) for K > 0 and let M ⊂ B(0 , K ) be such that P (M ) = 1. Let fM (ε)
denote the ε covering number of M . Then we have
−1
−1
0 ≤ P d2P,h,k (u)−d2P,h (u) ≤ 2fM
(k)ζP,h (fM
(k)),

with

−1
fM
(k) = inf {ε > 0 |

fM (ε) ≤ k} ,

where ζP,h is the continuity modulus of x 7→ m(Px,h ), that is
ζP,h () =

{|m(Px,h ) − m(Py,h )|} .

sup
x,y∈M,kx−yk≤ε

Proof
[Proof of Proposition 18] The first inequality comes from Proposition 9.
We then focus on the second bound. By definition of dP,h,k , for all x ∈ Rd and
(k)
t = (t1 , t2 , . . . , tk ) ∈ Rd we have: P d2P,h,k (x) ≤ P mini∈[[1 ,k]] ku − m(Pti ,h )k2 + v(Pti ,h ).
Thus,
P d2P,h,k (u) − d2P,h (u) ≤ P min ku − m(Pti ,h )k2 + v(Pti ,h ) − d2P,h (u)
i∈[[1,k]]

= P min (d2P,h (ti ) − kti k2 ) − (d2P,h (u) − kuk2 ) + hu − ti , −2m(Pti ,h )i
i∈[[1,k]]

≤ P min 2hu − ti , m(Pu,h ) − m(Pti ,h )i
i∈[[1,k]]

≤ 2P min ku − ti kkm(Pu,h ) − m(Pti ,h )k,
i∈[[1,k]]

where we used (1), Lemma 10 and Cauchy-Schwarz inequality. Now choose t1 , . . . , tk as
−1
a fM
(k)-covering of M . The result follows. 
−1
When P is roughly uniform on its support, the quantities fM
(k) and ζP,h mostly
depend on the dimension and radius of M . We focus on two cases in which Proposition
18 may be adapted. First, the case where the distribution P has an ambient-dimensional
support is investigated.

Corollary 19.
Assume that P have a density f satisfying 0 < fmin ≤ f ≤ fmax . Then
0 ≤ P d2P,h,k (u) − d2P,h (u) ≤ Cfmax ,K,d,h k −2 /d .
The proof of Corollary 19 is given in Section B.2. Note that no assumptions on the
geometric regularity of M is required for Corollary 19 to hold. In the case where M has
a lower-dimensional structure, more regularity is required, as stated by the following
corollary.
Corollary 20.
Suppose that P is supported on a compact d0 -dimensional C 2 -submanifold of B(0 , K ),
denoted by N . Assume that N has positive reach ρ, and that P has a density 0 < fmin ≤
f ≤ fmax with respect to the volume measure on N . Moreover, suppose that P satisfies,
for all x ∈ N and positive r,
0

P (B(x, r)) ≥ cfmin r d ∧ 1 .

(4)
0

Then, for k ≥ cN,fmin and h ≤ cN,fmin , we have 0 ≤ P d2P,h,k (u)−d2P,h (u) ≤ CN ,fmin ,fmax k −2 /d .
10

Note that (4), also known as (cfmin , d0 )-standard assumption, is usual in set estimation
(see, e.g., [8]). In the submanifold case, it may be thought of as a condition preventing
the boundary from being arbitrarily narrow. This assumption is satisfied for instance
in the case where ∂N is empty or is a C 2 d0 − 1-dimensional submanifold (see, e.g., [2,
Corollary 1]). An important feature of Corollary 20 is that this approximation bound
does not depend on the ambient dimension. The proof of Corollary 20 may be found in
Section B.3.

3.3

Wasserstein stability for the k-PDTM

Next we assess that our k-PDTM shares with the DTM the key property of robustness
to noise.
Proposition 21.
Let P ∈ P K (Rd ) for some K > 0, Q ∈ P2 (Rd ), and  > 0. Set d2Q,h,k, an approximation of the k-PDTM of Q, then P d2Q,h,k, (u) − d2P,h (u) is bounded from
above by BP,Q,h,k, with
BP,Q,h,k, = +3kd2Q,h −d2P,h k∞,Supp(P) +Pd2P,h,k (u)−d2P,h (u)+2W1 (P, Q) sup km(Ps,h )k.
s∈Rd

Note that Lemma 2 gives a bound on m(Qs,h ) whenever Q is sub-Gaussian. Also,
upper-bounds for the deviation of the k-PDTM to the DTM associated to P have been
derived in the previous subsection.
Proof
n


o
[Sketch of proof] For x ∈ Supp(P), max 0, − d2Q,h,k − d2P,h (x) ≤ kd2P,h −d2Q,h k∞,Supp(P) .

Set fQ,p (x) = 2hx, m(Qp,h )i + v(Qp,h ) for p ∈ Rd , and let t ∈ Opt(Q, h, k). Then,
P − Q mini∈[[1,k]] fQ,ti (u) ≤ 2W1 (P, Q) supt∈Rd m(Qt,h ) and for s given by Theorem
13, that is s ∈ Opt(P, h, k) ∩ B(0, K)(k) such that si = m̃(P̃si ,h ) for all i ∈ [[1, k]],
P mini∈[[1,k]] fQ,si (u)−mini∈[[1,k]] fP,si (u) is bounded from above by kd2P,h −d2Q,h k∞,Supp(P)
. 
The details of the proof of Proposition 21 can be found in Section B.4.

3.4

Geometric inference with the k-PDTM

As detailed in [7, Section 4], under suitable assumptions, the sublevel sets of the distance
to measure are close enough to the sublevel sets of the distance to its support. Thus
they allow to infer the geometric structure of the support. As stated below, this is also
the case when replacing the distance to measure with the k-PDTM.
Proposition 22.
Let M be a compact set in B(0 , K ) such that P (M ) = 1. Moreover, assume that there
exists d0 such that, for every p ∈ M and r ≥ 0,
0

P (B(p, r)) ≥ C (P)r d ∧ 1 .

(5)

Let Q be a probability measure (thought of as a perturbation of P ), and let ∆2P denote
P d2Q,h,k,ε (u). Then, we have
sup |dQ,h,k,ε (x) − dM (x)| ≤ C(P )

x∈Rd

where W2 denotes the Wasserstein distance.
11

− d01+2

2
0

1

∆Pd +2 + W2 (P, Q)h− 2 ,

Proposition 22, whose proof can be found in Section B.5, ensures that the k-PDTM
achieves roughly the same performance as the distance to measure (see, e.g., [7, Corollary
4.8]) provided that d2Q,h,k,ε is small enough on the support M to be inferred. As will be
shown in the following Section, this will be the case if Q is an empirical measure drawn
close to the targeted support.

Approximation of the k-PDTM from point clouds

4

Let P ∈ P2 (Rd ), an approximation of the k-PDTM dP,h,k , is given by the empirical
k-PDTM dPn ,h,k . Note that when k = n, dPn ,h,n is equal to the q-witnessed distance.
Also, when h = 0 we recover the k-means method.

4.1

An algorithm for the empirical k-PDTM

The following algorithm is inspired by the Lloyds algorithm. We assume that the mass
q
parameter
Phq = n for some positive integer q. And for any t ∈ Rd , we use the notation
1
c(t) = q i=1 Xi (t), where Xi (t) is one of the i-th nearest neighbor of t in Rd . We
Pq
2
denote ω 2 (t) = 1q i=1 (Xi (t) − c(t)) , and C(t) the weighted Voronoï cell associated to
t. We use the notation |C(t)| for the cardinal of C(t) ∩ Xn .
Algorithm 1: Local minimum algorithm
Input : Xn a n-sample from P , q and k ;
# Initialization
Sample t1 , t2 ,. . . tk from Xn without replacement. ;
while t h e ti s vary make t h e f o l l o w i n g two s t e p s :
# Decomposition in weighted Voronoi cells .
f o r j in 1 . . n :
Add Xj to the C(ti ) (for i as small as possible) satisfying
kXj − c(ti )k2 + ω 2 (ti ) ≤ kXj − c(tl )k2 + ω 2 (tl ) ∀l 6= i ;
# Computation of the new centers and weights .
f o r i in 1P
..k:
ti = |C(t1i )| X∈C(ti ) X ;
Output : (t1 , t2 , . . . , tk )
The following proposition relies on the same arguments as in the proof of Theorem
13.
Proposition 23.
This algorithm converges to a local minimum of t 7→ Pn mini∈[[1,k]] kx − m(Pn ti ,h )k2 +
v(Pn ti ,h ).
The proof of Proposition 23 can be found in Section C.1.

4.2

Proximity between the k-PDTM and its empirical version

Theorem 24.
Let P be supported on M ⊂ B(0 , K ). Assume that we observe X1 , . . . , Xn such that
Xi = Yi + Zi , where Yi is an i.i.d n-sample from P and Zi is sub-Gaussian with variance
σ 2 , with σ ≤ K. Let Qn denote the empirical distribution associated with the Xi ’s. Then,
for any p > 0, with probability larger than 1 − 7n−p , we have
P (d2Qn ,h,k (u)

−

2
dQ,h,k
(u))

√ K 2 ((p + 1 ) log(n)) 23
Kσ
√
≤C k
+C √ .
h n
h
12

A proof of Theorem 24 is given in Section C.2. Theorem 24, combined with Proposition
21, allows to choose k in order to minimize P d2Qn ,h,k (u). Indeed, in the framework of
Corollaries 19 and 20 where the support has intrinsic dimension d0 , such a minimization
boils down to optimize a quantity of the form
√
3
2
C kK 2 ((p + 1) log(n)) 2
√
+ CP k − d0 .
h n
d0

d0

Hence the choice k ∼ n d0 +4 ensures that for n large enough, only n d0 +4 points are
sufficient to approximate well the sub-level sets of the distance to support. For surface
1
inference (d0 = 2), this amounts to compute the distance to n 3 points rather than n,
0
which might save some time. Note that when d is large, smaller choices of k, though
suboptimal for our bounds, would nonetheless give the right topology for large n’s. In
some sense, Theorem 24 advocates only an upper bound on k, above which no increase
of precision can be expected.

4.3

Some numerical illustration

As in [10], we sampled
n = 6000 points from the uniform measure on a sideways with
q
√
9
radius 2 and 8 convolved with a Gaussian N (0, σ 2 ) with σ = 0.45. We then plotted
in grey the r-sub-level set of the q-witnessed distance and in purple, the r-sub-level
set of an approximation of dPn ,q,k with r = 0.24 and q = 50 nearest-neighbors. The
approximation of dPn ,q,k is obtained after running our algorithm 10 times and keeping
the best (for the L1 (Pn ) loss) function obtained, each time after at most 10 iterations.
Choosing k = 100 points leads to a too sparse approximation of the sublevel sets of the

Figure 1: 6000-sample

Figure 2: k = 100

Figure 3: k = 300

q-witnessed distance. On the contrary, small holes which appeared in the r-sub-level set,
when k = 300, will disappear quickly when the radius r will get larger, before the two
holes get filled.
The authors are grateful to Pascal Massart, Frédéric Chazal and Marc Glisse for their
precious advice.

References
[1] Eddie Aamari and Clément Levrard. “Stability and Minimax Optimality of Tangential Delaunay Complexes for Manifold Reconstruction”. In: ArXiv e-prints,
1512.02857 (2015).
[2] Catherine Aaron and Alejandro Cholaquidis. “On boundary detection”. In: ArXiv
e-prints, 1603.08460 (2016).
[3] Jean-Daniel Boissonnat, Frédéric Chazal, and Mariette Yvinec. “Geometric and
Topological Inference”. In: Cambridge University Press (2017).

13

[4] Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. “Theory of classification:
a survey of some recent advances”. In: ESAIM. Probability and Statistics 9 (2005),
pp. 323–375.
[5] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities.
2013.
[6] Mickaël Buchet et al. “Efficient and robust persistent homology for measures”. In:
Computational Geometry 58 (2016), pp. 70–96.
[7] Frédéric Chazal, David Cohen-Steiner, and Quentin Mérigot. “Geometric Inference
for Probability Measures”. In: Foundations of Computational Mathematics 11.6
(2011), pp. 733–751.
[8] Frédéric Chazal et al. “Convergence Rates for Persistence Diagram estimation in
Topological Data Analysis”. In: Journal of Machine Learning Research 16 (2015),
pp. 3603–3635.
[9] Herbert Edelsbrunner. Weighted alpha-shapes. Tech. rep. UIUCDCS-R-92-1760.
Department of Computer Science, University of Illinois, 1992.
[10] Leonidas Guibas, Dmitriy Morozov, and Quentin Mérigot. “Witnessed k-distance”.
In: Discrete and Computational Geometry 49.1 (2013), pp. 22–45.
[11] Shahar Mendelson and Roman Vershynin. “Entropy and the combinatorial dimension”. In: Invent. Math. 152.1 (2003), pp. 37–55. issn: 0020-9910. doi: 10.1007/
s00222-002-0266-3. url: http://dx.doi.org/10.1007/s00222-002-0266-3.
[12] Quentin Mérigot. “Lower bounds for k-distance approximation”. In: International
Symposium on Computational Geometry (SoCG). 2013, 435––440.
[13] Jeff M. Phillips, Bei Wangy, and Yan Zheng. “Geometric Inference on Kernel
Density Estimates”. In: International Symposium on Computational Geometry
(SoCG). 2015.

14

Appendix
A
A.1

Proofs for Section 2
Proof of Lemma 2

Proof
Let P ∈ P (V ) (Rd ), x in Rd and Px,h a sub-measure of P , supported on B(x, δP,h (x)) (or
on H(v, cP,h (v)) if x = v∞ ∈ Rd \Rd ), coinciding with P on B(x, δP,h (x)), and such that
Px,h (Rd ) = h. We may write
1
P kuk2
h

1
≤
P kuk2 1kuk≤V + P kuk2 1kuk>V
h
P kuk2 1kuk>V
V2
≤
+
.
h
h

Px,h kuk2 ≤

Since P kuk2 1kuk>V ≤ NV 2 t2 1t>V ≤ NV 2 t2 = V 2 , where NV 2 denotes the distribution
of a Gaussian distribution with variance V 2 , the result of Lemma 2 follows. 

A.2

Proof of Lemma 3

Proof
Note that for any point x ∈ ∂H (v, cP,h (v)) ∩ S(0 , K ), x = w + c2P,h (v)v for some w
orthogonal to v. Moreover, kx − cP,h (v)vk2 = K 2 − c2P,h (v) and kx − xn k2 = (n −
cP,h (v))2 + K 2 − c2P,h (v) for xn = nv. Thus, we get that:
B (xn , n − cP,h (v)) ⊂ H (v, cP,h (v), )
and

 q

2 (v) + (n − c
2 .
H (v, cP,h (v)) ∩ Supp(P) ⊂ B xn , K 2 − cP,h
P,h (v))

In particular, since P (H (v, cP,h (v))) < h, B (x
− cP,h (v)) ⊂ B(xn , δP,h (x)) and
 n , nq


2 (v) + (n − c
2 ,
since P H (v, cP,h (v)) ≥ h, B(xn , δP,h (x)) ⊂ B xn , K 2 − cP,h
P,h (v))

with δP,h (x) the pseudo-distance defined in Section 2. Finally, for all y ∈ Rd , if
hy, vi = cP,h (v) −  for some  > 0, then ky − xn k2 = kyk2 + n2 − 2n(cP,h (v) − ),
which is superior to K 2 + (n − cP,h (v))2 − c2P,h (v) for n large enough. Thus, for all
n large enough, y ∈
/ B(xn , δP,h (xn )). If hy, vi = cP,h (v) +  for some  > 0, then
ky − xn k2 = kyk2 + (n − cP,h (v))2 − c2P,h (v) − 2n which is inferior to (n − cP,h (v))2 for
n large enough. Thus, for all n large enough, y ∈ B(xn , δP,h (xn )), which concludes the
first part of the Lemma.
Let (xn )n≥0 be a sequence in Rd such that limn→+∞ dRd (xn , v∞ ) = 0 , that is such
that limn→+∞ kxn k = +∞ and limn→+∞ kxxnn k = v. Then,
kxn k − K ≤ δP,h (xn ) ≤ kxn k + K.
Let y ∈ Rd . Then,
2

2



2

ky − xn k − δP,h (xn ) = kyk − 2 hxn , yi + O(kxn k) = kxn k

15

kyk2
−2
kxn k



xn
,y
kxn k




+ O(1) .



The notation yn = O(kxn k) means that kxynn k
is bounded. Thus, up to a subsen∈N
quence,
ky − xn k2 − δP,h (xn )2
lim
= 2c − 2hv, yi,
n→+∞
kxn k
for some c ∈ R. We deduce that, for all y ∈ Rd \∂H(v, c),

1B(xn ,δP,h (xn )) (y) → 1H(v,c) (y).
In particular, P (H(v, c)) ≤ h and P (H(v, c)) ≥ h. Therefore, for P -almost y, 1H(v,c) (y) =
1H(v,cP,h (v)) (y), the result then holds for c = cP,h (v). 

A.3

Proof of Lemma 4

Proof
Recall that a k-extreme point x of a convex set S is a point x which lies in the interior
of a k-dimensional convex set within S, but not a k + 1-dimensional convex set within S.
We will prove that the set of k-extreme points in Mh (P ) of Mh (P ) for k < d is equal to
{m(P
T x,h ) | x ∈ Rd \Rd }. In particular, this will yield that the set Conv(Mh (P)) is equal
to v∈S(0 ,1 ) H c (v, hm(Pv∞ ,h ), vi).
Let v ∈ S(0 , 1 ), then by definition the measure Pv∞ ,h is supported on H(v, cP,h (v)),
satisfies that hPv∞ ,h is a sub-measure of P and the measures hPv∞ ,h and P coincide on
H(v, cP,h (v)). Note that P (H(v, cP,h (v))) ≥ h and P (H(v, cP,h (v))) ≤ h.
We will denote C(Pv∞ ,h ) = hm(Pv∞ ,h ), vi, that is, C(Pv∞ ,h ) = Pv∞ ,h hu, vi.
Then, for all x ∈ Rd , we decompose any measure Px,h as P1 + P2 with P1 (B) =
Px,h (B ∩ H(v, cP,h (v))) and P2 (B) = Px,h (B ∩ Hc (v, cP,h (v))). Note that P1 is also a
sub-measure of Pv∞ ,h . Set P20 = Pv∞ ,h − P1 . Then, we have
Px,h hu, vi = P1 hu, vi + P2 hu, vi
= Pv∞ ,h hu, vi − P20 hu, vi + P2 hu, vi

= Pv∞ ,h hu, vi − hm(P20 ), viP20 (Rd ) + hm(P2 ), viP2 (Rd )
= C̄(Pv∞ ,h ) − P20 hu, vi + P2 hu, vi
≤ C̄(Pv∞ ,h ) − cP,h (v)P20 (Rd ) + cP,h (v)P2 (Rd )
= C̄(Pv∞ ,h ),

since P2 is supported on Hc (v, cP,h (v)) and P20 is supported on H(v, cP,h (v)) and P2 (Rd ) =
P20 (Rd ).
Thus, for all x ∈ Rd , hm(Px,h ), vi ≤ C̄(Pv∞ ,h ) = hm(Pv∞ ,h ), vi. It means that
m(Pv∞ ,h ) is not included in a d-dimensional simplex within Conv(Mh (P)). It is thus a kextreme point of Conv(Mh (P)) for some k < d. Moreover, the hyperplane ∂H(v, cP,h (v))
separates m(Pv∞ ,h ) from Conv(Mh (P)).
If x is extreme, then there is some vector v and some constant Cx such that
hm(Px,h ), vi = Cx and such that for all y, hm(Py,h ), vi ≤ Cx . We aim at proving
that x is in Rd \Rd . Similarly, we get
Cx = Px,h hu, vi
= P1 hu, vi + P2 hu, vi
= Pv∞ ,h hu, vi − P20 hu, vi + P2 hu, vi
≤ Cx − P20 hu, vi + P2 hu, vi

≤ Cx − cP,h (v)P20 (Rd ) + cP,h (v)P2 (Rd )

= Cx .
16

Thus the inequalities are equalities and we get that for P2 -almost all y, hy, vi = cP,h (v)
and for P20 -almost all y, hy, vi = cP,h (v). Thus, Px,h belongs to Pv∞ ,h (P ). Note that,
since there is equality, Cx = hm(Pv∞ ,h ), vi = hm(Px,h ), vi.
Note that according to the Krein-Milman theorem, we get that Conv(Mh (P)) =
Conv({m(Pv∞ ,h ) | v ∈ S(0 , 1 )}).
We proved that for all y ∈ Rd , for all v ∈ S(0 , 1 ),
hm(P−v∞ ,h ), vi ≤ hm(Py,h ), vi ≤ hm(Pv∞ ,h ), vi.
T
Therefore, the convex set Conv(Mh (P)) is included in v∈S(0 ,1 ) H c (v, hm(Pv∞ ,h ), vi).
With the Hahn-Banach separation theorem, we prove that for any θ ∈
/ Conv(Mh (P)),
there is some vector v such that for all θ0 ∈ Conv(Mh (P)), hθ0 , vi ≤ C < hθ, vi. In
particular, we get that hθ, vi > hm(Pv∞ ,h ), vi, meaning that θ does not belong to
H(v, hm(Pv∞ ,h ), vi). 

A.4

Proof of Lemma 5

Proof
Thanks to Lemma 4, we have:
Conv(Mh (P)) =

\

Hc (v, hm(Pv∞ ,h ), vi).

v∈S(0 ,1 )

Let 0 < h0 ≤ h ≤ 1, in order to prove that the map h 7→ Conv(Mh (P)) is non-increasing,
it is sufficient to prove that
Hc (v, hm(Pv∞ ,h 0 ), vi) ⊃ Hc (v, hm(Pv∞ ,h ), vi).
Thus, it is sufficient to prove that
hm(Pv∞ ,h0 ), vi ≥ hm(Pv∞ ,h ), vi.
c

Set P0 the sub-measure of P supported on H (v, cP,h (v))\Hc (v, cP,h 0 (v)) such that
hPv∞ ,h = h0 Pv∞ ,h0 + (h − h0 )P0 . Then, we have:
hm(Pv∞ ,h ), vi =

h0
h0 − h
hm(Pv∞ ,h0 ), vi +
hm(P0 ), vi.
h
h

The results comes from the fact that hm(P0 ), vi ≤ cP,h0 (v) ≤ hm(Pv∞ ,h0 ), vi. 

A.5

Proof of Lemma 7

The proof of Lemma 7 is based on the following concentration argument, that allows
to connect empirical sub-measures with sub-measures for Pn . For sake of concision the
statement also encompasses sub-Gaussian measures.
Lemma 25.
Suppose that Q ∈ P (V ) (Rd ). Then, for every p > 0, with probability larger than 1 − 8n−p ,

17

we have,
sup |(Qn − Q)|1B(x,r) (y)dy ≤ C

r

x,r

d+1
+
n

r

2p log(n)
n

r
d+1
2p log(n)
sup |(Qn − Q)|1hy,vi≤t (y)dy ≤ C
+
n
n
v,t
√ (p + 1) log(n)
√
sup k(Qn − Q)y 1B(x,r) (y)dyk ≤ CV d
n
x,r
√ (p + 1) log(n)
√
sup k(Qn − Q)y 1hv,yi≤t dyk ≤ CV d
n
v,t
√ (p + 1) log(n) 32
√
sup (Qn − Q)kyk2 1B(x,r) (y)dy ≤ CV 2 d
n
x,r
3
√
(p + 1) log(n) 2
2
2
√
sup (Qn − Q)kyk 1hv,yi≤t dy ≤ CV
d
,
n
v,t
r

where C > 0 denotes a universal constant.
The proof of Lemma 25 is postponed to the following Section A.6. A significant part
2
of the proof of Lemma 7 is based on the characterization of Conv(Mh (P)) through ωP,h
2
stated by Lemma 16, where we recall that ωP,h (τ ) is defined in Definition 11 by
2
ωP,h
(τ ) = sup d2P,h (x) − kx − τ k2 .
x∈Rd

Lemma 26.
Let C denote a convex set, θ ∈ Rd , and ∆ = d(θ, C ). There exists v ∈ Rd with kvk = 1
such that, for all τ in C,
hv, θ − τ i ≥ ∆.
Proof
[Proof of Lemma 26] Denote by π the projection onto C, and t = π(θ). Then, let x =
We may write

θ−t
∆ .

hx, θ − τ i = hx, θ − ti + hx, t − τ i
1
= ∆ + hθ − t, t − τ i .
∆
Since, for all τ in C, hθ − t, τ − ti ≤ 0, the result follows. 
We are now in position to prove Lemma 7.
Proof
[Proof of Lemma 7] Let P in P K (Rd ) which puts no mass on hyperplanes nor on spheres,
and θ ∈ Conv(Mh (P)). If we choose p large enough (for instance p = 10), a union bound
ensures that the inequalities of Lemma 25 are satisfied for all n ∈ N with probability
> 0. Since P puts no mass on hyperplanes, the probability that n points are not in
general position is 0. Hence there exists an empirical distribution Pn , in general position,
satisfying the inequalities of Lemma 25 for all n. In particular, for such a distribution
Pn and (y, r) such that P (B(y, r)) = h, we have
Pn u1B(y,r) (u) Pn u1B(y,r) (u)
Kαn
−
≤
,
P (B(y, r))
Pn (B(y, r))
h
P u1B(y,r) (u) Pn u1B(y,r) (u)
Kαn
−
≤
,
P (B(y, r))
P (B(y, r))
h
|(Pn − P )B(y, r)| ≤ αn ,
18

for αn → 0. Note that the same holds for means on half-spaces. Now let x ∈ Rd ,
d2P,h (x) − kx − θk2 = Px,h kx − uk2 − kx − θk2
= inf Py,h kx − uk2 − kx − θk2
y∈R

d

≥ inf km(Py,h )k2 + v(Py,h ) − kθk2 + inf 2hx, θ − m(Py,h )i
y∈R

y∈R

d

d

≥ −kθk2 + inf 2hx, θ − m(Py,h )i.
y∈R

d

Thus, we may write

Pn u1By,r (u)
inf 2hx, θ − m(Py,h )i ≥ min
,
inf
2 x, θ −
d
Pn (B(y, r))
y,r|Pn (B(y,r))∈[h−αn ,h+αn ]
y∈R


Pn u1H(v,t)(u)
4Kαn kxk
inf
2 x, θ −
−
,
Pn (H(v, t))
h
v,t|Pn (H(v,t))∈[h−αn ,h+αn ]
4Kαn kxk
.
= S
inf
2 hx, θ − τ i −
h
τ∈
Ms (Pn )




s∈[h−αn ,h+αn ]



Now, if d θ, Conv

S

s∈[h−αn ,h+αn ]

26, we can choose x in


Ms (Pn ) = ∆ >

Rd such that, for all τ ∈ Conv


x
,θ − τ
kxk


−

2Kαn

, then according to Lemma

s∈[h−αn ,h+αn ] Ms (Pn ) ,

Sh

2Kαn
> 0.
h

2
In this case, we immediately get ωP,h
(θ) = supx∈Rd d2P,h (x) − kx − θk2 = +∞. According
to Lemma 16, this contradicts ω ∈ Conv(Mh (P)).
Set hn = qnn for qn ∈ [[1, n]] such that h − αn ≥ hn ≥ h − αn − n1 . Note that for n
large enough, h − αn − n1 > 0, thus hn is well defined. Then, according to Lemma 5 and
6,




[
[
Conv 
Ms (Pn ) ⊂ Conv 
Ms (Pn ) = M qnn (Pn ).
s∈[h−αn ,h+αn ]

s∈[hn ,1 ]

Thus, we can build a sequence (yn )n≥N for some N ∈ N such that yn ∈ Mhn (Pn ) and
n
kθ − yn k ≤ 2 Kα
h . Hence the result of Lemma 7. 

A.6

Proof of Lemma 25

Proof
[Proof of Lemma 25]
The first inequality is a direct application of Theorem 3.2 in [4], since the Vapnik
dimension of balls in Rd is d + 1. The same argument holds
p for the second inequality.
Now turn to the third one. Let λ = p log(n), t = 4V 2 (log(n) + λ). Since Q ∈
P (V ) (Rd ), we have that
n
o
t2
P max kXi k ≥ t ≤ ne− 2V 2 ≤ n−2p+1 .
i

19

We may write
sup k(Qn − Q)y 1B(x,r) (y)dyk = sup
x,r

x,r

n

1X
Xi 1B(x,r) (Xi ) − E(X 1B(x,r) (X))
n i=1
n

≤ sup
x,r

1X
Xi 1B(x,r) (Xi )1kXi k≤t − E(X 1B(x,r) (X)1kXk≤t )
n i=1
+ E(kXk1kXk>t ) + sup
x,r

n

1X
kXi k1kXi k>t .
n i=1

On one hand,
E(kXk1kXk>t ) ≤

p

p
E(kXk2 ) P(kXk ≥ t)
t2

≤ 2V e− 4V 2
≤ 2V n−(p+1) .
On the other hand, with probability larger than 1 − n−2p+1 , it holds
n

sup
x,r

1X
kXi k1kXi k>t = 0.
n i=1

Now denote by fx,r,v the function y 1B(x,r) (y), v

1kyk≤t , for v ∈ B(0 , 1 ), so that

n

sup
x,r

1X
Xi 1B(x,r) (Xi )1kXi k≤t − E(X 1B(x,r) (X)1kXk≤t ) = sup |(Qn − Q)fx,r,v |.
n i=1
x,r,v

A straightforward application of MacDiarmid’s inequality (see, e.g., [5, Theorem 6.2])
entails
r !
2λ
P sup |(Qn − Q)fx,r,v | ≥ E sup |(Qn − Q)fx,r,v | + t
≤ e−λ = n−p .
n
x,r,v
x,r,v
It remains to bound E supx,r,v |(Qn − Q)fx,r,v |. A symmetrization inequality (see, e.g.,
[5, Lemma 11.4]) leads to
E sup |(Qn − Q)fx,r,v | ≤
x,r,v

n
X
2t
EX1:n Eε sup
εi fx,r,v (Xi )/t,
n
x,r,v
i=1

where the εi ’s are i.i.d. Rademacher random variable, and EY denotes expectation with
respect to the random variable Y .
Now suppose that X1 , . . . , Xn is fixed. In order to apply Dudley’s entropy integral
we have to provide an upper bound on the metric entropy of F = {fx,r,v /t}x,r,v , for the
Pn
L2 (Pn ) distance, that is d2 (f, f 0 ) = i=1 (f (Xi ) − f 0 (Xi ))2 /n. Denote, for any subset
of functions G, N (G, ε, L2 (Pn )) the ε-covering number of G with respect to the metric
L2 (Pn ). Then, if G ⊂ G1 × G2 (for the multiplication), with kG2 k ≤ 1 and kG1 k ≤ 1,
we may write
√
√
N (G, ε, L2 (Pn )) ≤ N (G1 , ε/(2 2), L2 (Pn )) × N (G2 , ε/(2 2), L2 (Pn )).

Define G1 = {(hv, .i)/t}kvk≤1 , and G2 = 1B(x,r)∩B(0 ,t) x,r . It is obvious that F ⊂
G1 × G2 . Using Theorem 1 in [11], if kGk ≤ 1, we have
 Cdp (G)
2
N (G, ε, L2 (Pn )) ≤
,
ε
20

where C is an absolute constant and dp denotes the pseudo-dimension. Hence we have
 Cd
2
N (G1 , ε, L2 (Pn )) ≤
ε
 C(2(d+1))
2
N (G2 , ε, L2 (Pn )) ≤
.
ε
We may then deduce

 √ C(3d+2)
4 2
N (F, ε, L2 (Pn )) ≤
.
ε
Now, using Dudley’s entropy integral (see, e.g., [5, Corollary 13.2]) yields
Z 1p
n
X
1
Eε √ sup
εi fx,r,v (Xi )/t ≤ 12
log(N (F, ε, L2 (Pn )dε
n x,r,v i=1
0
s
√
Z 1
p
4 2
log(
≤ 12 C(3d + 2)
)dε
ε
0
√
≤ C d.
Hence we deduce that

p
√
CV (p + 1) log(n)
Ct d
√
≤
.
E sup |(Qn − Q)fx,r,v | ≤ √
n
n
x,r,v

Combining the different terms gives, with probability larger than 1 − 2n−p ,
sup k(Qn − Q)y 1B(x,r) (y)dyk ≤ CV
x,r

(p + 1) log(n)
√
.
n

the third deviation bound follows. The fourth deviation bound may be proved the same
way.
p
For the 5-th inequality, as before let λ = p log(n) and t = 4V 2 (log(n) + λ). Similarly, we may write
sup |(Qn − Q)kyk2 1B(x,r) (y)dyk = sup
x,r

x,r

n

1X
kXi k2 1B(x,r) (Xi ) − E(kXk2 1B(x,r) (X))
n i=1
n

≤ sup
x,r

1X
kXi k2 1B(x,r) (Xi )1kXi k≤t − E(kXk2 1B(x,r) (X)1kXk≤t )
n i=1
+ E(kXk2 1kXk>t ) + sup
x,r

n

1X
kXi k2 1kXi k>t ,
n i=1

with E(kXk2 1kXk>t ) ≤ 2V 2 n−(p+1) and, with probability larger than 1 − n− p ,
1

n

sup
x,r

1X
kXi k2 1kXi k>t = 0.
n i=1

Using [5, Theorem 6.2] again leads to
n

P sup
x,r

1X
kXi k2 1B(x,r) (Xi )1kXi k≤t − E(kXk2 1B(x,r) (X)1kXk≤t )
n i=1
n

1X
≥ E sup
kXi k2 1B(x,r) (Xi )1kXi k≤t − E(kXk2 1B(x,r) (X)1kXk≤t ) + t2
x,r n
i=1
21

r

2λ
n

!
1

≤ e−λ = n− p .

At last, combining a symmetrization inequality with a contraction principle ([5, Theorem
11.5]) gives
n

E sup
x,r

≤

1X
kXi k2 1B(x,r) (Xi )1kXi k≤t − E(kXk2 1B(x,r) (X)1kXk≤t )
n i=1

n
X
2t2
kXi k2
EX1:n Eε sup
εi 2 1B(x,r)∩B(0 ,t) (Xi )
n
t
x,r
i=1

n
X
2t2
EX1:n Eε sup
εi 1B(x,r)∩B(0 ,t) (Xi )
n
x,r
i=1
√
C dt2
≤ √ ,
n

≤

where the last line may be derived the same way as for the third inequality, combining
[11, Theorem 1] and [5, Corollary 13.2]. Gluing all pieces yields, with probability larger
1
than 1 − 2n− p ,
√ (p + 1) log(n) 32
√
.
sup (Qn − Q)kyk2 1B(x,r) (y)dy ≤ CV 2 d
n
x,r
The last inequality follows from the same argument. 

A.7

Proof of Lemma 10

Proof
In Proposition 3.6 from [7], we get:
d2P,h (y) = Py,h ky − uk2
≤ Px,h ky − uk2
= ky − xk2 + Px,h kx − uk2 + 2hy − x, x − Px,h ui.
In particular,
d2P,h (y) − kyk2 ≤ d2P,h (x) − kxk2 − 2 hy − x, Px,h ui,
with equality if and only if Py,h ky − uk2 = Px,h ky − uk2 , that is if and only if like hPy,h ,
hPx,h is also a sub-measure of P with total mass h, whose support is contained in the
closed ball B(y, δP,h (y)) and whose restriction to the open ball B(y, δP,h (y)) coincides
with P ; see [7], Proposition 3.3. 

B
B.1

Proofs for Section 3
Proof of Theorem 13

Proof
(k)
First note that for all t, s ∈ Rd , denoting by
fs : x 7→ min

i∈[[1,k]]


kx − m(Psi ,h )k2 + v(Psi ,h ) ,

we have:
P fs (u)−ft (u) ≤

k
X


P̃ti ,h (Rd ) 2hm̃(P̃ti ,h ), m(Pti ,h ) − m(Psi ,h )i + M (Psi ,h ) − M (Pti ,h ) .

i=1

22

Then, according to Lemma 3 and the dominated convergence Theorem, for any v ∈ S(0 , 1 ),
there is a sequence (xn )n∈N in Rd such that m(Pxn ,h ) → m(Pv∞ ,h ) and M (Pxn ,h ) →
M (Pv∞ ,h ). Then, lim supn→+∞ P fxn (u)−fv∞ (u) ≤ 0. Thus, inf t∈Rd P ft (u) = inf t∈Rd P ft (u).
Let (tn )n∈N be a sequence in Rd such that P ftn (u) ≤ inf t∈Rd P ft (u)+ n1 , and denote

by m∗ the limit of a converging subsequence of m̃(P̃tn,1 ,h ), m̃(P̃tn,2 ,h ), . . . , m̃(P̃tn,k ,h ) n∈N
in the compact space B(0, K)(k) . Then, thanks to Lemma 10, and recalling that
∀y ∈ Rd , d2P,h (y) = ky − m(Py,h )k2 + v(Py,h ),
(k)

P fm∗ (u) − ftn (u) ≤ 2

k
X

P̃tn,i ,h (Rd )hm̃(P̃tn,i ,h ) − m∗i , m(Ptn,i ,h ) − m(Pm∗i ,h )i,

i=1

which goes to zero when n → +∞ since km(Py,h )k ≤ K whenever y ∈ Rd . Thus,
P fm∗ (u) = inf t∈Rd P ft (u). In particular, there is some s ∈ Opt(P, h, k) ∩ B(0, K)(k) .
Take Psi ,h ∈ Psi ,h (P ) for all i ∈ [[1, k]], then set s∗ ∈ B(0, K)(k) such that s∗i = m̃(P̃si ,h )
for all i ∈ [[1, k]]. Then for any choice of Ps∗i ,h ∈ Ps∗i ,h (P ),
0 ≤ P fs∗ (u) − fs (u)
≤

k
X

P̃si ,h ku − m(Ps∗i ,h )k2 + v(Ps∗i ,h ) − ku − m(Psi ,h )k2 − v(Psi ,h )

i=1

=

k
X



P̃si ,h d2P,h (si∗ ) − ksi∗ k2 − d2P,h (si ) − ksi k2 − hu − s∗i , 2m(Ps∗i ,h )i + hu − si , 2m(Psi ,h )i

i=1

≤2

k
X

P̃si ,h (Rd )hm̃(P̃si ,h ) − s∗i , m(Psi ,h ) − m(Ps∗i ,h )i = 0.

i=1

Thus, inequalities are all equalities. In particular, equality in Lemma 10 leads to Psi ,h ∈
Ps∗i ,h (P ), and by choosing Ps∗i ,h = Psi ,h , the Laguerre measures (P̃si ,h )i∈[[1,k]] are also
appropriate for s∗ . Then, m̃(P̃s∗i ,h ) = m̃(P̃si ,h ) = s∗i . Thus, s∗ ∈ Opt(P, h, k)∩B(0, K)(k)
and satisfies for some (Ps∗i ,h )i∈[[1,k]] , m̃(P̃s∗i ) = s∗i , for all i ∈ [[1, k]]. 

B.2

Proof of Corollary 19

Proof
[Proof of Corollary 19] The proof of Corollary 19 is based on the following bounds, in
the case where P is absolutely continuous with respect to the Lebesgue measure, with
density f satisfying 0 < fmin ≤ f ≤ fmax .
√
−1
fM
(k) ≤ 2K dk −1/d
(6)
−1
ζP,h (fM
(k)) ≤ KCfmax ,K,d,h k −1/d .

(7)

The first equation proceeds from the following. Since M ⊂ B(0 , K ), for any ε > 0 we
have
√ !d
2K d
fM (ε) ≤ fB (0, K)(ε) ≤
.
ε
Hence (6). To prove the second inequality, we will use the following Lemma.

23

Lemma 27.
Suppose that P has a density f satisfying 0 < fmin ≤ f ≤ fmax . Let x, y be in M , and
denote by δ = kx − yk. Then

1/d !d−1 
1/d
fmax ωd
fmax ωd
d+1
δ.
km(Px,h ) − m(Py,h )k ≤ (2K) ωd 1 + δ
h
h
Proof
[Proof of Lemma 27] Since P has a density, P ∂B(x, δx,h ) = P∂B(y, δy,h ) = 0 . We deduce
that Px,h = h1 P|B(x,h) and Py,h = h1 P|B(y,h) . Without loss of generality, assume that
δx,h ≥ δy,h . Then B(y, δy,h ) ⊂ B(x, δx,h + δ). We may write
km(Px,h ) − m(Py,h )k =
≤
≤
≤
≤


1
P u(1B(x,δx,h ) (u) − 1B(y,δy,h ) (u)
m0
2K
P (1B(x,δx,h ) (u) − 1B(y,δy,h ) (u)
h
2K
P (B(x, δx,h + δ) ∩ B(x, δx,h + δ)c )
h

2K 
d
ωd (δx,h + δ)d − δx,h
h


(2K)d+1 ωd
δ d
(1 +
) −1 .
h
δx,h

Since (1 + v)d ≤ 1 + d(1 + v)d−1 v, for v ≥ 0, and δx,h ≥




h
fmax ωd

1/d

, the result follows.

Hence (7). The result of Corollary 19 follows. 

B.3

Proof of Corollary 20

Proof
[Proof of Corollary 20] Without loss of generality we assume that N is connected. Since
P has a density with respect to the volume measure on N , we have P (N o ) = 1. Thus we
take M = N o , that is the set of interior points. Since P satisfies a (cfmin , d0 )-standard
assumption, we have
0
0
2d
fM (ε) ≤
r−d ,
cfmin
0

−1
according to [8, Lemma 10]. Hence fM
(k) ≤ Cfmin ,N k −1/d . It remains to bound the
continuity modulus of x 7→ m(Px,h ). For any x in M , since P (∂N ) = 0 and P has a
density with respect to the volume measure on N , we have Px,h = P|B(x,h) . Besides,
0
0
since for all r > 0 P (B(x, r)) ≥ cfmin r d , we may write δx,h ≤ cN,fmin h1/d ≤ ρ/12, for h
small enough. Now let x and y be in M so that kx − yk = δ ≤ ρ/12, and without loss of
generality assume that δx,h ≥ δy,h . Then, proceeding as in the proof of Lemma 27, it
comes
2K
km(Px,h ) − m(Py,h )k ≤
P (B(x, δx,h + δ) ∩ B(x, δx,h )c ) .
h
Since δx,h + δ ≤ ρ/6, for any u in B(x, δx,h + δ) ∩ M we may write u = expx (rv), where
v ∈ Tx M with kvk = 1 and r = dN (u, x) is the geodesic distance between u and x (see,
e.g., [1, Proposition 25]). Note that, according to [1, Proposition 26], for any u1 and u2
such that ku1 − u2 k ≤ ρ/4,

ku1 − u2 k ≤ dN (u1 , u2 ) ≤ 2ku1 − u2 k.
24

(8)

Now let p1 , . . . , pm be a δ-covering set of the sphere Sx,δx,h = {u ∈ M |kx − uk = δx,u }.
d0 −1 −(d0 −1)
According to (8), we may choose m ≤ cd0 δx,h
δ
.
Now, for any u such that u ∈ M and δx,h ≤ kx − uk ≤ δx,h + δ, there exists t ∈ Sx,δx,h
such that kt − uk ≤ 2δ. Hence
P (B(x, δx,h + δ) ∩ B(x, δx,h )c ) ≤

m
X

P (B(pj , 2 δ)) .

j=1

Now, for any j, since 2δ ≤ ρ/6, in local polar coordinates around pj we may write,
using (8) again,
Z
P (B(pj , 2 δ)) ≤
f (r, v)J(r, v)drdv
r,v| exppj (rv)∈M,r≤4δ

Z
≤ fmax

J(r, v)drdv
r,v|r≤4δ

where J(r, v) denotes the Jacobian of the volume form. According to [1, Proposition 27],
0
0
we have J(r, v) ≤ Cd0 rd . Hence P (B(pj , 2 δ)) ≤ Cd0 fmax δ d . We may conclude
0
2K
mCd0 fmax δ d
h
≤ CN,fmax ,fmin δ.

km(Px,h ) − m(Py,h )k ≤

0

−1
Choosing k large enough so that fM
(k) ≤ Cfmin ,N k −1/d ≤ ρ/12 gives the result of
Corollary 20. 

B.4

Proof of Proposition 21

Proof
To lighten the notation we omit the ε in dQ,h,k,ε . For all x ∈ Supp(P),
d2Q,h,k (x) − d2P,h (x) = d2Q,h,k (x) − d2Q,h (x) + d2Q,h (x) − d2P,h (x)
≥ −kd2P,h − d2Q,h k∞,Supp(P) .
Thus,



d2Q,h,k − d2P,h


−

≤ kd2P,h − d2Q,h k∞,Supp(P) on Supp(P), where f− : x 7→

f (x)1f (x)≤0 denotes the negative part of any function f on

Rd . Then,


P d2Q,h,k − d2P,h (u) = P d2Q,h,k (u) − d2P,h (u) + 2 d2Q,h,k (u) − d2P,h (u) −
≤ P ∆(u) + P d2P,h,k (u) − d2P,h (u) + 2 kd2P,h − d2Q,h k∞,Supp(P) .
with ∆ = d2Q,h,k − d2P,h,k . We can bound P ∆(u) from above. Let s ∈ Opt(P, h, k) ∩
B(0, K)(k) such that si = m̃(P̃si ,h ) for all i ∈ [[1, k]]. Such an s exists according to
Theorem 13. Set fQ,t (x) = 2hx, m(Qt,h )i + v(Qt,h ) for t ∈ Rd , and let t ∈ Opt(Q, h, k).
P ∆(u) = P min fQ,ti (u) − min fP,si (u)
i∈[[1,k]]

i∈[[1,k]]

≤ (P − Q) min fQ,ti (u) +  + (Q − P ) min fP,si (u) + P min fQ,ti (u) − min fP,si (u).
i∈[[1,k]]

i∈[[1,k]]

i∈[[1,k]]

i∈[[1,k]]

For any transport plan π between P and Q,


P − Q min fQ,ti (u) = E(X,Y )∼π min 2hX, m(Qt,h )i + v(Qt,h ) − min 2hY, m(Qt,h )i + v(Qt,h )
i∈[[1,k]]
i∈[[1,k]]
i∈[[1,k]]
"
#
≤ 2E(X,Y )∼π

sup hX − Y, m(Qt,h )i .

t∈Rd

25

Thus, P − Q mini∈[[1,k]] fQ,ti (u) ≤ 2W1 (P, Q) supt∈Rd m(Qt,h ), after taking for π the
optimal transport plan for the L1 -Wasserstein distance (noted W1 ) between P and Q.
Also note that P mini∈[[1,k]] fQ,ti (u) − mini∈[[1,k]] fP,si (u) is bounded from above by
≤

k
X

P̃si (2hu, m(Qsi ,h )i + v(Qsi ,h )) − (2hu, m(Psi ,h )i + v(Psi ,h )))

i=1

=

k
X
i=1

P̃si min

j∈[[1,k]]

2hu − si , m(Psi ,h ) − m(Qsi ,h )i + d2Q,h (si ) − d2P,h (si )

≤ kd2P,h − d2Q,h k∞,Supp(P) + 2

k
X



P̃si ,h (Rd )hm̃(P̃si ,h ) − si , m(Psi ,h ) − m(Qsi ,h )i.

i=1

Since si = m̃(P̃si ,h ), the result follows.


B.5

Proof of Proposition 22

Proof
The proof of Proposition 22 relies on [7, Corollary 4.8]. Namely, if P satisfies (5), then
1

kdP,h − dM k∞ ≤ C(P )h− d0 .
Let ∆∞,K denote supx∈M |dQ,h,k,ε |, and let x ∈ M achieving the maximum distance.
Since dQ,h,k,ε is 1-Lipschitz, we deduce that B(x, ∆∞ /2 ) ⊂ {y| |dQ,k,h,ε (y)| ≥ ∆∞ /2 }.
0
Since P (B(x, ∆∞ /2 ) ≥ C (P)∆d∞ , Markov inequality yields that
0

d +2
∆2P ≥ C(P )∆∞
.
−

1

2
0

Thus we have supx∈M |dQ,h,k − dM |(x) ≤ C(P ) d0 +2 ∆Pd +2 . Now, for x ∈ Rd , we let
p ∈ M such that
p kx − pk = dM (x). Denote by r = kx − pk, and let tj be such that
dQ,h,k,ε (p) = kp − m(Qtj ,h )k2 + v(Qtj ,h ). Then
q
kx − m(Qtj ,h )k2 + v(Qtj ,h )
q
≤ d2Q,h,k (p) + r2 + 2rkp − m(Qtj ,h )k
q
≤ d2Q,h,k (p) + r2 + 2rdQ,h,k (p)

dQ,h,k (x) ≤

≤ r + (dQ,h,k (p) − dM (p)).
1

On the other hand, we have dQ,h,k,ε ≥ dQ,h , along with kdQ,h − dP,h k∞ ≤ h− 2 W2 (P, Q)
(see, e.g., [7, Theorem 3.5]) as well as dP,h ≥ dM . Hence
1

dQ,h,k,ε ≥ dM − h− 2 W2 (P, Q).


26

C

Proofs for Section 4

C.1

Proof of Proposition 23

Proof
For any t = (t1 , t2 , . . . tk ) ∈ R

(k)
d ,

P
X∈C(ti )

we note ci =

|C(ti )|

X

. Then,

Pn min ku − m(Pn ti ,h )k2 + v(Pn ti ,h )
i∈[[1,k]]

=

=

k
X
1
n
i=1
k
X
i=1

=

1
n

1
n

n
X

X

kX − m(Pn ti ,h )k2 + v(Pn ti ,h )

X∈C(ti )

X

kXk2 − 2hX − ti , m(Pn ti ,h )i + d2Pn ,h (ti ) − kti k2



X∈C(ti )

kXj k2 +

j=1

k
X
|C(ti )|
i=1

n

−2hci − ti , m(Pn ti ,h )i + d2Pn ,h (ti ) − kti k2



k
n
X
1X
2
d2Pn ,h (ci ) − kci k2
kXj k +
≥
n j=1
i=1

=

≥

k
X
1
n
i=1
k
X
i=1

1
n

X

kX − m(Pn ci ,h )k2 + v(Pn ci ,h )

X∈C(ti )

X

kX − m(Pn ci ,h )k2 + v(Pn ci ,h )

X∈C(ci )

= Pn min ku − m(Pn ci ,h )k2 + v(Pn ci ,h ).
i∈[[1,k]]

We used Lemma 10. 

C.2

Proof of Theorem 24

Let γ and γ̂ the functions defined for (t, x) ∈ Rd × Rd with t = (t1 , t2 , . . . , tk ), by:
(k)

γ(t, x) = min −2hx, m(Qti ,h )i + km(Qti ,h )k2 + v(Qti ,h ),
i∈[[1,k]]

and
γ̂(t, x) = min −2hx, m(Qn ti ,h )i + km(Qn ti ,h )k2 + v(Qn ti ,h ).
i∈[[1,k]]

The proof of Theorem 24 is based on the two following deviation Lemmas.
Lemma 28.
If Q is sub-Gaussian with variance V 2 , then, for every p > 0, with probability larger than
1
1 − 2n− p , we have
√
kdV 2 log(n)
√
.
sup |(Q − Qn )γ(t, u)| ≤ C
h n
(k)
t∈R
d

The proof of Lemma 28 is deferred to Section C.3.

27

Lemma 29.
Assume that Q is sub-Gaussian with variance V 2 , then, for every p > 0, with probability
larger than 1 − 7n−p , we have
sup |Qn (γ − γ̂)(t, u)| ≤ CV
(k)

t∈Rd

2 (p

3

3

+ 1) 2 log(n) 2
√
.
h n

As well, the proof of Lemma 29 is deferred to Section C.4. We are now in position to
prove Theorem 24.
Proof
[Proof of Theorem 24] Let
n
o
(k)
s = arg min Qγ(t, u) | t = (t1 , t2 , . . . tk ) ∈ Rd
,
n
o
(k)
ŝ = arg min Qn γ̂(t, u) | t = (t1 , t2 , . . . tk ) ∈ Rd
and

n
o
(k)
s̃ = arg min Qn γ(t, u) | t = (t1 , t2 , . . . tk ) ∈ Rd
.

With these notations, for all x ∈ Rd , d2Q,h,k (x) = kxk2 + γ(s, x) and d2Qn ,h,k (x) =
kxk2 + γ̂(ŝ, x). We intend to bound l(s, ŝ) = Q(d2Qn ,h,k (u) − d2Q,h,k (u)), which is also
equal to l(s, ŝ) = Q(γ(ŝ, u) − Qγ(s, u)).
We have that:
l(s, ŝ) = Qγ(ŝ, u) − Qn γ(ŝ, u) + Qn γ(ŝ, u) − Qn γ(s̃, u) + Qn γ(s̃, u) − Qγ(s, u)
≤ sup (Q − Qn )γ(t, u) + Qn (γ − γ̂)(ŝ, u)
t∈Rd

(k)

+ Qn (γ̂(ŝ, u) − γ̂(s̃, u)) + Qn (γ̂ − γ)(s̃, u) + sup (Qn − Q)γ(t, u),
t∈Rd

(k)

where we used the fact that Qn γ(s̃, u) ≤ Qn γ(s, u). Now, since Qn (γ̂(ŝ, u) − γ̂(s̃, u)) ≤ 0,
we get:
l(s, ŝ) ≤ sup (Q − Qn )γ(t, u) + sup (Qn − Q)γ(t, u)
t∈Rd

t∈Rd

(k)

(k)

+ sup Qn (γ − γ̂)(t, u) + sup Qn (γ̂ − γ)(t, u).
t∈Rd

t∈Rd

(k)

(k)

Combining Lemma 28 and Lemma 29 entails, with probability larger than 1 − 8n−p ,
!
√
3
3
2
2
kdV 2 log(n)
2 (p + 1) log(n)
√
√
l(s, ŝ) ≤ C V
+
.
h n
h n
It remains to bound |P d2Qn ,h,k − Qd2Qn ,h,k | as well as |P d2Q,h,k − Qd2Q,h,k |. To this aim
we recall that X = Y + Z, Z being sub-Gaussian with variance σ 2 . Thus, denoting by
tj (x) = arg minj kx − m(Qtj ,h )k2 + v(Qtj ,h ),


P d2Q,h,k − Qd2Q,h,k ≤ E kY − m(Qtj (Y ),h )k2 + v(Qtj (Y ),h ) − kY + Z − m(Qtj (Y ),h )k2 + v(Qtj (Y ),h )
≤ EkZk2 + 2E max

Z, m(Qtj ,h ) − (Y + Z)
√
≤ σ 2 + 2σ( max km(Qtj ,h )k + 2(K + σ))
j∈[[1,k]]

j∈[[1,k]]

CσK
≤ √ ,
h
28

using (9) and σ ≤ K. The converse bound on P d2Q,h,k − Qd2Q,h,k may be proved the
same way. Similarly, we may write
√
P d2Qn ,h,k − Qd2Qn ,h,k ≤ σ 2 + 2σ( max km(Qn,tj ,h )k + 2(K + σ)
j∈[[1,k]]

≤ σ 2 + 2σ( max km(Qtj ,h )k +
j∈[[1,k]]

≤

√
C(K + σ)(p + 1) log(n)
√
) + 2(K + σ))
h n

CσK(p + 1) log(n)
√
,
h n

according to Lemma 2. The bound on Qd2Qn ,h,k − Pd2Qn ,h,k derives from the same
argument. Collecting all pieces, we have
P (d2Qn ,h,k − d2Q,h,k ) ≤ Q(d2Qn ,h,k − d2Q,h,k ) +

CσK(p + 1) log(n)
√
h n
3

CσK(p + 1) log(n) CkK 2 ((p + 1) log(n)) 2
√
√
≤
+
,
h n
h n
where we used σ ≤ K.


C.3

Proof of Lemma 28

Proof
With the notation lti (x) = −2hx, m(Qti ,h )i + km(Qti ,h )k2 + v(Qti ,h ), we get that:


sup (Q − Qn )γ(t, u) = sup (Q − Qn ) min lti (u) .
t∈Rd

t∈Rd

(k)

(k)

i∈[[1,k]]

First we note that since Q is sub-Gaussian with variance V 2 , we have, for every c ∈ Rd ,
km(Qc,h )k2 + v(Qc,h ) = Qt,h kuk2 ≤
Set z = 2V

2V 2
.
h

(9)

p
1
log(n) + λ and λ = p log(n). Then, with probability larger than 1 − n− p ,
max kXi k ≤ z.

(10)

i=1,...,n

We may then write
n

sup |(Q − Qn )γ(t, u)| = sup

t∈Rd

(k)

t∈Rd

(k)

1X
γ(t, Xi ) − E(γ(t, X))
n i=1
n

≤ sup
t∈Rd

(k)

1X
γ(t, Xi )1kXi k≤z − E(γ(t, X)1kXk≤z) )
n i=1

+ sup
t∈Rd

(k)

E(|γ(t, X)1kXk>z |) + sup
t∈Rd

(k)

29

n

1X
γ(t, Xi )1kXi k>z .
n i=1

1

According to (10), the last part is 0 with probability larger than 1 − n− p . Moreover

E(|γ(t, X)|1kXk>z ) ≤ E(1kXk>z sup 2|hx, m(Qtj ,h )|i| + km(Qtj ,h )k2 + v(Qtj ,h )
j=1,...,k

√ V
2V
P(kXk > z) + 2 2 √ E(kXk1kXk>z )
h
h
2
2
z
V
≤ 10 e− 2V 2
h
V 2 −(p+1)
.
≤ 10 n
h
2

≤

It remains to bound

sup (Q − Qn )γ(t, u)1kuk≤z .

t∈Rd

(k)

Since for every t and u, |γ(t, u)1kuk≤z | ≤ (z +

P  sup (Q − Qn )γ(t, u)1kuk≤z
t∈Rd

(k)

√
V√ 2 2
)
h

:= R, [5, Theorem 6.2] entails
r 
2λ 
≥ E sup (Q − Qn )γ(t, u)1kuk≤z + R
≤ e−λ = n−p .
n
(k)
t∈R
d

To bound E supt∈R(k) (Q − Qn )γ(t, u)1kuk≤z , we follow the same line as for Lemma 25.
d
A symmetrization argument yields


n
X
2
E sup (Q − Qn ) min lti (u)1kuk≤z ≤ EX1:n Eσ  sup
σi min ltj (Xi )1kXi k≤z 
n
i∈[[1,k]]
j∈[[1,k]]
(k)
(k)
t∈Rd
t∈Rd i=1


n
X
lt (Xi )1kXi k≤z
2R
,
σi min j
EX1:n Eσ  sup
≤
n
R
j∈[[1,k]]
(k)
t∈R
i=1
d

where the σi ’s are i.i.d. Rademacher variables, independent of the Xi ’s, and EY denotes
expectation with respect to the random variable Y . As in Section A.6, denote, for any
subset of functions G, N (G, ε) the ε-covering number of G with respect to the metric
L2 (Pn ). Denote by Fk the set of functions x 7→ minj∈[[1,k]]
lt (x)1kxk≤z
,
R

of functions x 7→
may write, for any ε > 0,

d

t ∈ R̄ . Since the x 7→

ltj (x)1kxk≤z
,
R

ltj (x)1kxk≤z
R

and by F the set

are bounded by 1, we

N (Fk , ε) ≤ N (F, ε)k ,
as well as



√
−2 hx, m(Qt,h )i 1kxk≤z
x 7→
, ε/2 2
R



√
(km(Qt,h )k2 + v(Qt,h ))1kxk≤z
×N
x 7→
, ε/2 2
R
√
√
≤ N (G1 , ε/2 2) × N (G2 , ε/2 2).

N (F, ε) ≤ N

Using [11, Theorem 1] yields
 2(d+1)C
2
ε
 2C
2
N (G2 , ε) ≤
.
ε

N (G1 , ε)) ≤

30

We then deduce
N (Fk , ε) ≤

 √ 2k(d+2)C
4 2
.
ε

Using [5, Corollary 13.2] leads to


n
X
p
ltj (Xi )1kXi k≤z
 ≤ C k(d + 2)n.
Eσ  sup
σi min
R
j∈[[1,k]]
(k)
t∈R
i=1
d

Combining these bounds gives the result of Lemma 28. 

C.4

Proof of Lemma 29

Proof
(k)
For t ∈ Rd , we get that:

|γ(t, x) − γ̂(t, x)| ≤ max | − 2hx, m(Qtj ,h ) − m(Qn tj ,h )i + M (Qtj ,h ) − M (Qn tj ,h ) |
j∈[[1,k]]

≤ 2kxk max km(Qtj ,h ) − m(Qn tj ,h k + max kM (Qtj ,h ) − M (Qn tj ,h k.
j∈[[1,k]]

j∈[[1,k]]

Let t ∈ Rd , and denote by r = δQ,h (t), rn = δQn ,h (t), and z = 2V
We may write

p

(p + 1) log(n).


1
kQu1B(t,r) (u) − Qu1B(t,rn ) (u)k + kQu1B(t,rn ) (u) − Qn u1B(t,rn ) (u)k
h

1
≤
k(Q − Qn )u1B(t,rn ) (u)k + Qkuk|1B(t,rn ) − 1B(t,r) |(u)
h

1
k(Q − Qn )u1B(t,rn ) (u)k + zQ|1B(t,rn ) − 1B(t,r) |(u) + Qkuk1kuk>z .
≤
h

km(Qt,h ) − m(Qn t,h )k ≤

Moreover, Q 1B(t,r) − 1B(t,rn ) (u) = |h − Q(B(t, rn ))| = |Qn (B(t, rn )) − Q(B(t, rn ))|.
On the event described in Lemma 25, we have that
√ (p + 1) log(n)
√
d
,
n
p
√
(p + 1) log(n)
√
|Qn (B(t, rn )) − Q(B(t, rn ))| ≤ C d
,
n
k(Q − Qn )u1B(t,rn ) (u)k ≤ CV

Qkuk1kuk>z ≤ 2V n−(p+1) .
Thus,
sup km(Qt,h ) − m(Qn t,h )k ≤

t∈R

d

CV (p + 1) log(n)
√
.
h n

As well,

1
(Q − Qn )kuk2 1B(t,rn ) + Qkuk2 |1B(t,rn ) − 1B(t,r |
h

1
≤
(Q − Qn )kuk2 1B(t,rn ) + Qkuk2 1kuk>z + z 2 |(Q − Qn )1B(t,rn ) | .
h

sup |M (Qt,h ) − M (Qn t,h )| ≤

t∈Rd

31

Using Lemma 25 again, we get
√ (p + 1) log(n) 23
√
(Q − Qn )kuk2 1B(t,rn ) ≤ CV 2 d
n
p
√
(p + 1) log(n)
√
|(Q − Qn )1B(t,rn ) | ≤ C d
n
Qkuk2 1kuk>z ≤ 2V 2 n−(p+1) .
Collecting all pieces leads to
3

|γ(t, x) − γ̂(t, x)| ≤ Ckxk

3

V (p + 1) log(n)
(p + 1) 2 log(n) 2
√
√
+ CV 2
.
h n
h n

At last, since
n
o
t2
P max kXi k ≥ z ≤ ne− 2V 2 ≤ n−2p+1 ,
i

we deduce that

3

Qn |γ(t, x) − γ̂(t, x)| ≤ CV 2


32

3

(p + 1) 2 log(n) 2
√
.
h n

(11)

