21
$\begingroup$

Specifically, I'm looking for references (papers, books) which will rigorously show and explain the curse of dimensionality. This question arose after I began reading this white paper by Lafferty and Wasserman. In the third paragraph they mention a "well known" equation which implies that the best rate of convergence is $n^{-4/(4-d)}$; if anyone can expound upon that (and explain it), that would be very helpful.

Also, can anyone point me to a reference which derives the "well known" equation?

$\endgroup$
  • 7
    $\begingroup$ I cannot expound, but I believe I've heard what sound like three different versions of the curse: 1) higher dimensions mean an exponentially-increasing amount of work, and 2) in higher dimensions you will get fewer and fewer examples in any part of your sample space, and 3) in high dimensions everything tends to be basically equi-distant making it hard to make any distinctions. $\endgroup$ – Wayne Sep 23 '11 at 14:58
  • 5
    $\begingroup$ You could interpret this geometrically. Say that you have a sphere in D dimensions with radius r=1. You can then ask the question about what fraction of the volume of the sphere that lies between radius r=1 and r=1-e. Since we know that the volume of a sphere scales like k(d)*r^(d), where d is the number of dimensions, we can derive that the fraction is given by 1-(1-e)^d. Thus, for high dimensional spheres most of the volume is concentrated in a thin shell near the surface. See more about this in Bishops book "Pattern regognition and machine learning". $\endgroup$ – Dr. Mike Sep 23 '11 at 15:24
  • $\begingroup$ @Wayne Sure; plus 5) more dims usually mean more noise. $\endgroup$ – mbq Sep 23 '11 at 15:25
  • $\begingroup$ Dr. Mike, I don't follow the logic. It sounds like you're saying that "since most of the volume is concentrated in a thin shell near the surface of high dimensional sphere, then you are cursed with dimensionality." Can you explain further, and perhaps explicitly show me how the analogy ties in with statistics? $\endgroup$ – khoda Sep 26 '11 at 18:19
9
$\begingroup$

Following up on richiemorrisroe, here is the relevant image from the Elements of Statistical Learning, chapter 2 (pp22-27):

ESL page 25

As you can see in the upper right pane, there are more neighbors 1 unit away in 1 dimension than there are neighbors 1 unit away in 2 dimensions. 3 dimensions would be even worse!

$\endgroup$
6
$\begingroup$

I know that I keep referring to it, but there's a great explanation of this is the Elements of Statistical Learning, chapter 2 (pp22-27). They basically note that as dimensions increase, the amount of data needs to increase (exponentially) with it or there will not be enough points in the larger sample space for any useful analysis to be carried out.

They refer to a paper by Bellman (1961) as their source, which appears to be his book Adaptive Control Processes, available from Amazon here

$\endgroup$
  • $\begingroup$ +1. The explanation in ESL is great, and the associated diagrams help a lot. $\endgroup$ – Zach Sep 23 '11 at 15:34
6
$\begingroup$

This doesn't answer your question directly, but David Donoho has a nice article on High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality (associated slides are here), in which he mentions three curses:

  • Optimization by Exhaustive Search: "If we must approximately optimize a function of $D$ variables and we know only that it is Lipschitz, say, then we need order $(1/\epsilon)^D$ evaluations on a grid in order to obtain an approximate minimizer within error $\epsilon$."
  • Integration over product domains: "If we must integrate a function of $d$ variables and we know only that it is Lipschitz, say, then we need order $(1/\epsilon)^D$ evaluations on a grid in order to obtain an integration scheme with error $\epsilon$."
  • Approximation over high-dimensional domains: "If we must approximate a function of $D$ variables and we know only that it is Lipschitz, say, then we need order $(1/\epsilon)^D$ evaluations on a grid in order to obtain an approximation scheme with uniform approximation error $\epsilon$."
$\endgroup$
2
$\begingroup$

enter image description here

Maybe the most notorious impact is captured by the following limit (which is (indirectly) illustrated in above picture):

$$\lim_{dim\rightarrow\infty}\frac{dist_{max}-dist_{min}}{dist_{min}}$$

The distance in the picture is the $L_2$-based euclidian distance. The limit expresses that the notion of distance captures less and less information on similarity with increase of dimensionality. That impacts algorithms like the k-NN. By allowing fractions for $k$ in $L_k$-norms the described affect can be amended.


Impact of Dimensionality on Data in Pictures

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.