PROVABLE DIMENSION DETECTION USING PRINCIPAL COMPONENT ANALYSIS
Siu-Wing Cheng, Yajun Wang, Zhuangzhi Wu · International Journal of Computational Geometry & Applications · 2008
We analyze an algorithm based on principal component analysis (PCA) for detecting the dimension k of a smooth manifold [Formula: see text] from a set P of point samples. The best running time so far is O(d 2O(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(d2O(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.