Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm reading a book named The Elements of Statistical Learning by Hastie, in section 2.5, Local Methods in High Dimensions, it says that the sampling density is proportional to $N^{\frac{1}{p}}$, where $p$ is the dimension of the input space and $N$ is the sample size.

I'm confused, what does it mean by sampling density? I do know, intuitively, as the dimension becomes larger, the sample becomes more sparse. But I don't understand exactly where does $N^{\frac{1}{p}}$ come from.

Could anyone give me a hint? Thanks a lot!

share|cite|improve this question

2 Answers 2

up vote 2 down vote accepted

Recall that the sampling density or sampling rate is the number of recorded samples per unit distance.

Assume that a sample of size $N$ is taken from the unit cube $[0,1]^p$ in $\mathbb R^p$ (but the argument applies to every domain of finite volume). Roughly speaking, each point in the sample takes a volume $1/N$ of the domain, hence the distance between this point and its neighbors scales as $1/N^{1/p}$.

share|cite|improve this answer
Thanks for your explanation! And yet I'm still a little confused by "per unit distance". What does "per unit distance" mean? Why do we define it in this way? – Tansy Jan 22 '13 at 0:27
A density of 0.01 per meter means that your nearest neighbour is at roughly 100 meters from you. – Did Jan 22 '13 at 7:57

An "engineering" explanation: say you have a sampling grid in 2D using $2$ samples per dimension, you will have a $2\times 2$ grid with $4$ samples. $4^{1/2}=2$

Now you do the "equivalent" for 3D, you will have $2\times 2\times 2$ grid with $8$ samples with the same sampling density $8^{1/3}=2$.

A 3D grid of $3\times 3\times3=27$ samples would have a sample density of $27^{1/3}=3$.

The relation between the number of samples $N$ of a $p$-dimensional grid with $k$ samples per direction is $N=k^p$.

So this sampling density is some how the opposite: say you have $N$ samples in $p$ dimensions and you want to know the "average" number of samples per dimension. $(N^{1/p})=k$.

And it is also used when the samples are not on a grid, but "randomly" distributed such that $k$ is not limited to integers but can be rational numbers.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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