Information Technology Reference
In-Depth Information
V
(
f
)=
f
−
μ
K
,where
·
K
is the norm that corresponds to the scalar product
of
H
,and
D
(
P
n
)thatsatisfies
D
2
(
P
n
)
K
(
u
i
,
v
)
d
v
+
[0
,
1]
2
s
n−
1
n−
1
n−
1
1
n
2
2
n
=
K
(
u
i
,
u
j
)
−
K
(
u
,
v
)
d
u
d
v
(4)
[0
,
1]
s
i
=0
j
=0
i
=0
(see [11,12]). When
K
(
u
,
v
) can be computed in
O
(
s
) time for an arbitrary
(
u
,
v
), then this
D
(
P
n
) can be computed in
O
(
n
2
s
) time, but this assumption
does not always hold.
One important type of kernel has the form
K
(
u
,
v
)=
h
∈
Z
w
(
h
)
e
2
πι
h
t
(
u
−
v
)
(5)
s
where
ι
=
√
−
1, the
t
means “transposed”, and the
w
(
h
) are non-negative
weights
such that
h
∈
Z
s
w
(
h
)
<
. The corresponding square variation is
V
2
(
f
)=
0
∞
f
(
h
)
2
/w
(
h
)
,
s
|
|
=
h
∈
Z
where the
f
(
h
) are the Fourier coecients of
f
. The corresponding discrepancy
is easily computable only for special shapes of the weights.
For example, if
s
h
j
|
−
2
α
)
,
w
(
h
)=
min(1
,γ
j
|
(6)
j
=1
for some integer
α
≥
1 and positive real numbers (weights)
γ
j
, then the kernel
becomes
1
v
j
)
mod
1)
,
s
−
4
π
2
)
α
(2
α
)!
γ
j
(
K
α
(
u
,
v
)=
−
B
2
α
((
u
j
−
(7)
j
=1
where
B
2
α
is the Bernoulli polynomial of degree 2
α
[20]. This kernel can be
computed in
O
(
s
) time, so the discrepancy can be computed in
O
(
n
2
s
)time.
The corresponding
V
(
f
) in this case satisfies
⎛
⎝
j∈
u
⎞
⎠
(4
π
2
)
−α|
u
|
2
V
2
(
f
)=
φ
=
u
⊆S
∂
α|
u
|
f
∂
u
α
u
γ
−α
j
(
u
)
d
u
u
d
u
u
,
[0
,
1]
|
u
|
[0
,
1]
s−|
u
|
(8)
where
u
u
represents the coordinates of
u
whose indices are in the set
u
and
u
u
represents those whose indices are not in
. This RKHS contains only periodic
functions
f
of period 1, with
f
(0) =
f
(1), and the variability measures the
smoothness via the partial derivatives of
f
.
u
