Detection of low dimensionality and data denoising via set
estimation techniques

arXiv:1702.05193v2 [] 3 Nov 2017

c

Catherine Aarona , Alejandro Cholaquidisb and Antonio Cuevasc
a
Université Blaise-Pascal Clermont II, France
b
Centro de Matemática, Universidad de la República, Uruguay
Departamento de Matemáticas, Universidad Autónoma de Madrid
Abstract

This work is closely related to the theories of set estimation and manifold estimation. Our
object of interest is a, possibly lower-dimensional, compact set S ⊂ Rd . The general aim is to
identify (via stochastic procedures) some qualitative or quantitative features of S, of geometric
or topological character. The available information is just a random sample of points drawn on
S. The term “to identify” means here to achieve a correct answer almost surely (a.s.) when the
sample size tends to infinity. More specifically the paper aims at giving some partial answers
to the following questions: is S full dimensional? Is S “close to a lower dimensional set” M?
If so, can we estimate M or some functionals of M (in particular, the Minkowski content of
M)? As an important auxiliary tool in the answers of these questions, a denoising procedure
is proposed in order to partially remove the noise in the original data. The theoretical results
are complemented with some simulations and graphical illustrations.

1

Introduction

The general setup and some related literature. The emerging statistical field currently known as
manifold estimation (or, sometimes, statistics on manifolds, or manifold learning) is the result of
the confluence of, at least, three classical theories: (a) the analysis of directional (or circular) data
Mardia and Jupp (2000), Bhattacharya and Patrangenaru (2008) where the aims are similar to those
of the classical statistics but the data are supposed to be drawn on the sphere or, more generally,
on a lower-dimensional manifold; (b) the study of non-linear methods of dimension reduction,
Delicado (2001), Hastie and Stuetzle (1989), aiming at recovering a lower-dimensional structure
from random points taken around it, and (c) some techniques of stochastic geometry Chazal and
Lieutier (2005) and set estimation Cuevas and Fraiman (2010), Cholaquidis et al. (2014), Cuevas
et al. (2007) whose purpose is to estimate some relevant quantities of a set (or the set itself) from
the information provided by a random sample whose distribution is closely related to the set.
There are also strong connections with the theories of persistent homology and computational
topology, Carlsson (2009), Niyogi, Smale and Weinberger (2011), Fasy et al. (2014), Cavanna et al
(2015).
In all these studies, from different points of view, the general aim is similar: one wants to get
information (very often of geometric or topological type) on a set from a sample of points. To be
more specific, let us mention some recent references on these topics, roughly grouped according the
subject (the list is largely non-exhaustive):
Manifold recovery from a sample of points, Genovese et al. (2012b); Genovese et al (2012c).
Inference on dimension, Fefferman et al. (2016), Brito et al. (2013).
Estimation of measures (perimeter, surface area, curvatures), Cuevas et al. (2007), Jiménez
and Yukich (2011), Berrendero et al. (2014).
1

Estimation of some other relevant quantities in a manifold, Niyogi, Smale and Weinberger
(2008), Chen and Müller (2012).
Dimensionality reduction, Genovese et al. (2012a), Tenebaum et al. (2000).
The problems under study. The contents of the paper. We are interested in getting some information (in particular, regarding dimensionality and Minkowski content) about a compact set
M ⊂ Rd . While the set M is typically unknown, we are supposed to have a random sample of
points X1 , . . . , Xn whose distribution PX has a support “close to M”. To be more specific, we
consider two different models:
The noiseless model : the support of PX is M itself; Aamari and Levrard (2015), Amenta et
al. (2002), Cholaquidis et al. (2014), Cuevas and Fraiman (1997).
The parallel (noisy) model : the support of PX is the parallel set S of points within a distance
to M smaller than R1 , for some R1 > 0, where M is a d0 -dimensional set and d0 ≤ d; Berrendero
et al. (2014). Note that other different models “with noise” are considered in Genovese et al.
(2012a), Genovese et al. (2012b) and Genovese et al (2012c).
In Section 3 we first develop, under the noiseless model, an algorithmic procedure to identify,
eventually, almost surely (a.s.), whether or not M has an empty interior; this is achieved in Theorems
1 and 2 below. A positive answer would essentially entail (under some conditions, see the beginning
of Section 3) that M has a dimension smaller than that of the ambient space.
Then, assuming the noisy model and M̊ = ∅ ( where M̊ denotes the interior of M) Theorems 3
(i) and 4 (i) provide two methods for the estimation of the maximum level of noise R1 , giving also
the corresponding convergence rates. If R1 is known in advance, the remaining results in Theorems
3 and 4 allow us also to decide whether or not the “inside set” M has an empty interior.
The identification methods are “algorithmic” in the sense that they are based on automatic
procedures to perform them with arbitrary precision. This will require to impose some regularity
conditions on M or S. Section 2 includes all the relevant definitions, notations and basic geometric
concepts we will need.
In Section 4 we consider again the noisy model where the data are drawn on the R1 -parallel set
around a lower dimensional set M. We propose a method to “denoise” the sample, which essentially
amounts to estimate M from sample data drawn around the parallel set S around M.
In Section 5 we consider the problem of estimating the d0 -dimensional Minkowski measure of
M under both the noiseless and the noisy model. We assume throughout the section that the
dimension d0 (in Hausdorff sense, see below) of the set M is known.
Finally, in Section 6 we present some simulations and numerical illustrations.

2

Some geometric background

This section is devoted to make explicit the notations, and basic concepts and definitions (mostly
of geometric character) we will need in the rest of the paper.
Some notation. Given a set S ⊂ Rd , we will denote by S̊, S, ∂S and S c , the interior, closure,
boundary and complement of S respectively, with respect to the usual topology of Rd . Let us
denote d(y, S) = inf x∈S ky − xk for y ∈ Rd , where k · k stands for the Euclidean norm. We will also
denote ρ(S) = supx∈S d(x, ∂S). Notice that ρ(S) > 0 is equivalent to S̊ 6= ∅.
2

The parallel set of S of radius ε will be denoted as B(S, ε), that is B(S, ε) = {y ∈ Rd : inf x∈S
ky − xk ≤ ε}. If A ⊂ Rd is a Borel set, then µd (A) (sometimes just µ(A)) will denote its Lebesgue
measure. We will denote by B(x, ε) (or Bd (x, ε), when necessary) the closed ball in Rd , of radius ε,
centred at x, and ωd = µd (Bd (x, 1)). Given two compact non-empty sets A, B ⊂ Rd , the Hausdorff
distance or Hausdorff-Pompeiu distance between A and C is defined by
dH (A, C) = inf{ε > 0 : such that A ⊂ B(C, ε) and C ⊂ B(A, ε)}.

(1)

Some geometric regularity conditions for sets. The following conditions have been used many times
in set estimation topics see, e.g., Niyogi, Smale and Weinberger (2008), Genovese et al. (2012b),
Cuevas and Fraiman (2010) and references therein.
Definition 1. Let S ⊂ Rd be a closed set. The set S is said to satisfy the outside r-rolling condition
if for each boundary point s ∈ ∂S there exists some x ∈ S c such that B(x, r) ∩ ∂S = {s}. A compact
set S is said to satisfy the inside r-rolling condition if S c satisfies the outside r-rolling condition at
all boundary points.
Definition 2. A set S ⊂ Rd is said to be r-convex, for r > 0, if S = Cr (S), where
c

\
Cr (S) =
B̊(x, r) ,


(2)

B̊(x,r): B̊(x,r)∩S=∅

is the r-convex hull of S. When S is r-convex, a natural estimator of S from a random sample Xn
of points (drawn on a distribution with support S), is Cr (Xn ).
Following the notation in Federer (1959), let Unp(S) be the set of points x ∈ Rd with a unique
projection on S.
Definition 3. For x ∈ S,
 let reach(S, x) = sup{r > 0 : B̊(x, r) ⊂ Unp(S) . The reach of S is
defined by reach(S) = inf reach(S, x) : x ∈ S , and S is said to be of positive reach if reach(S) > 0.
The study of sets with positive reach was started by Federer (1959); see Thäle (2008) for a
survey. This is now a major topic in different problems of manifold learning or topological data
analysis. See, e.g., Adler et al. (2016) for a recent reference.
The conditions established in Definitions 1, 2 and 3 have an obvious mutual affinity. In fact, they
are collectively referred to as “rolling properties” in Cuevas, Fraiman and Pateiro-López (2012).
However, they are not equivalent: if the reach of S is r then S is r-convex, which in turn implies the
(outer) r-rolling condition. The converse implications are not true in general; see Cuevas, Fraiman
and Pateiro-López (2012) for details.
Definition 4. A set S ⊂ Rd is said to be standard with respect to a Borel measure ν at a point x
if there exists λ > 0 and δ > 0 such that
ν(B(x, ε) ∩ S) ≥ δµd (B(x, ε)),

0 < ε ≤ λ.

(3)

A set S ⊂ Rd is said to be standard if (3) holds for all x ∈ S.
The following results will be useful below. The first one establishes a simple connection between
standardness and the inside r-rolling condition. The second one (whose proof can be found in
Pateiro-López and Rodrı́guez-Casal (2009)) relates the rolling condition with the reach property.
3

Proposition 1. Let S ⊂ Rd the support of a Borel measure ν, whose density f with respect to the
Lebesgue measure is bounded from below by f0 , if S satisfies reach(S c ) ≥ r, then it is standard with
respect to ν, for any δ ≤ f0 /3 and λ = r.
Proof. Let 0 < ε ≤ r and x ∈ S, if d(x, ∂S) ≥ r the result is obvious. Let x ∈ S such that
d(x, ∂S) < r. Since reach(S c ) ≥ r there exists z ∈ Rd such that x ∈ B(z, r) ⊂ S. Then, for all
ε≤r
ν(B(x, ε) ∩ S) ≥ ν(B(x, ε) ∩ B(z, r)) ≥ f0 µd (B(x, ε) ∩ B(z, r)) ≥

f0
µd (B(x, ε)).
3

Proposition 2 (Lemma 2.3 in Pateiro-López and Rodrı́guez-Casal (2009)). Let S ⊂ Rd be a
non-empty closed set. If S satisfies the inside and outside r-rolling condition, then reach(∂S) ≥ r.
Some basic definitions on manifolds. The following basic concepts are stated here for the sake
of completeness and notational clarity. More complete information on these topics can be found,
for example, in the classical textbooks Boothby (1975) and Do Carmo (1992). See also the book
Galbis and Maestre (2010) and the summary (Zhang, 2011, chapter 3). Let us start with the
classical concept of sub-manifold in Rd (often referred to simply as “manifold”). Denote by Rk+ the
half-space Rk+ = {x ∈ Rk : xk ≥ 0}.
Definition 5. A topological sub-manifold M of dimension k in Rd is a subset of Rd with k ≤ d
such that every point in M has a neighborhood homeomorphic either to Rk or to Rk+ .
Those points of M having no neighborhood homeomorphic to Rk are called boundary points.
If the boundary of M (i.e. the set of boundary points of M) is empty we will say that M is a
(sub-)manifold without boundary.
We will say that a manifold without boundary M is a regular k-surface, or a differentiable kmanifold of class p ≥ 1, if there is a family (often called atlas) V = {(Vα , xα )} of pairs (Vα , xα )
(often called parametrizations, coordinate systems or charts) such that the Vα are open sets in Rk
and the xα : Vα → M are functions of class p satisfying: (i) M = ∪α xα (Vα ), (ii) every xα is a
homeomorphism between Vα and xα (Vα ) and (iii) for every v ∈ Vα the differential dxα (u) : Rk → Rd
is injective.
A manifold with boundary M is said to be a regular k-surface if the set of interior points in M
is a regular k-surface.
A manifold M is said to be compact when it is compact as a topological space. As a direct
consequence of the definition of compactness, any compact differentiable manifold has a finite atlas.
Typically, in most relevant cases the required atlas for a differentiable manifold has, at most, a
denumerable set of charts.
An equivalent definition of the notion of manifold (see Do Carmo (1992, Def 2.1, p. 2)) can be
stated in terms of parametrizations or coordinate systems of type (Uα , ϕα ) with ϕα : Vα ⊂ M → Rk .
The conditions would be completely similar to the previous ones, except that the ϕα are defined in
a reverse way to that of Definition 5.
In the simplest case, just one chart x : V → M is needed. The structures defined in this way
are sometimes called planar manifolds.

4

Some background on geometric measure theory. The important problem of defining lower-dimensional
measures (surface measure, perimeter, etc.) has been tackled in different ways. The book by Mattila (1995) is a classical reference. We first recall the so-called Hausdorff measure. It is defined for
any separable metric space (M, ρ). Given δ, r > 0 and E ⊂ M, let


∞
X

Hδr (E) = inf
(diam(Bj ))r : E ⊂ ∪∞
B
,
diam(B
)
≤
δ
,
j
j=1 j


j=1

where diam(B) = sup{ρ(x, y) : x, y ∈ B}, inf ∅ = ∞. Now, define Hr (E) = limδ→0 Hδr (E).
The set function Hr is an outer measure. If we restrict Hr to the measurable sets (according
to standard Caratheodory’s definition) we get the r-dimensional Hausdorff measure on M.
The Hausdorff dimension of a set E is defined by
dimH (E) = inf{r ≥ 0 : Hr (E) = 0} = sup({r ≥ 0 : Hr (E) = ∞} ∪ {0}).

(4)

It can be proved that, when M is a k-dimensional smooth manifold, dimH (M) = k.
Another popular notion to define lower-dimensional measures for the case M ⊂ Rd is the
Minkowski content. For an integer d0 < d recall that ωd−d0 = µd−d0 (B(0, 1)) and define the d0 dimensional Minkowski content of a set M by
0

Ld0 (M) = lim

ε→0

µd (B(M, ε))
,
ωd−d0 εd−d0

(5)

provided that this limit does exist.
0
In what follows we will often denote Ld0 (M) = L0 (M), when the value of d0 is understood. The
term “content” is used here as a surrogate for “measure”, as the expression (5) does not generally
leads to a true (sigma-additive) measure.
0
A compact set M ⊂ Rd is said to be d0 -rectifiable if there exists a compact set K ⊂ Rd and a
0
Lipschitz function f : Rd → Rd such that M = f (K). Theorem 3.2.39 in Federer (1969) proves
0
0
that for a compact d0 -rectifiable set M, Ld0 (M) = Hd (M). More details on the relations between
the rectifiability property and the structure of manifold can be found in Federer (1969) Theorem
3.2.29.

3

Checking closeness to lower dimensionality

We consider here the problem of identifying whether or not the set M ⊂ Rd (not necessarily a
manifold) has an empty interior.
Note that, if M ⊂ Rd is “regular enough”, dimH (M) < d is in fact equivalent to M̊ = ∅. Indeed,
in general dimH (M) < d implies M̊ = ∅. The converse implication is not always true, even for sets
fulfilling the property Hd (∂M) = 0 (see Avila and Lyubich (2007)). However it holds if M has
positive reach, since in this case Hd−1 (∂M) < ∞ (see the comments after Th. 7 and inequality (27)
in Ambrosio, Colesanti and Villa (2008)).
Also, clearly, in the case where M is a manifold, the fact that M has an empty interior amounts
to say that its dimension is smaller than that of the ambient space.

5

3.1

The noiseless model

We first consider the case where the sample information follows the noiseless model explained in the
Introduction, that is, the data Xn = {X1 , . . . , Xn } are assumed to be an iid sample of points drawn
from an unknown distribution PX with support M ⊂ Rd . When M is a lower-dimensional set, this
model can be considered as an extension of the classical theory of directional (or spherical) data,
in which the sample data are assumed to follow a distribution whose support is the unit sphere in
Rd . See, e.g., Mardia and Jupp (2000).
Our main tool here will be the simple offset or Devroye-Wise estimator (see Devroye and Wise
(1980)) given by
n
[
Ŝn (r) =
B(Xi , r).
(6)
i=1

More specifically, we are especially interested in the “boundary balls” of Ŝn (r).
Definition 6. Given r > 0 let Ŝn (r) the set estimator (6) based on {X1 , . . . , Xn }. We will say
that B(Xi , r) is a boundary ball of Ŝn (r) if there exists a point y ∈ ∂B(Xi , r) such that y ∈ ∂ Ŝn (r).
The “peeling” of Ŝn (r), denoted by peel(Ŝn (r)), is the union of all non-boundary balls of Ŝn (r). In
other words, peel(Ŝn (r)) is the result of removing from Ŝn (r) all the boundary balls.
The following theorem is the main result of this section. It relates, in statistical terms, the
emptiness of M̊ with peel(Ŝn ).
Theorem 1. Let M ⊂ Rd be a compact non-empty set. Then under the model and notations stated
in the two previous paragraphs we have,
(i) if M̊ = ∅, and M fulfills the outside rolling condition for some r > 0, then peel(Ŝn (r0 )) = ∅
for any set Ŝn (r0 ) of type (6) with r0 < r.
(ii) In the case M̊ 6= ∅, assume that there exists a ball B(x0 , ρ0 ) ⊂ M̊ such that B(x0 , ρ0 ) is
standard w.r.t to PX , with constants δ and λ = ρ0 (see Definition (4)). Then peel(Ŝn (rn )) 6= ∅
1/d
≤ rn ≤ ρ0 /2 for a given
eventually, a.s., where rn is a radius sequence such that: (κ log(n)
n )
κ > (δωd )−1 .
Proof. (i) To prove that peel(Ŝn (r0 )) = ∅ for all r0 < r it is enough to prove that for all r0 < r and
for all i = 1, . . . , n there exists a point yi ∈ ∂B(Xi , r0 ) such that yi ∈
/ B(Xj , r0 )
for all Xj 6= Xi . Since M is closed and M̊ = ∅, ∂M = M. The outside rolling ball property implies
that for all Xi ∈ M exists zi ∈ Mc such that B(zi , r) ∩ M = {Xi }. Let us denote ui = (zi − Xi )/r,
then yi = Xi + r0 ui see Figure 1. Clearly yi ∈ ∂B(Xi , r0 ). From B(yi , r0 ) ⊂ B(zi , r) and the outside
rolling ball property we get that {Xi } ⊂ B(yi , r0 ) ∩ Xn ⊂ B(zi , r) ∩ M ⊂ {Xi } so that, for all
Xj 6= Xi , Xj ∈
/ B(yi , r0 ) and thus, yi ∈
/ B(Xj , r0 ).
(ii) First we are going to prove that
 C log(n) 1/d
if
≤ rn ≤ ρ0 /2 for a given C > 1 then eventually a.s. for all y ∈ B(x0 , 2rn ) we have
δωd n
B̊(y, rn ) ∩ Xn 6= ∅.
(7)
Consider only n ≥ 3 and let εn = (log(n))−1 , there is a positive constant τd , such that we can cover
B(x0 , 2rn ) with νn = τd ε−d
n balls of radius rn εn centred in {t1 , . . . , tνn }. Let us define


pn = PX ∃y ∈ B(x0 , 2rn ), B̊(y, rn ) ∩ Xn = ∅ ,
6

Figure 1:
then,
pn ≤

νn
X




PX B ti , rn (1 − εn ) ∩ Xn = ∅ .

(8)

i=1

Notice that for any given i,

 

 n
PX B ti , rn (1 − εn ) ∩ Xn = ∅ = 1 − PX B ti , rn (1 − εn )
.
Since rn ≤ ρ0 /2, ti ∈ B(x0 , ρ0 ), then using that B(x0 , ρ0 ) is standard with the same δ,

 
n

PX B ti , rn (1 − εn ) ∩ Xn = ∅ ≤ 1 − ωd δrnd (1 − εn )d

d  n
log(n)
1 − εn
.
≤ 1−C
n
Which, according to (8) provides:

 d n
log(n)
−C(1−εn )d
pn ≤ τd ε−d
1
−
C
1
−
ε
≤ τd ε−d
,
n
n
n n
n
where we have usedPthat (1 − x)n ≤ exp(−nx). Since C > 1, we can choose β > 1 such that
pn /n−β → 0, then,
pn < ∞. Finally (7) follows as a direct application of Borel Cantelli Lemma.
Observe that (7) implies that x0 ∈ Ŝn (rn ) eventually a.s. see Figure 2, so there exists Xi such that
x0 ∈ B(Xi , rn ) eventually a.s. Again by (7) we get that, eventually a.s. for all z ∈ ∂B(Xi , rn )
there exists Xj such that z ∈ B̊(Xj , rn ) and so z ∈
/ ∂ Ŝn (rn ), which implies that, eventually a.s.,
B(Xi , rn ) is not removed by the peeling process and so peel(Ŝn (rn )) 6= ∅ eventually, a.s..
Remark 1. Some comments on Theorem 1 are in order, regarding the intuitive meaning of the
result itself, the required assumptions and the involved parameters. First note that the outside
rolling condition imposed in part (i) is nothing but a geometric smoothness property ruling out the
existence of very sharp inward peaks in the boundary of the set. It is close, but not equivalent,
to the positive reach condition, as stated in Definition 3. Clearly, the value of the parameter r in
Theorem 1 is a regularity condition on M: the larger r, the more regular M. In general, if we want
to obtain, using statistical methods, some meaningful results on the dimensionality or the interior

7

Figure 2:
of M, we will need to impose some regularity property. The advantage of the rolling condition is
its simple intuitive, almost “visual”, interpretation. See Walther (1999) and Cuevas, Fraiman and
Pateiro-López (2012) for further insights on the rolling condition and related properties.
Regarding part (ii): if M̊ 6= ∅ there must be some ball B(x0 , ρ0 ) included in M̊ 6= ∅. The
standardness assumption imposed in the theorem, only asks that the probability PX is not “too far
from uniformity” on that ball. To be more specific, the probability of the intersection with B(x0 , ρ0 )
of any small enough ball B centered at a point of B(x0 , ρ0 ) must be at most δ times the volume of
B. Observe that this mild condition holds, in particular, whenever PX has a density f bounded from
below by a positive constant. More insights on the meaning and use of this standardness property
can be found, for example, in Cuevas and Fraiman (1997) and Rinaldo and Wasserman (2010).
Finally, about the interpretation of parts (i) and (ii) in the theorem: statement (i) is simple. It
just establishes that the property M̊ = ∅ can be identified, with probability one, whatever the simple
size using the offset estimator (6) with any radius smaller that the assumed rolling parameter r.
As for part (ii), let us note that the only relevant parameter is the standardness constant δ. A
conservative choice of δ would also do the job asymptotically. In this case, the identification of
M̊ 6= ∅ is done asymptotically (eventually, a.s.) by taking the offset estimator with balls of radii rn
depending only on δ and n. The order (log n/n)1/d of such balls appears typically in the convergence
rates of many set estimators (see Cuevas and Fraiman (1997), Rodrı́guez-Casal (2007)) as well as
in the theory of multivariate spacings, Janson (1987).
Hence, in summary, the method to identify whether or not M̊ = ∅ is completely “algorithmic”
and works, under some regularity conditions on M, with probability one. While the situation M̊ = ∅
is easy to identify, the identification of M̊ 6= ∅ only works asymptotically.
The manifold case. If M is assumed to be a manifold, then, under some mild additional assumptions,
the identification of low dimensionality can be done in a completely automatic (data-driven) way,
with no resort to extra parameters. In other words, the radius of the balls in the auxiliary DevroyeWise estimator can be chosen as a function of the data in such a way that it is (asymptotically)
small enough to identify the situation M̊ = ∅ and large enough to eventually detect M̊ = ∅, when
this is the case.
Theorem 2. Let M be a d0 -dimensional compact manifold in Rd . Suppose that the sample points
X1 , . . . , Xn are drawn from a probability measure PX with support M which has a density f , with respect the d0 -dimensional Hausdorff measure on M, continuous on M such that f0 = minx∈M f (x) >
0. Let us define, for any β > 61/d , rn = β maxi minj6=i kXj − Xi k. Then,

8

i) if d0 = d and ∂M is a C2 manifold then peel(Ŝn (rn )) 6= ∅ eventually, a.s..
ii) if d0 < d and M is a C2 manifold without boundary, then peel(Ŝn (rn )) = ∅ eventually, a.s.
Proof.
i) We will use Theorem 1 (ii). In order to do that, we will prove first that the set is
standard. As d0 = d then ∂M is a C2 a compact (d − 1)-manifold. Then we can use the
following result, due to Walther (1999).
Theorem (Walther, 1999, Th.1).- Let S ⊂ Rd be a compact path-connected set with S̊ 6= ∅
and let r0 > 0. Then, the following conditions are equivalent
1 A ball of radius r rolls freely inside S and inside S c for all 0 ≤ r ≤ r0 .
2 ∂S is a (d − 1)-dimensional C 1 submanifold in Rd with the outward pointing unit normal
vector n(s) at s ∈ ∂S satisfying the Lipschitz condition
kn(s) − n(t)k ≤

1
ks − tk
r0

for all s, t ∈ ∂S

In fact, the author points out that the result is also valid if the condition of path-connected
is dropped and we only assume that every path connected component of M has non-empty
interior. Hence, note that this result can be applied in our case for S = M since the C2
assumption on the compact hypersurface ∂M implies the Lipschitz condition for the outward
normal vector and the assumption M̊1 6= ∅ for every path-connected component M1 of M
is guaranteed from the fact that every point in M has a neighborhood homeomorphic to an
open set in Rd+ . Thus, we may use the result 2 ⇒ 1 in the above theorem to conclude that
M fulfills both the inside and outside rolling ball property for a small enough radius r > 0.
Then by Proposition 2 reach(∂M) ≥ r. So, by Proposition 1, M satisfies the standardness
condition established in Definition 4 with ν = PX , δ = f0 /3 and λ < r. Now, in order to
prove that rn fulfils all the conditions in Theorem 1 (ii) observe that in the full-dimensional
case d0 = d the intrinsic volume in M coincides with the restricted Lebesgue measure; see
(Taylor, 2006, Prop. 12.6). As a consequence, f is equal to the density of PX w.r.t. the
Lebesgue measure restricted to M. Let us denote f1 = minx∈∂M f (x). Note that rn /β is in
fact the “connectivity statistic”, that is the minimum value of r such that ∪i B(Xi , r) is a
connected set. Then, as f is continuous and bounded below from zero on the compact set M
with smooth boundary we are in the assumptions of Theorem 1.1 in Penrose (1999) so that,
using this result we can conclude that, with probability one, we have,
n 1 2(d − 1) o
nrnd ωd
1
→
max
,
≥ .
d
log(n)β
f0
df1
f0
Then for n large enough,
rn ≥

 log(n) β d 1/d
,
n ωd 2f0

now if we denote κ = β d /(ωd 2f0 ), it fulfills that κ > (δωd )−1 , so we are in the hypotheses of
Theorem 1 (ii) and then we can conclude peel(Ŝn (rn )) 6= ∅ eventually, with probability 1.
ii) Notice that we can use Theorem 1 (ii) indeed, as M is a C2 compact manifold of Rd by (Thäle,
2008, Prop. 14) it has a positive reach and, thus, it satisfies the outside rolling ball condition
9

(for some radius r > 0). Then it remains to be proved that rn ≤ r for n large enough. Let us
endow M with the standard Riemannian structure, where a local metric is defined on every
tangent space just by restricting on it the standard inner product on Rd . Under smoothness
assumptions, the Riemannian measure induced by such a metric on the manifold M agrees
with the d0 -dimensional Hausdorff measure on M (this is just a particular case of the Area
Formula; see (Federer, 1969, 3.2.46)). So we may use Theorem 5.1 in Penrose (1999). As a
consequence of that result
1/d0 !

log n
, a.s.,
(9)
max min γ(Xi , Xj ) = O
i
j6=i
n
where γ denotes the geodesic distance on M associated with the Riemannian structure.
Now, since the Euclidean distance is smaller than the geodesic distance, we have for all i, j,
kXj − Xi k ≤ γ(Xi , Xj ) and minj γ(Xi , Xj ) = γ(Xi , Xi0 ) ≥ kXi − Xi0 k ≥
minj kXi − Xj k and finally maxi minj6=i γ(Xi , Xj ) ≥ maxi minj6=i kXi − Xj k. Finally from
a.s.
(9) we have maxi minj6=i kXj − Xi k −→ 0, which concludes the proof.

3.2

The case of noisy data: the “parallel” model

The following two theorems are meaningful in at least two ways. On the one hand, if we know the
amount of noise (R1 in the notation introduced before), these results can be used to detect whether
or not the support M of the original sample is full dimensional (see (11) and (15)).
On the other hand, in the lower dimensional setting, they give an easy-to-implement way to
estimate R1 (see (10) and (14)).
c n denotes a consistent estimator
Observe that when M̊ = ∅, then R1 = maxx∈S d(x, ∂S). If ∂S
c n ).
of ∂B(M, R1 ), a natural plug-in estimator for R1 is maxYi ∈Yn d(Yn , ∂S
c
In Theorem 3 ∂S n is constructed in terms of the set of the centers of the boundary balls, while
in Theorem 4 we use the boundary of the r-convex hull. The second theorem is stronger than the
first one in several aspects: the parameter choice is easier and the convergence rate is better (and
does not depend on the parameter). The price to pay is computational since the corresponding
statistic is much more difficult to implement; see Section 6.
Theorem 3. Let M ⊂ Rd be a compact set such that reach(M) = R0 > 0. Let R1 be a constant
with 0 < R1 < R0 and let Yn = {Y1 , . . . , Yn } be an iid sample of a distribution PY with support
S = B(M, R1 ), absolutely continuous with respect to the Lebesgue measure, whose density f is
bounded from below by f0 > 0. Let εn = c(log(n)/n)1/d , with c > (6/(f0 ωd ))1/d , and let us denote
R̂n = maxYi ∈Yn minj∈Ibb kYi − Yj k where Ibb = {j : B(Yj , εn ) is a boundary ball}.
i) if M̊ = ∅ then, with probability one,
R̂n − R1 ≤ 2εn for n large enough,

(10)

ii) if M̊ 6= ∅ then there exists C > 0 such that, with probability one
R̂n − R1 > C for n large enough.
10

(11)

Proof.
i) Observe, that, since M̊ = ∅, R1 = maxx∈S d(x, ∂S). Then, the proposed estimator R̂n
is quite natural: roughly speaking, we may consider that the set of centres of the boundary
balls is an estimator of the boundary of S so that the maximum distance from the sample
points to these centres is a natural estimator of the parameter R1 that measures the “thickness” of S. We will now use Corollary 4.9 in Federer (1959); this result establishes that for
r > 0, the r-parallel set of a non-empty closed set A fulfills reach(B(A, r)) ≥ reach(A) − r.
Also, reach{x : d(x, A) ≥ r} ≥ r. Then, in our case, for S = B(M, R1 ), this result yields
reach(S) ≥ R0 − R1 > 0 and reach(S c ) ≥ R1 . By Proposition 1 and 2 in Cuevas, Fraiman
and Pateiro-López (2012) S fulfils the inner and outer rolling condition.
Another consequence of the positive reach of S is that it has a Lebesgue null boundary and
thus, with probability one for all i, Yi ∈ S̊ and then, with probability one
Ŝn (εn ) ⊂ B(S̊, εn ).

(12)

Since reach(S c ) > 0, by Proposition 1 S is standard with respect to PX for any constant
δ < f0 /3 (see Definition 4).
Now, we will use Theorem 4 and Proposition 1 in Cuevas and Rodriguez-Casal (2004); according to these result, if S is partially expandable and it is standard with respect to PX
(both conditions are satisfied in our case) we have for large enough n, with probability one,
S ⊂ Ŝn (εn ),

(13)

for a choice of εn as that indicated in the above statement of the theorem.
For all x ∈ S let us consider z ∈ ∂S a point such that kx − zk = d(x, ∂S) and t = z + εn η
where η = η(z) is a normal vector to ∂S at z that points outside S (η can be defined according
to Definition 4.4 and Theorem 4.8 (12) in Federer (1959)). Notice that the metric projection
of t on S is z thus d(t, S) = εn so, according to (12), with probability one t ∈
/ Ŝn (εn ). The
point z belongs to S so, by (13), with probability one for n large enough z ∈ Ŝn (εn ). We
thus conclude [t, z] ∩ ∂ Ŝn (εn ) 6= ∅, with probability one, for n large enough. Let then consider
y ∈ [t, z] ∩ ∂ Ŝn (εn ), as y ∈ ∂ Ŝn (εn ) there exists i ∈ Ibb such that y ∈ ∂B(Yi , εn ) and, as
y ∈ [t, z], ky − zk ≤ εn thus kx − Yi k ≤ kx − zk + kz − yk + ky − Yi k ≤ d(x, ∂S) + 2εn .
To summarize we just have proved that: for all x ∈ S there exits i ∈ Ibb such that kx −
Yi k ≤ d(x, ∂S) + 2εn thus for all x ∈ S : mini∈Ibb kx − Yi k ≤ d(x, ∂S) + 2εn . To conclude
maxj mini∈Ibb kYj − Yi k ≤ maxj d(Yj , ∂S) + 2εn ≤ maxx∈S d(x, ∂S) + 2εn = R1 + 2εn (with
probability one for n large enough).
The reverse inequality is easier to prove, let us consider x0 ∈ S such that d(x0 , ∂S) = R1 ,
notice that, by (13) (with probability one for n large enough) there exists i0 such that
kx0 − Yi0 k ≤ εn . By triangular inequality B(Yi0 , R1 − εn ) ⊂ S and by (13) we also have
B(Yi0 , R1 − εn ) ⊂ Ŝn (εn ) thus mini∈Ibb {kYi0 − Yi k} ≥ R1 − 2εn . Then we have proved
maxj mini∈Ibb {kYi − Yj k} ≥ R1 − 2εn . This concludes the proof of (10).
ii) Observe that to prove i) we proved that |R̂n −maxx∈S d(x, ∂S)| < 2εn . Then, with probability
one, for n large enough, |R̂n − R1 | > |c1 − R1 |/2 = C > 0, where c1 = maxx∈∂S d(x, ∂S).

11

Theorem 4. Let M ⊂ Rd be a compact set such that reach(M) = R0 > 0. Suppose that the sample
Yn = {Y1 , . . . , Yn } has a distribution with support S = B(M, R1 ) for some R1 < R0 with a density
bounded from below by a constant f0 > 0. Let us denote R̃n = maxi d(Yi , ∂Cr (Yn )) where Cr (Yn )
denotes the r-convex hull of the sample, as defined in (2) for r ≤ min(R1 , R0 − R1 ).
i) If M̊ = ∅ and for some d0 < d M has a finite, strictly positive d0 -dimensional Minkowski
content, then, with probability one,
R̃n − R1 = O log(n)/n

min(1/(d−d0 ),2/(d+1))

,

(14)

ii) if M̊ 6= ∅, then there exists C > 0 such that, with probability one
R̃n − R1 > C for n large enough.

(15)

Proof. Again, as shown in the proof of Theorem 3, reach(B(M, R1 )) ≥ reach(M) − R1 = R0 − R1 ;
also reach(B(M, R1 )c ) ≥ R1 . We now use Proposition 1 in Cuevas, Fraiman and Pateiro-López
(2012); this result establishes that reach(S) ≥ r implies that S is r-convex. According to this result
we may conclude that B(M, R1 ) and B(M, R1 )c are both r-convex for r = min(R1 , R0 − R1 ) >
0. Note, in addition, that by construction of S = B(M, R1 ) we have that S̊i 6= ∅ for every
path-connected component Si ⊂ S. So, we can use Theorem 3 in Rodrı́guez-Casal (2007) (which
establishes the rates of convergence in the estimation of an r-convex set using the r-convex hull of
the sample) to conclude


dH ∂Cr (Yn ), ∂S = O (log(n)/n)2/(d+1) , a.s.
(16)
Let us now prove that, with probability one, for n large enough,

B M, R1 − dH (∂Cr (Yn ), ∂S) ⊂ Cr (Yn ).
(17)

Proceeding by contradiction, let xn ∈ B M, R1 − dH (∂Cr (Yn ), ∂S) such that xn ∈
/ Cr (Yn ), let yn
be the projection of xn onto M. It is easy to see that, for n large enough, with probability one,
M ⊂ Cr (Yn ) then yn ∈ Cr (Yn ). Observe that, from the definition of parallel set,



B ∂S, dH (∂Cr (Yn ), ∂S) = B M, R1 + dH (∂Cr (Yn ), ∂S) \ B̊ M, R1 − dH (∂Cr (Yn ), ∂S) , (18)
then, there exists zn ∈ ∂Cr (Yn ) ∩ (xn , yn ), (xn , yn ) being the open segment joining xn and yn , but
then by (18), d(zn , ∂S) > dH (∂Cr (Yn ), ∂S) which is a contradiction; this concludes the proof of
(17).
Now we can prove i). Suppose that M̊ = ∅. Then R1 = maxx∈S d(x, ∂S) = maxx∈M d(x, ∂S) =
dH (M, ∂S). Also, as Cr (Yn ) ⊂ S thus
R̃n ≤ R1 .
(19)
For every observation Yi let mi denote its projection on M; by (17) we have d(mi , ∂Cr (Yn )) ≥
R1 − dH (∂Cr (Yn ), ∂S) so that, from triangular inequality,
d(mi , Yi ) + d(Yi , ∂Cr (Yn )) ≥ R1 − dH (∂Cr (Yn ), ∂S). Thus
R̃n ≥ R1 − dH (∂Cr (Yn ), ∂S) − min d(Yi , M).
i

12

(20)

We now analyze the order of the last term in (20). From the assumption of finiteness of the
Minkowski content of M, given a constant A > 0 there exists a constant cM > 0 such that for n
large enough,


0 
µd B M, (A log(n)/n)1/(d−d ) ≥ cM A log(n)/n.
Thus,
n
0 
PX ∀i, d(Yi , M) ≥ (A log(n)/n)1/(d−d ) ≤ 1 − f0 cM A(log(n)/n) ≤ n−f0 cM A .
If we take A > 1/(f0 cM ) we obtain, from Borel-Cantelli lemma,


0
min d(Yi , M) = O (log(n)/n)1/(d−d ) , a.s.
i

(21)

Finally, (14) is a direct consequence of (16), (19), (20) and (21).
The proof of ii) is obtained as in Theorem 3 part ii).
Remark 2. The assumption imposed on M in part (i) can be seen as an statement of d0 -dimensionality. For example if we assume that M is rectifiable then, from Theorem 3.2.39 in Federer (1969),
0
the d0 -dimensional Hausdorff measure of M, Hd (M) coincides with the corresponding Minkowski
d0
content. Hence 0 < H (M) < ∞ and, according to expression (4), this entails dimH (M) = d0 .

3.3

An index of closeness to lower dimensionality

[
[
According to Theorem 3 in the case R1 = 0, the value 2R̂n /diam(M)
(where diam(M)
= maxi6=j
kXi − Xj k) can be seen as an index of departure from low-dimensionality. Observe that if M = M̊
[
[
we get 2R̂n /diam(M)
→ 1, a.s. and if M has empty interior, 2R̂n /diam(M)
→ 0 a.s.

4

A method to partially denoise the sample data

There are several situations in which we may speak of “noise in the data”: we could first mention
the “outlier model” in which the noise is given by a certain amount of outlying observations, far
away from the central core of the data. Also, we might have a situation in which every observation
is perturbed with a small amount of noise. We will present in this section a denoising proposal,
dealing with the latter case and related to the models considered in the previous sections. Before
presenting this proposal we will let us briefly comment some references that, from different points
of view, deal with the problem of noisy samples in geometric/statistical contexts.
Sometimes the term “denoise” is replaced with “declutter” in the literature on stochastic geometry. A general “declutter algorithm”, depending on a single parameter has bee recently proposed
in Buchet et al. (2015). This paper includes also a short interesting overview of the literature on
the topic. In particular, the authors mention two main general declutter methodologies, namely
procedures based on deconvolution (where the distribution generating the noise appears convolved
with the “true” underlying model), see Caillerie et al. (2013), and those based on thresholding,
Ozertem and Erdogmus (2011), where the data are “cleaned” using an auxiliary density estimator.
Another interesting approach to the denoising idea, different to that followed in this paper,
is given in Chazal et al. (2011). These authors tackle the identification of some geometric or
13

topological features from samples that could include outliers. Again, they use the r-offsets (that is
the r-parallel sets of the sample data and the target set S) as a fundamental tool. Such r-offsets
are represented in terms of sublevel sets of appropriate functions, defined as a short of distance
between a point and a set. The main contribution in the mentioned paper is to robustify (against
outliers) such distance functions, and the corresponding sublevel sets, by replacing them with a new
function that can be seen as a distance between a point and a probability distribution. A recent
related approach, based on the use of kernel density estimates, can be found in Phillips et al (2015).
The denoising idea is also alike to that of identifying (from a sample of points on the set S) the
“central part” of the set, often called “skeleton” or “medial axis” of S. See Cuevas et al. (2014) and
references therein. In fact, the possible idea of defining a denoising procedure in terms of distance
to the medial axis, could be seen as a sort of “dual” version of the method proposed in the present
paper, based on the distance to the estimated boundary.
Closely related ideas, ultimately relying on the notion of medial axis, are considered in Dey
et al. (2015), where a method for “sparsification” of a sample is proposed. The aim is also (as
in the denoising case) to retain a subset of the original sample, which is assumed to be drawn on
a manifold. In authors’ words: “We sparsify the data so that the resulting set is locally uniform
and is still good for homology inference”. The proposed method is based on the “lean feature size”
distance, which is intermediate between the well-know “local feature size” (defined in terms of the
medial axis) and the “weak local feature size”.

4.1

The algorithm

Let M ⊂ Rd be a compact set with reach(M) = R0 > 0. Let Yn = {Y1 , . . . , Yn } be an iid sample
of a random variable Y , with absolutely continuous distribution whose support is the parallel set
S = B(M, R1 ) for some 0 < R1 < R0 . We now propose an algorithm to get from Yn , a “partially denoised” sample of points Zm that allow us to estimate the target set M, as established in Theorem
5.
The procedure works as follows:
1. Take suitable auxiliary estimators for S and R1 . Let Ŝn be an estimator of S (based on Yn )
such that dH (∂ Ŝn , ∂S) < an eventually a.s., for some an → 0. Let R̂n be an estimator of R1
such that |R̂n − R1 | ≤ en eventually a.s. for some en → 0.
2. Select a λ-subsample far from the estimated boundary of S. Take λ ∈ (0, 1) and define
Yλm = {Y1λ , . . . , Ymλ } ⊂ Yn where Yiλ ∈ Yλm if and only if d(Yiλ , ∂ Ŝn ) > λR̂n .
3. The projection + translation stage. For every Yiλ ∈ Yλm , we define Zm = {Z1 , . . . , Zm } as
follows,
Yiλ − π∂ Ŝn (Yiλ )
,
(22)
Zi = π∂ Ŝn (Yiλ ) + R̂n λ
kYi − π∂ Ŝn (Yiλ )k
where π∂ Ŝn (Yiλ ) denotes the metric projection of Yiλ on ∂ Ŝn .

4.2

Asymptotics

The following result shows that the above de-noising procedure allows us to asymptotically recover
the “inner set” M.

14

Theorem 5. Let M ⊂ Rd be a compact set with reach(M) = R0 > 0. Let Yn = {Y1 , . . . , Yn }
be an iid sample of Y , with support S = B(M, R1 ) for some 0 < R1 < R0 , and distribution PY ,
absolutely continuous with respect to the Lebesgue measure, whose density f , is bounded from below
by f0 > 0. Let an and en be, respectively, the convergence ratesin the estimation of ∂S, as defined
1/3
in the algorithm of Sunsection 4.1. Then, there exists bn = O max(an , en , εn ) such that, with
probability one, for n large enough,
dH (Zm , M) ≤ bn
where εn = c(log(n)/n)1/d with c > (6/(f0 ωd ))1/d and Zm denotes the denoised sample defined in
the algorithm.
Proof. First let us prove that dH (Yn , S) ≤ εn eventually a.s.. To do that, we will use Theorem 4
in Cuevas and Rodriguez-Casal (2004) as it was done in Theorem 3. By Corollary 4.9 in Federer
(1959), reach(S c ) > 0 and then by Proposition 1, S is standard. Again by Corollary 4.9 in Federer
(1959) reach(∂S) > 0, which entails, by Proposition 2 that S fulfils the outside rolling condition.
Using Theorem 4 and Proposition 1 in Cuevas and Rodriguez-Casal (2004) we conclude that,
dH (Yn , S) ≤ εn eventually a.s..
Let us fix Yiλ ∈ Yλm .
Let us denote l = kYiλ − π∂S (Yiλ )k and ηi = (Yiλ − π∂S (Yiλ ))/l, let us introduce two estimators
λ
λ
λ
λ
ˆ
ˆl = kY λ − π
i
∂ Ŝn (Yi )k and η̂i = (Yi − π∂ Ŝn (Yi ))/l. With this notation Zi = π∂ Ŝn (Yi ) + R̂n η̂i .
Recall that since reach(M) > R1 we have (by Corollary 4.9 in Federer (1959)) that πM (Yiλ ) =
π∂S (Yiλ ) + R1 ηi ,
For all Yiλ there exists a point x ∈ ∂ Ŝn with ||x − π∂S (Yiλ )|| ≤ an so that, by triangular
inequality: d(Yiλ , ∂ Ŝn ) ≤ l + an that is,
π∂ Ŝn (Yiλ ) ∈ B(Yiλ , l + an ).

(23)

π∂ Ŝn (Yiλ ) ∈ B(Yiλ , l − an )c .

(24)

Now let us prove that
∈ B(Yiλ , l−an ), since dH (∂Sn , ∂S) < an there exists t ∈ ∂S
then l = d(Yiλ , ∂S) ≤ kYiλ − π∂ Ŝn (Yiλ )k + kπ∂ Ŝn (Yiλ ) − tk < l.

π∂ Ŝn (Yiλ )

Suppose by contradiction that
such that kt − π∂ Ŝn (Yiλ )k < an , but
That concludes the proof of (24).
By (23) and (24) we have:

l − an ≤ ˆl ≤ l + an .

(25)

π∂ Ŝn (Yiλ ) ∈ B(πM (Yiλ ), R1 − an )c .

(26)

In the same way it can be proved that

Let us prove that there exists C0 > 0 such that
for all Yiλ ∈ Yλm , kZi − πM (Yiλ )k ≤ C0

q

2/3

1/3

an + an en + e2n .

1/3

(27)
1/3

First consider the case 0 ≤ R1 − l ≤ an , which implies that kYiλ − πM (Yiλ )k ≤ an . Notice
1/3
that, by (25), kYiλ − Zi k = |R̂n − ˆl| ≤ an + en + an , finally we get
kZi − πM (Yiλ )k ≤ 2a1/3
n + an + en .
15

(28)

1/3

Now we consider the case R1 − l ≥ an , recall that by (23) and (26) we have.
π∂ Ŝn (Yiλ ) ∈ B(Yiλ , l + an ) \ B(πM (Y1λ ), R1 − an ).

(29)

kπ∂ Ŝn (Yiλ ) − π∂S (Yiλ )k

takes its largest possible

In Figure 3 it is represented the case for which
value.

Figure 3: In solid black line B(πM (Y1λ ), R1 − an ), in dashed line B(Yiλ , ˆl) and B(Yiλ , l).
To find an upper bound for such value, let us first note that the points π∂ Ŝn (Yiλ ), Yiλ and
π∂ Ŝn (Yiλ ) + R1 η̂i are aligned. And the points π∂S (Yiλ ), Yiλ and πM (Yiλ ), are aligned. So all of them
are in the same plane Π. Let us now apply a translation T in order to get, T (π∂S (Y1λ )) = 0. Let
us consider in Π a coordinate system (x, y) such that πM (Yiλ ) = (0, −R1 ).
Let (x1 , y1 ) be the coordinates of the point π∂ Ŝn (Yiλ ). From (29) we get
x21 + (y1 + l)2 ≤ (l + an )2
x21

2

(30)
2

+ (y1 + R1 ) ≥ (R1 − an )

(31)

If we multiply (31) by −l, we get −l(x21 + y12 ) − 2y1 lR1 ≤ −la2n + 2an lR1 and if we multiply (30)
by R1 we get R1 (x21 + y12 ) + 2y1 lR1 ≤ 2R1 an l + a2n R1 . Then, if we sum this two inequalities we get,
x21 + y12 ≤

4lR1
2
an + a2n ≤ 4R12 a2/3
n + an .
R1 − l

Notice that Zi ∈ Π, let us denote (x, y) the coordinates of Zi in Π, then
x = x1 − R̂n
and
y = y1 − R̂n

kYiλ

x1
x1
= x1 − R̂n
λ
ˆl
− π∂ Ŝn (Yi )k

l + y1
l + y1
= y1 − R̂n
.
ˆl
kYiλ − π∂ Ŝn (Yiλ )k
16

(32)

Since the coordinates of πM (Yiλ ) are (0, −R1 ) we get that
kZi −

πM (Yiλ )k2

2

= k(x, y + R1 )k =

(x21

+

y12 )

ˆl − R̂n
ˆl

!2


2
l
+ R1 − R̂n
ˆl
+ 2y1


ˆl − R̂n 
l
R1 − R̂n
. (33)
ˆl
ˆl

Observe that |l − ˆl| ≤ an and |R1 − R̂n | ≤ en eventually almost surely. We can bound | l̂−l̂R̂n | ≤ 2
and ˆl ≥ λR1 /2, then
R1 − R̂n

R1 (ˆl − l) − l(R̂n − R1 )
an + en
l
=
≤2
.
ˆl
ˆl
λ

(34)

1/3

Finally by equations (32), (33) and (34), if R1 − l ≥ an (note that this is used in the proof of
(32)), there exists C0 such that
q
1/3
2/3
(35)
kZi − πM (Yiλ )k ≤ C0 an + an en + e2n .
1/3

where (see (32)) we are using y1 = O(an ) here. That concludes the proof of (27).
Let us finally prove that M ⊂ B(Zm , an +en +2εn ) eventually, a.s. As indicated at the beginning
of the proof, we have dH (Yn , S) ≤ εn eventually a.s., thus for all x ∈ M, there exists Yi ∈ Yn such
that kx − Yi k ≤ εn . For n large enough we have Yi ∈ Yλm . Following the same ideas used to prove
(28) we obtain kZi − Yi k ≤ εn + an + en . By triangular inequality we get
M ⊂ B(Zm , an + en + 2εn ) eventually, a.s.

(36)

Combining (28), (35) and (36) we obtain,


q


1/3
2/3
2 , ε ) = O max(a1/3 , e , ε ) .
dH (Zm , M) = O max(a1/3
,
e
,
e
+
e
+
a
a
n
n
n
n
n
n
n
n
n
n

Remark 3. Note that, when M̊ = ∅, the result simplifies since, according to Theorem 3 we can
take en = 2n and, according to Cuevas and Rodriguez-Casal (2004) (Prop. 1 and Th. 4) an = n .
1/3
Therefore, in this case bn = an .
The two following corollaries give the exact convergence rate for the denoising process introduced
before, using the centers of the boundary balls (Corollary 1), and the boundary of the r-convex hull
(Corollary 2), as estimators of the boundary of the support.
Corollary 1. Let M ⊂ Rd be a compact set such that reach(M) = R0 > 0. Let Yn = {Y1 , . . . , Yn }
be an iid sample of a distribution PY with support B(M, R1 ) for some 0 < R1 < R0 . Assume that
PY is absolutely continuous with respect to the Lebesgue measure and the density f , is bounded from
below by a constant f0 > 0. Let εn = c(log(n)/n)1/d and c > (6/(f0 ωd ))1/d .
17

Given λ ∈ (0, 1), let Zn be the points obtained after the denoising process using R̂n to estimate
R1 and {Yi , i ∈ Ibb } as an estimator of ∂S where Ibb = {j : B(Yj , εn ) is a boundary ball}. Then,

dH (Zm , M) = O (log(n)/n)1/(3d) , a.s.
Using the assumption of r-convexity for M (see Definitions 2 and 3 and the subsequent comments) in the construction of the set estimator, we can replace R̂n with R̃n (see Theorem 4). Then,
at the cost of some additional complexity in the numerical implementation, a faster convergence
rate can be obtained. This is made explicit in the following result.
Corollary 2. Let M ⊂ Rd be a compact d0 -dimensional set (in the sense of Theorem 4, i) such
that reach(M) = R0 > 0. Let Yn = {Y1 , . . . , Yn } be an iid sample of a distribution PY with support
B(M, R1 ) for some 0 < R1 < R0 . Assume that PY is absolutely continuous with respect to the
Lebesgue measure and the density f , is bounded from below by a constant f0 > 0.
For a given λ ∈ (0, 1), let Zn be the set of the points obtained after the denoising process, based
on the estimator ∂Cr (Yn ) of ∂S (for some r with 0 < r < min(R0 − R1 , R1 )) and the estimator R̃n
of R1 .
Then,

dH (Zm , M) = O (log(n)/n)2/(3(d+1)) a.s.

5
5.1

Estimation of lower-dimensional measures
Noiseless model

In this section, we go back to the noiseless model, that is, we assume that the sample points
X1 , . . . , Xn are drawn according to a distribution whose support is M. The target is to estimate
the d0 -dimensional Minkowski content of M, as given by
lim

→0

µd (B(M, ))
= L0 (M) < ∞.
ωd−d0 d−d0

(37)

This is just (alongside with Hausdorff measure, among others) one of the possible ways to measure
lower-dimensional sets; see Mattila (1995) for background.
In recent years, the problem of estimating the d0 -dimensional measures of a compact set from a
random sample has received some attention in the literature. The simplest situation corresponds to
the full-dimensional case d0 = d. Any estimator Mn of M consistent with respect to the distance in
measure, that is µd (Mn ∆M) → 0 (in prob. or a.s., where ∆ stands for the symmetric difference),
will provide a consistent estimator for µd (M). In fact, as a consequence of Th. 1 in Devroye and
Wise (1980) (recall that S is compact here) this will the always the case (in probability) when Mn
is the offset estimator (6), provided that µd is absolutely continuous (on M) with respect to PX
together with rn → 0 and nrnd → ∞.
Other more specific estimators of µd (M) can be obtained by imposing some shape assumptions
on M, such as convexity or r-convexity, which are incorporated to the estimator Mn ; see AriasCastro et al. (2016), Baldin and Reiss (2016), Pardon (2011).
Regarding the estimation of lower-dimensional measures, with d0 < d, the available literature
mostly concerns the problem of estimating L0 (M), M being the boundary of some compact support
18

S. The sample model is also a bit different, as it is assumed that we have sample points inside and
outside S. Here, typically, d0 = d − 1; see Cuevas et al. (2007), Cuevas et al. (2013), Jiménez and
Yukich (2011).
Again, in the case M = ∂S with d = 2, under the extra assumption of r-convexity for S, the
consistency of the plug-in estimator L0 (∂Cr (Xn )) of L0 (∂S) is proved in Cuevas, Fraiman and
Pateiro-López (2012) under the usual inside model (points taken on S). Finally, in Berrendero
et al. (2014), assuming an outside model (points drawn in B(S, R) \ S), estimators of µd (S) and
L0 (∂S) are proposed, under the condition of polynomial volume for S
From the perspective of the above references, our contribution here (Th. 6 below) could be
seen as a sort of lower-dimensional extension of the mentioned results of type µd (Mn ) → µd (M)
regarding volume estimation. But, obviously, in this case the Lebesgue measure µd must be replaced
with a lower-dimensional counterpart, such as the Minkowski content (37). We will also need the
following lower-dimensional version of the standardness property given in Definition 3.
Definition 7. A Borel probability measure defined on a d0 -dimensional set M ⊂ Rd (considered
with the topology induced by Rd ) is said to be standard with respect to the d0 -dimensional Lebesgue
measure µd0 if there exist λ and δ such that, for all x ∈ M,
PX (B(x, r)) = P(X ∈ B(x, r) ∩ M) ≥ δµd0 (B(x, r)), for 0 ≤ r ≤ λ.
Remark 4. Observe that, by Lemma 5.3 in (Niyogi, Smale and Weinberger (2008)) this condition
is fulfilled if PX has a density f bounded from below and M is a manifold with positive condition
number (also known as positive reach). Standardness of the distribution has also been used in ?,
Chazal et al. (2015), Aamari and Levrard (2015).
Theorem 6. Let Xn = {X1 , . . . , Xn } be an iid sample drawn according to a distribution PX on a
set M ⊂ Rd . Let us assume that the distribution PX is standard with respect to the d0 -dimensional
Lebesgue measure (see 7) and that there exists the d0 Minkowski content L0 (M) < ∞ of M, given
0
by (37). Let us take rn such that rn → 0 and (log(n)/n)1/d = o(rn ), then
(i)
lim

n→∞


µd B(Xn , rn )
0

ωd−d0 rnd−d

= L0 (M)

a.s.

(38)

(ii) If reach(M) = R0 > 0, then

µd B(Xn , rn )
0
ωd−d0 rnd−d

where βn = O log(n)/n

1/d0

β

n
− L0 (M) = O
+ rn ,
rn

.

Proof. (i) First we will see that, following the same ideas as in Theorem 3 in Cuevas and RodriguezCasal (2004) it can be readily proved that, with probability one, for n large enough,
dH (Xn , M) ≤ Cβn .

(39)

for some large enough constant C > 0. In order to see (39), let us consider M∆ a minimal covering
0
of M, with balls of radius ∆ centred in N∆ points belonging to M. Let us prove that N∆ = O(∆−d ).
Indeed, since M∆ is a minimal covering it is clear that µd (B(M, ∆)) ≥ N∆ ωd (∆/2)d , and then
19

0
µd (B(M, ∆))
N∆ ωd (∆/2)d
≥
= c 1 N∆ ∆ d ,
0
0
d−d
d−d
0
0
ωd−d ∆
ωd−d ∆
0

c1 being a positive constant. Since there exists L0 (M) it follows that N∆ = O(∆−d ). Then the
0
proof of (39) follows easily from the standardness of PX and N∆ = O(∆−d ), so we will omit it.
Now, in order to prove (38), let us first prove that, if we take αn = 1 − Cβn /rn ,
B(M, αn rn ) ⊂ B(Xn , rn ) ⊂ B(M, rn ) a.s..

(40)

To prove this, consider xn ∈ B(M, αn rn ), then there exists tn ∈ M such that xn ∈ B(tn , αn rn ).
Since dH (Xn , M) ≤ Cβn there exists yn ∈ B(tn , Cβn ), yn ∈ Xn . It is enough to prove that
xn ∈ B(yn , rn ). But this follows from the fact that, eventually a.s.,
kyn − xn k ≤ kxn − tn k + ktn − yn k ≤ αn rn + Cβn = rn .
Then, from (40)

0
αnd−d


µ B(M, αn rn )
0

0

ωd−d0 αnd−d rnd−d

− L0 (M) ≤

µ B(Xn , rn )
0

ωd−d0 rnd−d


− L0 (M) ≤


µ B(M, rn )
0

ωd−d0 rnd−d

− L0 (M).

(41)

Since there exists L0 (M), the right hand side of (41) goes to zero. To prove that the left hand side
0
of (41) goes to zero, let us observe that, as αn = 1 − Cβn /rn , and αnd−d = 1 − O(βn /rn ), then


µ B(M, αn rn )
d−d0 µ B(M, αn rn )
αn
(42)
0 − L0 (M) =
0 − O(βn /rn ) − L0 (M),
0
0
ωd−d0 αnd−d rnd−d
ωd−d0 αnd−d rnd−d
since αn → 1 and βn /rn → 0 we get
lim

n→∞

µ B(M, αn rn )



0

ωd−d0 rnd−d

= L0 (M) a.s..

(ii) The assumption reach(M) = R0 > 0 allow us to ensure
 that M has a polynomial volume in the
interval [0, r0 ). This means that, for r < R0 , µ B(M, r) = Pd (r) where Pd (r) is a polynomial of
degree at most d; this is a classical result due to Federer (1959, Th. 5.6). Since we assume that the
d0 -Minkowski content L0 (M) is finite, this polynomial volume condition entails that the coefficient
to the d − d0 term is ωd−d0 L0 (M). Then,
µ(B(M, rn ))
= L0 (M) + rn A(M) + o(rn ),
0
ωd−d0 rnd−d
for some constant A(M). Now the proof follows from (41) and (42).
Remark 5. In the case of sets with positive reach, part (b) suggests to take rn2 = maxi minj6=i kXi −
0
Xj k since we know by Theorem 1 in Penrose (1999) that rn2 = O (log(n)/n)1/d ) that gives the
optimal convergence rate.

20

5.2

Noisy Model

The estimation of the Minkowski content in the noisy model has been tackled in Berrendero et al.
(2014), where the random sample is assumed to have uniform distribution in the parallel set U . In
this section we will see that even if the sample is not uniformly distributed on B(M, R1 ) for some
0 < R1 < R0 = reach(M), it is still possible, by applying first the de-noising algorithm introduced
in Section 4, to estimate L0 (M). Following the notation in Section 4, let Yn be an iid sample of a
random variable Y with support B(M, R1 ), let us denote Zm the de-noised sample defined by (22).
The estimator is defined as in (38) but replacing Xn with Zm . Although the subset Zm is not an iid
sample (since the random variables Zi are not independent), the consistency is based on the fact
that Zm converge in Hausdorff distance to M, as we will prove in the following theorem.
1/3

Theorem 7. With the hypothesis and notation of Theorem 5, if max(an , en , εn ) = o(rn ) where
εn = c(log(n)/n)1/d with c > (6/(f0 ωd ))1/d . Then,
lim

n→∞

µd (B(Zm , rn ))
= L0 (M)
0
ωd−d0 rnd−d

a.s..

(43)

Proof. The proof is analogous to the one in Theorem 6. Observe that in Theorem 5 we proved that
1/3
dH (Zm , M) ≤ bn , for some bn = O(max(an , en , εn )), then bn /rn → 0. As we did Theorem 6 if we
take αn = 1 − bn /rn , then, with probability one,
B(M, αn rn ) ⊂ B(Zm , rn ) ⊂ B(M, rn ),
then we get
0
αnd−d


µ B(M, αn rn )
0

ωd−d0 αnd−d rnd−d

0

− L0 (M) ≤


µ B(Zn , rn )
0

ωd−d0 rnd−d

− L0 (M) ≤


µ B(M, rn )
0

ωd−d0 rnd−d

− L0 (M),

from where it follows
0
αnd−d


µ B(M, αn rn )
0

0

ωd−d0 αnd−d rnd−d

− L0 (M) =


µ B(M, αn rn )
0

0

ωd−d0 αnd−d rnd−d

− O(bn /rn ) − L0 (M).

Since αn → 1 and bn /rn → 0 we get (43).

6

Computational aspects and simulations

We discuss here some theoretical and practical aspects regarding the implementation of the algorithms. We present also some simulations and numerical examples.

6.1

Identifying the boundary balls

The cornerstone of the practical use of Theorem 1 is the effective identification of the boundary
balls. The following proposition provides the basis for such identification, in terms of the Voronoi
cells of the sample points. Recall that, given a finite set {x1 , . . . , xn }, the Voronoi cell associated
with the point xi is defined by Vor(xi ) = {x : d(x, xi ) ≤ d(x, xj ) for all i 6= j}.

21

Proposition 3. Let Xn = {X1 , . . . , Xn } be an iid sample of points, in Rd , drawn according to a
distribution PX , absolutely continuous with respect to the Lebesgue measure. Then, with probability
one, for all i = 1, . . . , n and all r > 0, sup{kz − Xi k, z ∈ Vor(Xi )} ≥ r if and only if B(Xi , r) is a
boundary ball for the Devroye-Wise estimator (6).
Proof. Let us take r > 0 and Xi such that there exists z ∈ ∂B(Xi , r) ∩ Vor(Xi ) 6= ∅, let us prove
that z ∈ ∂ Ŝn (r). Observe that since z ∈ Vor(Xi ), d(z, Xn \Xi ) ≥ r thus d(z, Xn ) = r. Reasoning by
˚
contradiction suppose that z ∈ Ŝn then, with probability one, there exists j0 such that z ∈ B̊(Xj0 , r)
and so kz − Xj0 k < r that is a contradiction.
Now to prove the converse implication let us assume that B(Xi , r) is a boundary ball, then
there exists z ∈ ∂B(Xi , r) such that z ∈ ∂ Ŝn (r). Let us prove that d(z, Xn \ Xi ) ≥ r (from where
it follows that z ∈ Vor(Xi ) ). Suppose that d(z, Xn \ Xi ) < r, then there exists Xj 6= Xi such that
 ˚
d(z, Xj ) < r and then B z, r − d(z, Xj ) ⊂ Ŝn (r).

6.2

An algorithm to detect empty interior in the noiseless case using
Theorem 1

In order to use in practice Theorem 1 to detect lower-dimensionality in the noiseless case, we need
to fix a sequence rn ↓ 0 under the conditions indicated in Theorem 1 (ii). Note that this requires
to assume lower bounds for the “thickness” constant ρ(M) = sup d(x, ∂M) and the standardness
constant δ (see Definition 4) as well as an upper bound for the radius of the outer rolling ball.
Now, according to Theorem 1, and Proposition 3, we will use the following algorithm.
1) For i = 1, . . . , n, let V i = {V1i , . . . Vkii } be the vertices of Vor(Xi ),
2) Let δi = sup{kz − Xi k, z ∈ Vor(Xi )} = max{kXi − Vki k, 1 ≤ k ≤ ki }, since Vor(Xi ) is a
convex polyhedron. In the case that Vor(Xi ) is an unbounded cell we put δi = ∞. Define
δ0 = mini δi .
3) Decide M̊ 6= ∅ if and only if δ0 ≥ rn .

6.3

On the estimation of the maximum distance to the boundary

Theorems 3 and 4 involve the calculation of quantities such as d(x, ∂ Ŝn (n )) and d(x, ∂Cr (Yn )),
where Ŝn (n ) is a Devroye-Wise estimator of type (6) and Cr (Yn ) is the r-convex hull (2) of Yn .
It is somewhat surprising to note that, in spite of the much simpler structure of Ŝn (n ) when compared to Cr (Yn ), the distance to the boundary d(x, ∂Cr (Yn )) can be calculated in a simpler, more
accurate way than the analogous quantity d(x, ∂ Ŝn (n )) for the Devroye-Wise estimator Ŝn (n )).
Indeed note that d(x, ∂Cr (Yn )) is relatively simple to calculate; this is done in Berrendero,
Cuevas and Pateiro-López (2012) in the two-dimensional case although can be in fact used in any
dimension. Observe first that ∂Cr (Yn )) is included in a finite union of spheres of radius r, with
centres in Z = {z1 , . . . , zm }. Then d(x, ∂Cr (Yn )) = minzi ∈Z kx − zi k − r. In order to find Z we
need to compute the Delaunay triangulation. Recall that the Delaunay triangulation, Del(Yn ), is
defined as follows. Let τ ⊂ Yn ,
\
τ ∈ Del(Yn ) if and only if
Vor(Yi ) 6= ∅.
Yi ∈τ

22

T
Observe finally, for any dimension, Yi ∈τ Vor(Yi ) 6= ∅ is a segment or a half line. If τi is the
d-dimensional simplex with vertices {Yi1 , . . . , Yid } ⊂ ∂B(zi , r), the point zi can be obtained as
T
i
Y i ∈τi Vor(Yi ) ∩ B(Y1 , r).
j

6.4

Experiments

The general aim of these experiments is not to make an extensive, systematic empirical study.
We are just trying to show that the methods and algorithm proposed here can be implemented in
practice.
Detection of full dimensionality. We consider here a simple illustration of the use of Theorem 1
and the associated algorithm. In each case, we draw 200 samples of sizes n = 50, 100, 200, 300,
400, 500, 1000, 2000, 5000, 10000 on the A-parallel set around the unit sphere, ∂B(0, 1) ⊂ Rd ; that
is, the sample data are selected on B(0, 1 + A) \ B̊(0, 1 − A). The width parameter A takes the
values A = 0, 0.01, 0.05, 0.1, . . . , 0.05. Table 1 provides the minimum sample sizes to “safely decide”
the correct answer. This means to correctly decide on, at least 190 out of 200 considered samples,
that the support is lower dimensional (in the case A = 0) or that it is full dimensional (cases with
A > 0).
We have used the boundary balls procedure (here and in the denoising experiment below for
A = 0) with r = 2 maxi (minj6=i kXj − Xi k).
The results look quite reasonable: the larger the dimension d and the smaller the width parameter A, the harder the detection problem.
A
0
0.01
0.05
0.1
0.2
0.3
0.4
0.5

d=2
≤ 50
[51, 100]
≤ 50
≤ 50
≤ 50
≤ 50
≤ 50
≤ 50

d=3
≤ 50
[1001, 2000]
[201, 300]
[51, 100]
≤ 50
≤ 50
≤ 50
≤ 50

d=4
≤ 50
> 10000
[1001, 2000]
[101, 200]
[51, 100]
[51, 100]
≤ 50
≤ 50

Table 1: Minimum sample sizes required to detect lower dimensionality for different values of the
dimension d and the width parameter A.

Denoising. We draw points on B(0, 1.3) \ B̊(0, 0.7) in R2 and R3 .
In order to evaluate the effectiveness of the denoising procedure we define the random variable
e = kY k − 1 from the denoised data Y and also from the original data. Note that the “perfect”
denoising would correspond to e = 0. The Figure 4 shows the kernel estimators of both densities
of e for the case d = 2 (left panel) and for d = 3 (right panel). These estimators for the denoised
case are based on m = 100 values of e extracted from samples of sizes n =100, 1000, 10000. The
density estimators for the initial distribution are based on samples of size 100. Clearly, when the
denoised sample of size m = 100 is based on a very large sample, with n = 10000, the denoising
process is better, as suggested by the fact that the corresponding density estimators are strongly
23

concentrated around 0. The slight asymmetry in the three dimensional case, accounts for the fact
that the “external” volume B(0, 1.3) \ B(0, 1) is larger than the “internal” one B(0, 1) \ B(0, 0.7).
30

8

init
denoised 100 pt
denoised 1000 pt
denoised 10000 pt

25

init
denoised 100 pt
denoised 1000 pt
denoised 10000 pt

7

6

20
5

15

4

3

10
2

5
1

0
−0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

0

0.4

−0.5

−0.4

−0.3

−0.2

−0.1

0

0.1

0.2

0.3

0.4

Figure 4: Estimated density functions of the random variable e = kY k − 1 for d = 2 (left) and d = 3
right, with and without denoising.
Figures 5 and 6 provide a more visual idea on the result of the denoising algorithm. They
correspond, respectively, to the set B(SL3 , 0.3) (where SL3 = {(x, y), |x|3 + |y|3 = 1}) and to
B(T, 0.3), where T is the so-called Trefoil Knot, a well-known curve with interesting topological
and geometric properties.

24

1.5

1

0.5

0

−0.5

−1

−1.5
−1.5

−1

−0.5

0

0.5

1

1.5

Figure 5: The yellow background is made of 5000 points (left) and 50000 points (right) drawn on
on B(SL3 , 0.3), with SL3 = {(x, y), |x|3 + |y|3 = 1}. The blue points are the result of the denoising
process. The black line corresponds to the original set SL3
Minkowski contents estimation. Finally in Table 3 we show, just as a tentative experiment, some
results about the Minkowki contents estimation, again in the case of noiseless data (R1 = 0) and
noisy points (with R1 =0.2) drawn around a sphere for different values for n and different dimensions.

d=2
d=3
d=4

n = 103
0.11
0.14
0.16

n = 104
0.1
0.14
0.16

n = 105
0.08
0.13
0.16

n = 106
0.07
0.12
0.15

Table 2: Radius r0 (n, d) for Minkowski contents estimation when R1 = 0.2
p For every R1 , n, d we estimate the Minkowski contents using a radius r = 0.5
maxi (minj6=i kXi − Xj k) (see Theorem 2) when R1 = 0 and with a a deterministic radius
r = r0 (n, d) ( slowly decreasing with the dimension, see Table 2) when R1 = 0.2. The values of the
estimators have been calculated via a Monte Carlo Method based on 105 points uniformly drawn on
B(0, 1+2r)\ B̊(0, 1−2r). For every R1 , n, d the experiment has been done 100 times. Table 3 entries
provide the average relative error (in percentage) in the estimation of the
boundary Minkowski conpP
2
tents L. That is, the entries are 100 · err(R1 , d) where err(R1 , d) = L1
i (Li (R1 , d) − L) /100, L
2
being the correct value of the boundary length in each case, that is L = 2π, 4π, 2π , for d = 2, 3, 4,
respectively.
Even if we disregard the intrinsic difficulties associated with the Monte Carlo approximation,
the outputs of Table 3 suggest that the denoising-based methodology for the estimation of the
Minkowski content from noisy observations, is not accurate for large dimensions. Note however that
the problem is intrinsically difficult, as shown by the convergence rates obtained in the noiseless
case. Note also that the noise level R1 = 0.2 is quite large, especially for d = 3, 4. In any case, the
25

4

4

2

2

0

0

−2

−2

−4
5

−4
5
4

4
2

0

2

0

0

0

−2
−5

−2
−5

−4

4

4

2

2

0

0

−2

−2

−4
5

−4

−4
5
4

4

2

0

2

0

0

0

−2
−5

−2
−5

−4

−4

Figure 6: The upper panel shows 5000 noisy points (left) and 50000 noisy points (right) drawn on
B(T, 0.3). The lower panel shows the result of the corresponding denoising process.
results displayed in Figure 6 suggest a quite reasonable performance of the denoising procedure,
for other descriptive or image analysis purposes. Clearly, more research would be needed to reach
more definitive conclusions.

26

d
2
2
3
3
4
4

R1
0
0.2
0
0.2
0
0.2

n = 103
0.38
27.29
4
37.03
16.1
91.37

n = 104
0.34
11.79
0.88
28.76
4.34
54.85

n = 105
0.32
5.33
0.37
19.95
1.23
26.69

n = 106
0.3
2.37
0.32
11.35
0.45
25.88

Table 3: Relative errors (in percentage) for Minkowski contents estimation

Acknowledgements
This research has been partially supported by MATH-AmSud grant 16-MATH-05 SM-HCD-HDD
(C. Aaron and A. Cholaquidis) and Spanish grant MTM2016-78751-P (A. Cuevas). We are grateful
to Luis Guijarro and Jesús Gonzalo (Dept. Mathematics, UAM, Madrid) for useful conversations
and advice.

References
Aamari, E. and Levrard, C. (2015). Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction. arXiv preprint arXiv:1512.02857v1.
Adler, R.J., Krishnan, S.R., Taylor, J.E. and Weinberger, S. (2015). Convergence of the reach for
a sequence of Gaussian-embedded manifolds. arXiv preprint arXiv:1503.01733.
Amenta, N., Choi, S., Dey, T.K. and Leekha, N. (2002). A simple algorithm for homeomorphic
surface reconstruction. Internat. J. Comput. Geom. Appl. 12, 125–141.
Ambrosio, L., Colesanti, A. and Villa, E. (2008). Outer Minkowski content for some classes of closed
sets. Math. Ann. 342, 727–748.
Arias-Castro, E., Pateiro-López, B. and Rodrı́guez-Casal, A. (2016). Minimax estimation of the
volume of a set with smooth boundary. arXiv preprint arXiv:1605.01333v1.
Avila A. and Lybich, M. (2007). Hausdorff dimension and conformal measures of Feigenbaum Julia
sets. J. Am. Math. Soc. 21, 305–363.
Baldin, N. and M. Reiss (2016). Unbiased estimation of the volume of a convex body. Stochastic
Process. Appl. 126, 3716–3732.
Berrendero, J.R., Cuevas, A.. and Pateiro-López, B. (2012). A multivariate uniformity test for the
case of unknown support Stat. Comput. 22, 259–271.
Berrendero, J.R., Cholaquidis, A., Cuevas, A. and Fraiman, R. (2014). A geometrically motivated
parametric model in manifold estimation. Statistics 48, 983-1004.
Boothby, W.M. (1975). An Introduction to Differentiable Manifolds and Riemannian Geometry.
Academic Press, New York.
27

Brito, M.R., Quiroz, A.J., Yukich, J.E. (2013). Intrinsic dimension identification via graph-theoretic
methods. J. Multivariate Anal. 116, 263–277.
Bhattacharya, R. and Patrangenaru, V.(2014) Statistics on manifolds and landmarks based image
analysis: A nonparametric theory with applications. J. Statist. Plann. Inf. 145, 1–22.
Buchet, M., Dey, T. K., Wang, J., and Wang, Y. (2015). Declutter and Resample: Towards parameter free denoising. arXiv preprint arXiv:1511.05479.
Caillerie, C., Chazal, F., Dedecker, J. and Michel, B.(2013) Deconvolution for the Wasserstein
metric and geometric inference. In Geometric Science of Information pp. 561–568. Springer,
Berlin, Heidelberg.
Carlsson, G. (2009). Topology and data. Bull. Amer. Math. Soc. (N.S.) 46, 255–308.
Cavanna N.J., Jahanseir, M. and Sheehy, D.R.(2015) A geometric perspective on sparse filtrations.
arXiv preprint arXiv:1506.03797.
Chazal, F. and Lieutier, A. (2005). The λ-medial axis. Graphical Models 67, 304–331.
Chazal, F., Glisse, M., Labruère, C. and Michel, B. (2015) Convergence rates for persistence diagram
estimation in topological data analysis J. Mach. Learn. Res. 16, 3603–3635.
Chazal, F., Cohen-Steiner, D., and Merigot, Q. (2011) Geometric inference for probability measures.
Found. Comput. Math. 11, 733–751.
Chen, D. and Müller, H. G. (2012). Nonlinear manifold representations for functional data. Ann.
Statist. 40, 1–29.
Cholaquidis, A., Cuevas, A. and Fraiman, R. (2014) On Poincaré cone property. Ann. Statist., 42,
255–284.
Cuevas, A. and Fraiman, R. (1997). A plug-in approach to support estimation. Ann. Statist. 25,
2300–2312.
Cuevas, A. and Rodriguez-Casal, A. (2004). On boundary estimation. Adv. in Appl. Probab. 36,
340–354.
Cuevas, A., Fraiman, R. and Rodrı́guez-Casal, A. (2007). A nonparametric approach to the estimation of lengths and surface areas. Ann. Statist. 35, 1031-1051.
Cuevas, A. and Fraiman, R. (2010). Set Estimation. In New Perspectives on Stochastic Geometry,
W.S. Kendall and I. Molchanov, eds., pp. 374–397. Oxford University Press.
Cuevas, A., Fraiman, R. and Pateiro-López, B. (2012). On statistical properties of sets fulfilling
rolling-type conditions. Adv. in Appl. Probab. 44, 311–329.
Cuevas, A., Fraiman, R. and Györfi, L. (2013). Towards a universally consistent estimator of the
Minkowski content. ESAIM: Probability and Statistics, 17, 359-369.
Cuevas, A., Pateiro-López, B. and Llop, P. (2014). On the estimation of the medial axis and inner
parallel body. J. Multivariate Anal. 129, 171–185.
28

Delicado, P. (2001) Another look at principal curves and surfaces. J. Multivariate Anal. 77, 84-116.
Devroye, L. and Wise, G. (1980) Detection of abnormal behaviour via nonparametric estimation
of the support. SIAM J. Appl. Math. 3, 480–488.
Dey, T. K., Dong, Z. and Wang, Y. (2015). Parameter-free topology inference and sparsification for
data on manifolds. arXiv preprint arXiv:1505.06462v1.
Do Carmo, M. (1992). Riemannian Geometry. Birkhäuser, Boston.
Fasy, B.T., Lecci, F., Rinaldo, R., Wasserman, L. Balakrishnan, S. and Singh, A. (2014). Confidence
sets for persistence diagrams. Ann. Statist. 42, 2301–2339.
Federer, H. (1959). Curvature measures. Trans. Amer. Math. Soc. 93, 418–491.
Federer, H. (1969). Geometric Measure Theory. Springer.
Fefferman, C., Mitter, S. and Narayanan, H. (2016). Testing the manifold hypothesis. J. Amer.
Math. Soc. 29, 983–1049.
Galbis, A. and Maestre, M. (2010). Vector Analysis Versus vector Calculus. Springer, New York.
Genovese, C.R., Perone-Pacifico, M., Verdinelli, I. and Wasserman, L. (2012a). The geometry of
nonparametric filament estimation. J. Amer. Statist. Assoc. 107, 788-799.
Genovese, C.R., Perone-Pacifico, M., Verdinelli, I. and Wasserman, L. (2012b). Minimax Manifold
Estimation. J. Mach. Learn. Res. 13, 1263-1291.
Genovese, C.R., Perone-Pacifico, M., Verdinelli, I. and Wasserman, L. (2012c). Manifold estimation
and singular deconvolution under Hausdorff loss. Ann. Statist. 40, 941-963
Hastie, T. and Stuetzle, W. (1989). Principal curves. J. Amer. Statist. Assoc. 84, 502-516.
Hirsch, M.W. Differential Topology. Springer-Verlag, New York.
Janson, S. (1987). Maximal spacings in several dimensions. Ann. Prob. 15, 274–280.
Jiménez, R. and Yukich, J.E. (2011). Nonparametric estimation of surface integrals. Ann. Statist.
39, 232-260.
Mardia, K.V. and Jupp, P.E. (2000). Directional Statistics. Wiley, Chichester.
Mattila, P. (1995). Geometry of Sets and Measures in Euclidean Spaces: Fractals and Rectifiability.
Cambridge University Press, Cambridge.
Niyogi, P., Smale, S. and Weinberger, S. (2008). Finding the Homology of Submanifolds with High
Confidence from Random Samples. Discrete Comput. Geom. 39. 419–441.
Niyogi, P., Smale, S. and Weinberger, S. (2011). A topological view of unsupervised learning from
noisy data. SIAM J. Comput. 40, 646–663.
Pateiro-López, B. and Rodrı́guez-Casal, A. (2009). Surface area estimation under convexity type
assumptions. J. Nonparametr. Stat. 21, 729–741.
29

Ozertem, U. and Erdogmus, D. (2011). Locally defined principal curves and surfaces. J. Mach.
Learn. Res. 12, 1249–1286.
Pardon, J. (2011). Central limit theorems for random polygons in an arbitrary convex set. Ann.
Probab. 39, 881–903.
Pennec, X.2006 Intrinsic Statistics on Riemannian Manifolds: Basic Tools for Geometric Measurements J. Math. Imaging Vis. 25, 127–154.
Penrose. M.D. (1999). A strong law for the largest nearest-neighbour link between random points.
J. London Math. Soc. 60, 951–960.
Phillips, J.M., Wang, B., and Zheng, Y. (2015) Geometric inference on kernel density estimates.
31st International Symposium on Computational Geometry (SoCG’15). Lars Arge and János
Pach eds., pp. 857–871.
Rinaldo, A. and Wasserman, L. (2010). Generalized density clustering. Ann. Statist. 38, 2678–2722.
Rodrı́guez-Casal, A. (2007). Set estimation under convexity-type assumptions. Ann. Inst. H.
Poincaré Probab. Statist. 43, 763–774.
Taylor, M.E. (2006). Measure Theory and Integration. American Mathematical Society. Providence.
Tenenbaum, , J.B., de Silva, V. and Langford, J.C. (2000). A Global geometric framework for
nonlinear dimensionality reduction. Science 290, 2319-2323.
Thäle, C. (2008). 50 years sets with positive reach. A survey. Surv. Math. Appl. 3, 123–165.
Walther, G. (1999). On a generalization of Blaschke’s rolling theorem and the smoothing of surfaces,
Math. Meth. Appl. Sci. 22, 301–316.
Zhang, Q.S. (2011). Sobolev Inequalities, Heat Kernel under Ricci Flow and the Poincar Conjecture.
CRC Press, Boca Raton.

30

