Provable dimension detection using principal component analysis

We present simple algorithms for detecting the dimension k of a smooth manifold M ⊂ ℝ^d from a set P of point samples, provided that P satisfies a standard sampling condition as in previous results. The best running time so far is O(d2^{O(k7 log k)}) worst-case by Giesen and Wagner after the adaptive neighborhood graph is constructed in O(d |P| ²) worst-case time. Given the adaptive neighborhood graph, for any l > 1, our algorithm outputs the true dimension with probability at least 1 - 2^-1 in O(2^O(k)kd(k + l log d)) expected time. Our experimental results validate the effectiveness of our approach in computing the dimension. A further advantage is that both the algorithm and its analysis can be generalized to the noisy case, in which outliers and a small perturbation of the samples are allowed.