# ε-Coverings of Hölder-Zygmund Type Spaces on Data-Defined Manifolds

Authors: Martin Ehler; Frank Filbir
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We first determine the asymptotes of theε-covering numbers of Hölder-Zygmund type spaces
on data-defined manifolds. Secondly, a fully discrete and finite algorithmic scheme is developed providing explicit ε-coverings whose cardinality is asymptotically near the ε-covering number. Given an arbitrary Hölder-Zygmund type function, the nearby center of a ball in the ε-covering can also be computed in a discrete finite fashion.


---

## Body

## 1. Introduction

Data processing in the digital era often deals with finitely many high-dimensional data chunks stemming from measurements that obey some continuous physical model. The implementation and numerical evaluation require estimates on the accuracy of the discretization with respect to the underlying model. As an elementary tool providing accuracy guarantees, we will addressɛ-coverings of some function spaces related to information theory and machine learning.As a standard concept in discrete mathematics, theɛ
-covering number
n
ɛ
(
Y
) is the minimal number of balls of radius ɛ that cover a compact metric space Y. An arbitrary element in Y can be represented by a nearby center preserving precision up to ɛ. As such, ɛ-coverings are also an integral part of approximation theory, especially if Y is some function space. Covering numbers capture the complexity of  Y and the approximation aspects are used in many fields such as information theory, statistics, nonparametric density estimation, and machine learning. There are estimates on the asymtotics of the ɛ-covering numbers of the standard function spaces (cf. [1, 2]), but some fields such as machine learning involve data lying on some manifold, so that target functions are naturally defined on this manifold. To clarify the terminology, we consider smoothness spaces on manifolds as somewhat nonstandard function spaces. It may be possible that the covering number of a function space on some compact Riemannian manifold can be assembled by covering numbers of standard function spaces on Euclidian spaces derived from the charts. However, it is also important to derive explicit ɛ-coverings whose cardinality is near the benchmark given by the ɛ-covering number. We believe that explicit coverings may be harder to construct using the charts due to interface problems, and therefore we will not pursue this direction and, instead, we will follow a more global approach.In general, there is still demand for computing coverings of many discrete and continuous spaces [3]. As an important additional requirement, any covering of a function space needs to come with an algorithmic scheme to determine some function’s nearby center in an effective manner. At first sight, the latter seems simple enough as we can take the center whose distance is minimal. However, determining the distance between two functions is eventually a continuous operation, and one is particularly interested in finite methods.In this paper, we first determine the asymtotics of theɛ-covering number for the unit ball of some Hölder-Zygmund type space Y
=
C
s
(
X
) on an underlying smooth compact Riemannian manifold X (without boundary and with nonnegative Ricci curvature). In fact, we determine the asymtotics of themetric entropy
log
⁡
2
(
n
ɛ
(
Y
)
), which is the number of bits needed to enumerate the ɛ-covering (cf. [1]). Moreover, we compute an explicit ɛ-covering, such that
(1)
log
⁡
2
(
n
^
ɛ
)
log
⁡
2
(
n
ɛ
)
≲
(
1
+
log
⁡
2
(
1
ɛ
)
)
,
where n
^
ɛ is the cardinality of the constructed covering and ≲ means that the left-hand side can be bounded by a generic constant times the right-hand side. Hence, our covering is optimal up to a logarithmic factor by means of the metric entropy. We allow the underlying manifold to be unknown in our scheme and, instead, to be represented through a finite sampling. This sampling must be chosen carefully and is the key to obtaining a finite scheme. The centers of our ɛ-covering can then be determined through a finite process, and we can measure any function’s distance to these centers in a finite manner.For constructions ofɛ-coverings on periodic smoothness spaces, for instance, we refer to [4, 5]. The concept of ɛ-entropy is also closely related to entropy numbers; see [6–8].The outline of this paper is as follows. In Section2 we introduce the setting, define the Hölder-Zygmund type space C
s
(
X
), and determine the metric entropy for its unit ball. An explicit covering is computed in Section 3.


## 2. Covering Numbers for Hölder-Zygmund Type Spaces

We first fix the setting and list some technical assumptions used throughout the paper. LetX
⊂
R
d be an α-dimensional compact and connected Riemannian manifold without boundary and with nonnegative Ricci curvature, geodesic distance ρ, and μ being the normalized Riemannian volume measure on X; {
φ
k
}
k
=
0
∞ are the eigenfunctions of the Laplacian on X, and {
-
λ
k
2
}
k
=
0
∞ are the corresponding eigenvalues arranged in nonincreasing order, so that 0
=
λ
0
≤
λ
1
≤
⋯. Readers who are not familiar with some terms from differential geometry that are used here may simply think of a “nice” manifold without boundary, such as the sphere, the real projective space, the (real) Grassmann manifold, or more generally compact homogeneous spaces. The above properties ensure certain estimates on the heat kernel on X (see [9, 10]), which were used in a series of papers [9, 11–13] to develop approximation schemes for smooth functions on the manifold. Here, we will make use of those approximation schemes, but we will keep the technical details at a minimum level.LetN be a positive integer and most of the time we will restrict ourselves to N
=
2
j, where j is some nonnegative integer. The space ofdiffusion polynomials up to degree N is
(2)
Π
N
∶
=
span
⁡
{
φ
k
:
λ
k
≤
N
}
.
Later, we will use the fact that the above conditions imply the following estimate on the Christoffel function:
(3)
∑
λ
k
≤
N
‍
|
φ
k
(
x
)
|
2
≍
N
α
,
x
∈
X
,
N
>
0
(cf. [9–11]), so that integration and orthonormality yield dim
⁡
(
Π
N
)
≍
N
α. Here, the symbol ≍ indicates that each side is bounded by a generic positive constant times the other side.In traditional scenarios, the accuracy of approximation by polynomials is closely related to the smoothness of the function. Therefore, the accuracy of approximation itself is nowadays considered to be a measurement of smoothness. This viewpoint is particularly useful in our setting because defining smoothness in a classical manner would require more technical details. Here, we define theHölder-Zygmund type space of order s
>
0 by C
s
(
X
)
=
{
f
∈
L
∞
(
X
)
:
∥
f
∥
C
s
(
X
)
<
∞
}, where its norm is given by
(4)
∥
f
∥
C
s
(
X
)
∶
=
∥
f
∥
L
∞
(
X
)
+
sup
⁡
N
≥
1
N
s
E
(
f
,
Π
N
,
L
∞
(
X
)
)
,
with E
(
f
,
Π
N
,
L
∞
(
X
)
)
∶
=
inf
⁡
g
∈
Π
N
∥
f
-
g
∥
L
∞
(
X
). Hence, f
∈
L
∞
(
X
) is contained in the Hölder-Zygmund type space if and only if it can be approximated by Π
N at rate N
-
s. Since the eigenfunctions {
φ
k
}
k
=
0
∞ are known to be smooth and we consider the L
∞-norm, each function in C
s
(
X
) has a continuous representative and point evaluation makes sense. The unit ball in C
s
(
X
) is denoted by C
s
¯
(
X
)
∶
=
{
f
∈
L
∞
(
X
)
:
∥
f
∥
C
s
(
X
)
≤
1
}. To compute its covering number, we first establish compactness. Since C
s
(
X
) is not finite-dimensional, C
s
¯
(
X
) is not compact in the Hölder-Zygmund type space, but we consider it as a subspace of L
∞
(
X
).Lemma 1.
The setC
s
¯
(
X
) is compact in L
∞
(
X
).The compactness of this embedding can be derived from (4) by abstract arguments involving Kolmogorov numbers (cf. [6]). Here, we provide a simple elementary proof for the sake of completeness.Proof.
We aim to verify that any sequence(
f
j
)
j
=
1
∞
⊂
C
s
¯
(
X
) must have an accumulation point in this set. Since each space Π
N is finite-dimensional, there are g
j
,
N
∈
Π
N, such that ∥
f
j
∥
L
∞
(
X
)
+
sup
⁡
N
≥
1
N
s
∥
f
j
-
g
j
,
N
∥
L
∞
(
X
)
≤
1. The latter implies that ∥
g
j
,
N
∥
L
∞
(
X
) is bounded for all j and N. Thus, there is g
1
∈
Π
1 such that the subsequence (
g
π
1
(
j
)
,
1
)
j
=
1
∞ converges towards g
1. For any N
=
1,2
,
…, we can recursively construct g
N
∈
Π
N such that
(5)
g
π
N
(
j
)
,
k
⟶
g
k
,
∀
k
=
1
,
…
,
N
,
and (
g
π
N
(
j
)
,
k
)
n
=
1
∞ is a subsequence of (
g
π
N
-
1
(
j
)
,
k
)
n
=
1
∞. For N
′
≥
N, this construction yields that (
g
π
N
′
(
j
)
,
N
)
j
=
1
∞ is a subsequence of (
g
π
N
(
j
)
,
N
)
j
=
1
∞, so that we derive
(6)
∥
g
N
-
g
N
′
∥
L
∞
(
X
)
=
lim
⁡
n
→
∞
∥
g
π
N
′
(
j
)
,
N
-
g
π
N
′
(
j
)
,
N
′
∥
L
∞
(
X
)
≤
lim
⁡
n
→
∞
∥
g
π
N
′
(
j
)
,
N
-
f
π
N
′
(
j
)
∥
L
∞
(
X
)
+
∥
f
π
N
′
(
j
)
-
g
π
N
′
(
j
)
,
N
′
∥
L
∞
(
X
)
≤
N
-
s
+
N
′
-
s
.
Therefore, (
g
N
)
N
=
1
∞ is a Cauchy sequence and, hence, converges towards some g
∈
L
∞
(
X
). Standard calculations reveal that g is an accumulation point of (
f
j
)
j
=
1
∞ and is contained in C
s
¯
(
X
), which concludes the proof.We can now derive the asymptotes of theɛ-covering number of C
s
¯
(
X
) in L
∞
(
X
).Theorem 2.
Ifs
>
0 is fixed and 0
<
ɛ
≤
1, then
(7)
log
⁡
2
(
n
ɛ
(
C
s
¯
(
X
)
)
)
≍
ε
-
α
/
s
holds, where the generic constants do not depend on ɛ.Analogous results can be derived for similar concepts such as different types ofn-widths of functions spaces (cf. [14–16]). Theorem 2 and its proof are rather classical and can be derived from [17]. To guide the interested reader, we will provide the outline of the proof that is based on a general Banach space result and is also used in [18, Theorem 4.1]. Let X be a Banach space and let {
ϕ
k
}
k
=
1
∞
⊂
X be a sequence of linearly independent elements whose linear span is dense in X, and define X
k
∶
=
span
⁡
{
ϕ
1
,
…
,
ϕ
k
} with X
0
=
{
0
}. Let {
δ
k
}
k
=
0
∞ be a nonincreasing sequence of positive numbers with lim
⁡
k
→
∞
δ
k
=
0. The full approximation space is
(8)
A
(
X
;
{
δ
k
}
k
=
0
∞
,
{
ϕ
k
}
k
=
1
∞
)
∶
=
{
f
∈
X
:
E
(
f
,
X
k
,
X
)
≤
δ
k
,
for
k
=
0,1
,
…
}
.
A proof similar to Lemma 1 yields that this space is compact, and we can formulate the result from Banach space theory that goes back to Lorentz in [17].Theorem 3 (see [19, Theorem 3.3]).
Let{
δ
k
}
k
=
0
∞ be a nonincreasing sequence of positive numbers such that δ
2
k
≤
c
δ
k, for k
=
1,2
,
… and some constant c
∈
(
0,1
). For l
≥
0, let M
l
:
=
min
⁡
{
k
:
δ
k
≤
e
-
l
}. If n
ɛ denotes the ɛ-covering number of A
(
X
;
{
δ
k
}
k
=
0
∞
,
{
ϕ
k
}
k
=
1
∞
) in X, then one has, for 0
<
ɛ
≤
1,
(9)
log
⁡
2
(
n
ɛ
)
≍
∑
l
=
1
L
‍
M
l
,
where L
:
=
2
+
⌊
log
⁡
(
1
/
ɛ
)
⌋.At this point our preparations are complete.Proof of Theorem2.
We aim to apply Theorem3 with the function system {
φ
k
}
k
=
0
∞ and with X being the closure of ⋃
N
=
1
∞
‍
Π
N in L
∞
(
X
). There, the index set is supposed to start with k
=
1, so we set ϕ
k
=
φ
k
-
1, k
=
1,2
,
…. To define the sequence {
δ
k
}
k
=
0
∞, we need some preparations. As pointed out before, integrating (3) over X yields dim
⁡
(
Π
N
)
≍
N
α. By using X
k
∶
=
span
⁡
{
φ
0
,
…
,
φ
k
-
1
}, we derive, for N
α
≤
k
≤
(
2
N
)
α,
(10)
(
2
N
)
s
E
(
f
,
Π
2
N
,
X
)
≲
k
s
/
α
E
(
f
,
X
k
,
X
)
≲
N
s
E
(
f
,
Π
N
,
X
)
.
Therefore, there are constants C
i
≥
1, for i
=
1,2, such that the definitions δ
1
;
0
=
1
/
2, δ
1
;
k
∶
=
(
2
C
1
)
-
1
k
-
s
/
α, and δ
2
;
0
=
C
2, δ
2
;
k
∶
=
C
2
k
-
s
/
α, lead to
(11)
A
(
X
;
{
δ
1
;
k
}
k
=
0
∞
,
{
ϕ
k
}
k
=
1
∞
)
⊂
C
s
¯
(
X
)
⊂
A
(
X
;
{
δ
2
;
k
}
k
=
0
∞
,
{
ϕ
k
}
k
=
1
∞
)
,
which also yields
(12)
n
ɛ
(
A
(
X
;
{
δ
1
;
k
}
k
=
0
∞
,
{
ϕ
k
}
k
=
1
∞
)
)
≤
n
ɛ
(
C
s
¯
(
X
)
)
≤
n
ɛ
(
A
(
X
;
{
δ
2
;
k
}
k
=
0
∞
,
{
ϕ
k
}
k
=
1
∞
)
)
.
Since δ
i
;
2
k
≤
c
δ
i
;
k, for c
:
=
2
-
s
/
α
∈
(
0,1
), we can apply Theorem 3. According to [18, Lemma 4.1], ∑
l
=
1
L
‍
M
l
≍
e
L
α
/
s, so that the choice of L in (9) implies (7).Remark 4.
The proof of Theorem2 discovers that (7) also holds under much weaker conditions, and we have only used the fact that there is a sequence of linearly independent functions {
φ
k
}
k
=
0
∞, so that the polynomial spaces in (2) satisfy dim
⁡
(
Π
N
)
≍
N
α.


## 3. Near Optimal Covering

This section is dedicated to constructing our covering of the unit ball in the Hölder-Zygmund type space, which is based on localized summation kernels as developed in a series of papers [9, 11–13]. We first need some preparations. A Borel probability measure ν on X is called aquadrature measure of order N if
(13)
∫
X
‍
f
(
x
)
g
(
x
)
d
μ
(
x
)
=
∫
X
‍
f
(
x
)
g
(
x
)
d
ν
(
x
)
,
∀
f
,
g
∈
Π
N
.
Note that our setting yields that there is a constant a
>
0 such that f
·
g
∈
Π
a
N for all f
,
g
∈
Π
N and all N (cf. [11, Theorem A
.
1]); see also [20] for homogeneous spaces. The existence of quadrature measures with finite support is proved for fairly general smooth Riemannian manifolds in [11], where a construction procedure is outlined. In fact, the support of ν can be chosen to be contained in any sufficiently dense finite sampling {
x
l
}
l
=
1
m of X, so that ν can be identified with {
x
l
}
l
=
1
m and nonnegative weights {
ω
l
}
l
=
1
m satisfying ν
(
{
x
l
}
)
=
ω
l. Examples on the sphere, for instance, are given in [21].The results in [11] yield that we can even choose a sequence (
ν
N
)
N
=
1
∞ of quadrature measures of order N, respectively, such that #
supp
⁡
(
ν
N
)
≲
N
α. For the remaining part of the paper, we will suppose that this estimate holds and we define, for N
=
2
j,
(14)
p
p
p
p
p
p
σ
N
(
f
)
∶
=
∫
X
‍
f
(
y
)
K
N
(
·
,
y
)
d
ν
N
(
y
)
,
where
K
N
(
x
,
y
)
=
∑
k
=
0
∞
‍
h
(
λ
k
N
)
φ
k
*
(
y
)
φ
k
(
x
)
,
where h
:
R
≥
0
→
R is an infinitely often differentiable and nonincreasing function with h
(
t
)
=
1 for t
≤
1
/
2 and h
(
t
)
=
0 for t
≥
1. Although we will not explicitly use it in the present paper, we want to point out that many advantageous properties of σ
N are steered by the so-called localization of the kernel K
N; that is, for fixed S
>
α and all x
≠
y with N
=
1,2
,
…,
(15)
|
K
N
(
x
,
y
)
|
≲
N
α
-
S
ρ
(
x
,
y
)
S
.
See [12, 13]. Later, we will apply
(16)
sup
⁡
x
∈
X
∫
X
‍
|
K
N
(
x
,
y
)
|
d
|
ν
N
|
(
y
)
≲
1
(cf. [11]). Those estimates are used in [12, 13] to characterize the Hölder-Zygmund type smoothness by means of σ
N.Theorem 5.
Assume that(
ν
N
)
N
=
1
∞ is a family of quadrature measures of order N, respectively. Then, for all f
∈
C
s
(
X
), one has
(17)
∥
f
-
σ
N
(
f
)
∥
L
∞
(
X
)
≲
N
-
s
∥
f
∥
C
s
(
X
)
,
where the generic constants do not depend on N or f. On the other hand, if, for f
∈
L
p
(
X
), there are generic constants not depending on N such that ∥
f
-
σ
N
(
f
)
∥
L
∞
(
X
)
≲
N
-
s holds, then f
∈
C
s
(
X
).Next, by usingh
(
λ
k
/
N
)
h
(
λ
k
/
2
N
)
=
h
(
λ
k
/
N
) and applying the quadrature property of ν
N, a straightforward calculation yields
(18)
σ
N
(
f
,
x
)
=
∫
X
‍
σ
N
(
f
,
y
)
K
2
N
(
x
,
y
)
d
ν
N
(
y
)
.
For some fixed S
>
1, we define the actual approximation by
(19)
σ
N
∘
(
f
,
x
)
∶
=
∫
X
‍
I
N
(
f
,
y
)
K
2
N
(
x
,
y
)
d
ν
N
(
y
)
,
o
o
o
i
o
i
where
I
N
(
f
,
y
)
=
N
-
S
⌊
N
S
σ
N
(
f
,
y
)
⌋
.
In other words, we replace σ
N
(
f
,
y
) in (18) with a number on the grid (
1
/
N
S
)
Z. We define the following collection:
(20)
M
S
,
N
∶
=
{
σ
N
∘
(
f
)
:
f
∈
C
s
¯
(
X
)
}
,
which induces a covering of C
s
¯
(
X
) in L
∞
(
X
).Theorem 6.
For fixeds
>
0 and S
>
max
⁡
(
1
,
s
), one applies the discretization (19). Then, there is a constant c
>
0 such that, for all f
∈
C
s
¯
(
X
), ∥
f
-
σ
N
∘
(
f
)
∥
L
∞
(
X
)
≤
c
N
-
s holds. Thus, for c
N
-
s
=
ɛ
≤
1, the collection M
S
,
N induces an ɛ-covering of C
s
¯
(
X
) in L
∞
(
X
). Its cardinality n
^
ɛ satisfies
(21)
log
⁡
2
(
n
^
ɛ
)
≲
ε
-
α
/
s
(
1
-
log
⁡
2
(
ɛ
)
)
,
where the generic constant does not depend on ɛ.Proof of Theorem6.
The triangle inequality yields(22)
∥
f
-
σ
N
∘
(
f
)
∥
L
∞
(
X
)
≲
∥
f
-
σ
N
(
f
)
∥
L
∞
(
X
)
+
∥
σ
N
(
f
,
ν
N
)
-
σ
N
∘
(
f
)
∥
L
∞
(
X
)
.
Since Theorem 5 implies ∥
f
-
σ
N
(
f
)
∥
L
∞
(
X
)
≲
N
-
s
∥
f
∥
C
s
(
X
)
=
N
-
s, we only need to take care of the term on the farmost right. The quantization (19) immediately yields
(23)
|
σ
N
(
f
,
y
)
-
I
N
(
f
,
y
)
|
≤
N
-
S
,
∀
y
∈
supp
⁡
(
ν
N
)
,
so that (18) and (16) imply
(24)
∥
σ
N
(
f
)
-
σ
N
∘
(
f
)
∥
L
∞
(
X
)
=
∥
∫
X
‍
(
σ
N
(
f
,
y
)
-
I
N
(
f
,
y
)
)
K
N
(
·
,
y
)
d
ν
N
(
y
)
∥
L
∞
(
X
)
≲
N
-
S
≤
N
-
s
.
Hence, we have derived the estimate on ∥
f
-
σ
N
∘
(
f
)
∥
L
∞
(
X
).
To tackle (21), we apply (23), which yields
(25)
|
I
N
(
f
,
y
)
|
≲
∥
σ
N
(
f
)
∥
L
∞
(
X
)
.
According to [13, Theorem 5.1], ∥
σ
N
(
f
)
∥
L
∞
(
X
)
≲
∥
f
∥
L
∞
(
X
) holds. Since f is contained in the ball of radius 1, we see that
(26)
|
I
N
(
f
,
y
)
|
≲
1
.
Thus, the number of possible values of I
N
(
f
,
y
) for fixed y is at most c
1
N
S, where c
1
≥
1 is a positive constant. Note that we can assume that c
1
N
S
≥
1 because, otherwise, I
N
(
f
,
y
) would be zero. Since #
supp
⁡
(
ν
N
)
≲
N
α, we have #
{
I
N
(
f
,
y
)
:
y
∈
supp
⁡
(
ν
N
)
}
≲
N
α. Therefore, we have n
^
ɛ
≤
(
c
1
N
S
)
c
2
N
α, for some positive constant c
2. By using c
N
-
s
=
ɛ
≤
1, we obtain
(27)
log
⁡
2
(
n
^
ɛ
)
=
c
2
c
α
/
s
ε
-
α
/
s
log
⁡
2
(
c
1
(
c
ɛ
)
S
/
s
)
≲
ε
-
α
/
s
log
⁡
2
(
(
c
1
)
s
/
S
c
ɛ
)
≲
ε
-
α
/
s
log
⁡
2
(
(
c
1
/
ɛ
)
s
/
S
c
ɛ
)
≲
ε
-
α
/
s
(
1
+
log
⁡
2
(
1
ɛ
)
)
,
which concludes the proof.According to Theorems2 and 6, the ɛ-covering number n
ɛ of C
s
¯
(
X
) and the number n
^
ɛ of ɛ-balls induced by M
S
,
N satisfy
(28)
log
⁡
2
(
n
^
ɛ
)
log
⁡
2
(
n
ɛ
)
≲
(
1
+
log
⁡
2
(
1
ɛ
)
)
.
Therefore, our scheme is optimal up to a logarithmic factor by means of the metric entropy.Our results are also related to the field of manifold learning, in which a function must be reconstructed from finite training data (cf. [22–25]). When actually applying our scheme, we first acquire a set of samples {
x
l
}
l
=
1
m sufficiently well covering X and we also need the function values {
f
(
x
l
)
}
l
=
1
m, which altogether build the training data. Next, we compute a quadrature measure ν
N for some maximal N such that supp
⁡
(
ν
N
)
⊂
{
x
l
}
l
=
1
m; see [11, 21] for an algorithm. Here, we need that the sample points {
x
l
}
l
=
1
m are well distributed and larger N require more samples. An element in M
S
,
N that is ɛ-close to f is simply given by σ
N
∘
(
f
), whose computation only requires knowledge of f and {
φ
k
:
λ
k
≤
N
} on the finite set supp
⁡
(
ν
N
); see (14) and (19). In other words, we do not need to know the entire manifold but only the finite sampling of the training data {
x
l
}
l
=
1
m, the sampling of the target function {
f
(
x
l
)
}
l
=
1
m, and, more delicately, the sampling of the eigenfunctions {
φ
k
(
x
l
)
:
λ
k
≤
N, l
=
1
,
…
,
m
} of the Laplacian. Those eigenfunctions, however, are not explicitly known except for few special cases, such as the sphere, projective space, the Grassmann manifold, and few more. Fortunately, approximation of those eigenfunctions is a common procedure in manifold learning. Computational schemes are based on the graph Laplacian to be built from the training data and, at least under suitable assumptions, converging towards the Laplacian on the manifold when the cardinality of the data increases (cf. [26–28] and references therein). Those schemes approximately sample the first few eigenfunctions on the training data. Thus, our proposed approach is indeed fully discrete and computationally feasible even if the eigenfunctions {
φ
k
}
k
=
0
∞ are not explicitly known. In fact, the manifold itself can be unknown. As long as X satisfies the theoretical assumptions, it is simply represented by means of a finite sample.Remark 7.
The technical assumptions on the manifoldX and the function system {
φ
k
}
k
=
0
∞ imply certain estimates on the heat kernel on X (see [9, 10]), mainly used to ensure that the localization property (15) holds (cf. [12, 13]). Our assumptions also imply the existence of quadrature measures ν
N and that f
·
g
∈
Π
a
N for all f
,
g
∈
Π
N and some constant a
>
0. These items lead to the characterization of the Hölder-Zygmund type space by means of σ
N in Theorem 5. Moreover, the family (
ν
N
)
N
=
1
∞ can be chosen with finite support, in fact with #
supp
⁡
(
ν
N
)
≲
N
α (cf. [11]). Theorem 5 and #
supp
⁡
(
ν
N
)
≲
N
α are indeed the two main ingredients of the poof of our results in Theorem 6.Remark 8.
The reader familiar with the approximation scheme developed in [9, 11–13] may expect that the presented results can be generalized to a wider class of Besov spaces on metric spaces. This is indeed true but requires more technical details and does not lead to a fully discrete scheme in the end. Here, we intended to emphasize the main ideas by keeping technical details at a minimum level and to focus on the development of a fully discrete covering algorithm. The more general approach will be described elsewhere.



---

*Source: 402918-2014-06-17.xml*