HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/6021
Title: Provable dimension detection using principal component analysis
Authors: Cheng, Siu-Wing
Wang, Yajun
Wu, Zhuangzhi
Keywords: Dimension detection
Sampling
Principal component analysis
Issue Date: Jul-2006
Citation: International journal of computational geometry and applications, v. 18, no. 5, 2008, p. 415-440
Abstract: We analyze an algorithm based on principal component analysis (PCA) for detecting the dimension k of a smooth manifold M ⊂ Rd from a set P of point samples. The best running time so far is O(d 2O(k7logk)) by Giesen andWagner 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.
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/
URI: http://hdl.handle.net/1783.1/6021
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
paper.pdfpre-published version236KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.