I am a bit confused by the phenomenon of the curse of dimensionality. Most lecturers motivate this with the KNN classifier and I understand why higher dimensions should be avoided with this classifier but I don't get why higher dimensions are so bad in general.
I understand that the more dimensions our data has the more computationally heavy the algorithms get but the crucial point why high dimensionality is so bad seems to lie somewhere else. Udacity expresses this phenomenon as follows:
As the number of features or dimensions grows, the amount of data we need to accurately generalize grows exponentially.
Why is that? I know that for high dimensional data it is very likely that a random chosen data sample lies somewhere near the edge of the domain. But I still don't really get why the statement above holds.