Potential applications of a result (by Beyer et al) on distance concentration and meaningless nearest neighbors in high dimensions

Question

My question is motivated by this question, and self-study of the paper "When is nearest neighbor meaningful?", where the authors show the following

Theorem 1: Let $X^{(d)} \in \mathbb{R}^d$ be a sequence of random vectors so that $\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||} \to_{p}1 \iff Var\left[\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||}\right] \to 0, d \to \infty.$ Then for any given $n \in \mathbb{N},$ and the random sample $\{X_1^{(d)} \dots X_n^{(d)}\}$ generated by $X^{(d)},$ the ratio

$$ \frac{max_{1 \le i \le n}||X_n^{(d)}||}{min_{1 \le i \le n}||X_n^{(d)}||}\to_{p} 1, d \to \infty. $$

Roughly speaking, the theorem shows that if the the norm of the random vector $X^{(d)}$ "behaves more deterministically" (i.e. $\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||} \to_{p}1,$) then the nearest neighbor of the origin loses it meaning (i.e. the maximum dist divided by minimum distance to the origin converges in probability to $1.$)

Also of relevance, is a family of examples that satisfies the hypothesis of the above Theorem 1, which is given in this paper "Concentration of Fractional Distances (Wertz. et. al.)", which basically states that (see its Theorem 5, P. 878)

Theorem 2: If $X^{(d)}=(X_1 \dots X_d) \in \mathbb{R}^d$ is a $d$ -dimensional random vector with iid components, then $\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||} \to_{p}1.$

*If we combine the above two theorems, we can infer that:

Corollary: For data generated by features that're iid, then the norm "behaves more deterministically" (explained above) in high dimensions (Theorem 2), hence by Theorem 1, the nearest neighbor of the origin loses its meaning in high dimensions.

N.B. assume below tat we're only considering Euclidean distances, not fractional etc. We do this because Euclidean distances are more amenable to manifold learnign or do linear algebraic computations (e.g. it's easy to transform dstances into inner products.)

I'm looking for a practical application of this corollary or the above two theorems, in terms of clustering and classification, where we use nearest neighbor. To be more specific, can we use this theorem or the corollary above as a "warning step" before performing, say kNN or 1-NN classification? So, let's say that we've an idea (maybe after some normality tests) that the data is generated by a normal random vector whose covariance matrix is almost diagonal , then the features are almost iid (thus almost satisfying the hypothesis of Theorem 2 above), and hence we can apply Theorem 2 first and then Theorem 1, to conclude beforehand that the nearest neighborhood classifier is not going to give us good results, without actually computing the maximum and minimum distances. This is just an idea, but are there any other practical applications where we can use the above two theorems?

Answer 1

I have found a possible application. After been generated several tabular synthetic datasets I have seen the following: I have used small sample size tabular data (less than 30 samples) and I have generated synthetic data with for example 1000 samples. The relative contrast in synthetic data is much higher than original data. In fact I have seen that this contrast in original data is close to the Ck value (see theorem below).

Theorem 2 (from Hinneburg et al.):

Let $\mathcal{F}$ be an arbitrary distribution of two points and the distance function $\lVert \mathbf{.} \rVert$ be an $L_k$ metric. Then,

$\lim_{d \to +\infty} E = \left[ \frac{Dmax_k^{d}-Dmin_k^{d}}{d^{1/k-1/2}}\right] = C_k$

where $C_k$ is some constant dependent on $k$ and $\frac{Dmax_k^{d}-Dmin_k^{d}}{d^{1/k-1/2}}$ is the relative contrast $\zeta_{\mathcal{L}_k}$($\mathcal{L}_k$ is the norm).

Then the metric $Dmax-Dmin$ will converge at $C_k$ when increrasing the dimensionality $d \to +\infty$. $C_k$ illustrates the concentration phenomenon (Beyer et al.).

Example:

Synthetic data created with python library nbsynthetic (https://github.com/NextBrain-ml/nbsynthetic)

Results:

Conclusions:

• This can be a prove that generated synthetic has higher contrast and is more suitable for finding patterns and quantify it.
• If Ck values from original and synthetic data are the same ¿does it means both distributions are close? ¿Could me a 'distance metric' to check if synthetic data is 'similar' to original data?

References:

• K. S. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft. 1999. When is "nearest neighbor" meaningful? in Proc. 7th Int. Conf. Database Theory, pp. 217–235.
• Alexander Hinneburg, Charu C. Aggarwal, and Daniel A. Keim. 2000. What Is the Nearest Neighbor in High Dimensional Spaces? In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB '00). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 506–515.

Answer 2

What makes this tricky when $d$ is large is that the data can obviously be very far from uniform or Normal or iid or anything, but it may still be unclear whether the distribution is 'nearly' $d$-dimensional or whether it actually concentrates on a low-dimensional subset. For an extreme case, imagine a tangled ball of string, where most of the near neighbours of most points on the string are close in the one-dimensional distance along the string.

What I would do is to pick a few points at random, find their distances from each other and from their nearest neighbour, and see if these were close. This takes advantage of the law-of-large-numbers part of the theorem: as $d$ increases, the probability of a random set of points having nearest neighbours near the typical value goes to 1.

You could even compare the ratio (nearest distance)/(typical distance) to what the theorem says, and say something like "We have 50 dimensions here but the nearest neighbours are only about as useless as in 20 iid dimensions".