Vtyjkyuk

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^frac1p$, 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^frac1p$ come from.

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

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

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

A 3D grid of $3times 3times3=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.