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 ⊂ R d from a set P of point samples. The best running time so far is O(d2 O(k7 log 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