Intrinsic Dimensionality Estimation with Optimally Topology Preserving Maps
A new method for analyzing the intrinsic dimensionality (ID) of low dimensional manifolds in high dimensional feature spaces is presented. The basic idea is to first extract a low-dimensional representation that captures the intrinsic topological structure of the input data and then to analyze this representation, i.e. estimate the intrinsic dimensionality. More specifically, the representation we extract is an optimally topology preserving feature map (OTPM) which is an undirected parametrized graph with a pointer in the input space associated with each node. Estimation of the intrinsic dimensionality is based on local PCA of the pointers of the nodes in the OTPM and their direct neighbors. The method has a number of important advantages compared with previous approaches: First, it can be shown to have only linear time complexity w.r.t. the dimensionality of the input space, in contrast to conventional PCA based approaches which have cubic complexity and hence become computational impracticable for high dimensional input spaces. Second, it is less sensitive to noise than former approaches, and, finally, the extracted representation can be directly used for further data processing tasks including auto-association and classification. Experiments include ID estimation of synthetic data for illustration as well as ID estimation of a sequence of full scale images.
Use and reproduction:No Creative Commons license - The provisions of the German Copyright Act (UrhG) apply.Please note that individual components of the publication may be subject to other licensing or copyright conditions.