ml
Dimensionality Reduction
Curse of dimensionality: ball/cube volume ratio, expected nearest-neighbor distance, required sample blowup, Johnson-Lindenstrauss bound — log-scale curve chart.
Parameters
Data Density
Distance Metric
Curse of Dimensionality Analysis
Ball/cube volume ratio (d=20)0.02581
E[NN distance] at d=20, n=10000.7079
E[NN distance] at k=30.1
Distance preservation ratio (k/d)0.1413
Required samples vs 2D baseline1.00e+30
Johnson-Lindenstrauss Bound
Minimum k to preserve distances within ε (n=1000):
ε=0.1 → k ≥ 5717
ε=0.2 → k ≥ 1481
ε=0.3 → k ≥ 683
k ≥ 8·ln(n) / (ε²−ε³/3) · E[NN] ≈ (1/n)^(1/d) · vol(d) = π^(d/2)/Γ(d/2+1)
Curse of Dimensionality (d = 1 to 100, log scale)
— E[NN dist]— ball/cube ratio--- req. samples| current d| target k