Estimating the intrinsic dimensionality (ID) of data is a fundamental problem in machine learning and computer vision, providing insight into the true degrees of freedom underlying high-dimensional observations. Existing methods often rely on geometric or distributional assumptions and can significantly fail when these assumptions are violated. In this paper, we introduce a novel ID estimator based on nearest-neighbor distance ratios that involves simple calculations and achieves state-of-the-art results. Most importantly, we provide a theoretical analysis proving that our estimator is universal, namely, it converges to the true ID independently of the distribution generating the data. We present experimental results on benchmark manifolds and real-world datasets to demonstrate the performance of our estimator.
Figures & tables
Fig. 1 : The (approximately) linear relationship between Lˉk,j and log(d) (for (k,j)=(2,1) , (5,3) , and (8,4) ). Here we used 2,500 points, sampled from the d -dimensional Gaussian distribution. The error bars are computed from 1000 independent trials.
Name
Intrinsic dim. ( d )
Ambient dim.
M1_Sphere
10
11
M2_Affine_3to5
3
5
M3_Nonlinear_4to6
4
6
M4_Nonlinear
4
8
M5a_Helix1d
1
3
M5b_Helix2d
2
3
TABLE I : List of benchmark manifolds [ 9 ]
No. Pts
625
1,250
2,500
5,000
L2N2(2,1)(r)
8.52
6.97
6.06
5.52
L2N2(2,1)(opt)
11.62
9.21
8.09
7.23
L2N2(2,1)
13.02
11.00
9.96
9.28
L2N2(4,2)
16.43
12.59
11.38
10.86
L2N2(8,4)
19.33
17.36
12.96
11.29
CDim [ 43 ]
53.91
50.81
45.78
43.83
TABLE II : MPE for benchmark manifolds. The suffix “(r)” indicates that the estimated dimensions were rounded to the nearest integer, and “(opt)” indicates that the parameter values were optimized for the benchmark. Note the results reported for all methods other than L2N2 were optimized as well [ 4 ] .
Fig. 2 : (a) MPE scores of L2N2 with (k,j)=(2,j) and (8,4) , TwoNN, and GriDE across the individual benchmark manifolds for 2,500 points. (b) Comparing the MPE when dimensionality rounding is used. L2N2 without rounding is here added for reference.
Fig. 3 : Comparison of estimated ID of d -dimensional spheres for different methods and dimensions with the ground truth shown.
Method
σ=0.0
σ=0.01
σ=0.1
L2N2(2,1)
6.10
6.16
8.48
lPCA
7.00
7.00
11.00
MLE
5.89
5.92
8.04
PH
5.94
5.97
8.21
KNN
6.00
5.97
9.17
WODCap
6.93
6.93
6.93
TABLE III : Average estimated dimensions for the noise experiments where S6 is embedded into R11 with mean zero, variance σ2 Gaussian noise (in ambient space dimension) added.
Method
σ:0.0
σ:0.01
σ:0.1
L2N2(2,1)
10.05
10.02
10.47
lPCA
11.00
11.00
11.00
MLE
9.26
9.25
9.61
PH
9.38
9.34
9.78
KNN
9.91
9.99
10.29
WODCap
9.15
9.15
9.15
TABLE IV : Average estimated dimensions for the noise experiments where S10 is embedded into R11 with mean zero, variance σ2 Gaussian noise (in ambient space dimension) added.
Fig. 4 : Estimated ID for real datasets. (a) ISOMAP faces; (b) digit “1” in MNIST (other digits can be found in the supplemental material); (c) CIFAR-100; (d) Isolet dataset. Bars denote ±1 standard deviation.
Fig. 5 : Downstream experiments results: Reconstruction errors (MSE) of autoencoders with bottleneck layers set to different values.
No. Pts ( ×103 )
15
50
100
500
(SubSamp) MPE
8.50
7.67
7.61
6.88
(Full Set) MPE
8.15
7.33
7.05
6.41
MPE Diff.
0.45
0.34
0.56
0.47
TABLE V : Benchmark manifold MPE from the subsampling experiments (no rounding or optimization). (Full Set) indicates that all points are used. (SubSamp) indicates that a random subset of 2,500 points are used.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Fig. 6 : Results for digits “2”,“3”, and “4” from the MNIST dataset. The error bars represent the standard deviation.
# pts
α2,1(n)
β2,1(n)
100
0.843130 ± 0.030100
0.774468 ± 0.063900
250
0.880452 ± 0.024624
0.730182 ± 0.052274
500
0.904643 ± 0.028951
0.703754 ± 0.061459
750
0.908416 ± 0.023954
0.702147 ± 0.050852
1,000
0.911129 ± 0.025758
0.703216 ± 0.054681
2,000
0.928568 ± 0.021527
0.675884 ± 0.045700
Appendix
TABLE VI : d -dimensional Gaussian : Dimensions 1–20 used
# pts
α2,1(n)
β2,1(n)
100
0.693905 ± 0.024272
1.150159 ± 0.076637
250
0.708339 ± 0.011373
1.169491 ± 0.035910
500
0.703530 ± 0.014324
1.221910 ± 0.045228
750
0.727740 ± 0.016855
1.165622 ± 0.053221
1,000
0.732002 ± 0.014138
1.165663 ± 0.044642
2,000
0.752371 ± 0.016913
1.131156 ± 0.053402
Appendix
TABLE VII : d -dimensional Gaussian : Dimensions 10–40 used
Fig. 7 : A comparison of the estimated values using different dimensionality ranges for (a) α2,1(n) and (b) β2,1(n) for different numbers of points n sampling from a d -dimensional Gaussian distribution. The dotted black line indicates the theoretical limit value. The error bars represent the standard deviation.
Fig. 8 : A comparison of the estimated values using different sampling distributions (a) α2,1(n) and (b) β2,1(n) for different numbers of points n using dimensions up to d=20 . The distributions shown are a d -dimensional Gaussian distribution, and uniform distributions on a d -dimensional hypercube and hypersphere. The dotted black line indicates the theoretical limit values. The error bars represent the standard deviation.
Fig. 9 : A comparison of the estimated values using different sampling distributions (a) α2,1(n) and (b) β2,1(n) for different numbers of points n using samples from dimensions 10–40. The distributions shown are a d -dimensional Gaussian distribution, and uniform distributions on a d -dimensional hypercube and hypersphere. The dotted black line indicates the theoretical limit values. The error bars represent the standard deviation.