# What is a sampling density? Why is the sampling density proportional to $N^{\frac{1}{p}}$?

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!

-

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}$.

-
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.

-