Information Technology Reference
In-Depth Information
V
(
C
2
)
V
(
C
3
)
→
π
1
x
3
2
V
(
C
3
)=
1
−
dx
3
−
1
=
π
1
x
3
)
dx
3
(1
−
−
1
4
3
π
=
.
V
(
C
n−
1
)
V
(
C
n
)
V
(
C
n
)=
V
(
C
n−
1
)
→
1
x
n
)
(
n−
1)
/
2
dx
n
·
(1
−
−
1
π
n/
2
Γ
(
2
+1)
=
Proposition 1.
The volume of a n-dimensional hypersphere with radius r is
π
n/
2
Γ
2
+1
V
(
n, r
)=
r
n
·
(2)
Proof.
see [11]
4
Curse of Dimensionality
The phenomenon “curse of dimensionality” was first mentioned by Bellman [13]
during his study of optimizing a function of a few dozen variables in an exhaus-
tive search space. For example, given a function defined on a unitary hypercube
of dimension
n
, in each dimension 10 discrete points are considered for evaluat-
ing the function. In dimension
n
= 2, this results in 100 evaluations, whereas in
dimension
n
= 10, 10
10
function evaluations are required. In general, an exponen-
tial number of (1
/
)
n
function evaluations are required to obtain an optimization
error of
and therefore is computationally infeasible, even for a moderate
n
.
This simple example shows how problems like function optimization, which
are computationally feasible in lower dimensions, transform to computation-
ally infeasible problems in higher dimensions. A similar phenomenon (but not
from the perspective of computational complexity) can be observed with hyper-
spheres in high-dimensional spaces, where they loose their familiar properties. In
high-dimensions
n
, i.e.
n>
3, hyperspheres have undesirable properties. These
properties (the following corollaries) can be derived directly from proposition (1).
R
Corollary 1.
The volume of hyperspheres converges to
0
for n
→∞
.
lim
n→∞
V
(
n, r
)=0
