title: An axiomatic approach to intrinsic dimension of a dataset.
abstract: We perform a deeper analysis of an axiomatic approach to the concept of intrinsic dimension of a dataset proposed by us in the IJCNN'07 paper. The main features of our approach are that a high intrinsic dimension of a dataset reflects the presence of the curse of dimensionality (in a certain mathematically precise sense), and that dimension of a discrete i.i.d. sample of a low-dimensional manifold is, with high probability, close to that of the manifold. At the same time, the intrinsic dimension of a sample is easily corrupted by moderate high-dimensional noise (of the same amplitude as the size of the manifold) and suffers from prohibitively high computational complexity (computing it is an NP-complete problem). We outline a possible way to overcome these difficulties.
authors.affiliation: Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, Ottawa, ON, K1N 6N5, Canada. vpest283@uottawa.ca
authors.forename: Vladimir
authors.initials: V
authors.lastname: Pestov
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D017711:Nonlinear Dynamics; D010363:Pattern Recognition, Automated