Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/6021

PROVABLE DIMENSION DETECTION USING PRINCIPAL COMPONENT ANALYSIS

Authors Cheng, Siu-Wing
Wang, Yajun
Wu, Zhaungzhi
Issue Date 2008
Source International journal of computational geometry & applications , v. 18, (5), 2008, OCT, p. 415-440
Summary We analyze an algorithm based on principal component analysis (PCA) for detecting the dimension k of a smooth manifold M subset of 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.
Subjects
ISSN 0218-1959
Rights Electronic version of an article published as International Journal of Computational Geometry and Applications, v. 18, no. 5, 2008, p. 415-440. DOI: 10.1142/S0218195908002702 © copyright World Scientic Publishing Company http://www.worldscinet.com/ijcga/
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST
Files in this item:
File Description Size Format
paper.pdf 242116 B Adobe PDF