Provable dimension detection using principal component analysis

We analyze an algorithm based on principal component analysis (PCA) for detecting the dimension k of a smooth manifold M ⊂ ℝ^d from a set P of point samples. The best running time so far is O(d 2 ^{O(k7log k)}) by Giesen and Wagner after the adaptive neighborhood graph is constructed. Given the adaptive neighborhood graph, the PCA-based algorithm outputs the true dimension in O(d2^O(k)) time, provided that P satisfies a standard sampling condition as in previous results. Our experimental results validate the effectiveness of the approach. A further advantage is that both the algorithm and its analysis can be generalized to the noisy case, in which small perturbations of the samples and a small portion of outliers are allowed.