An axiomatic approach to intrinsic dimension of a dataset

DOI10.1016/J.NEUNET.2007.12.030zbMATH Open1254.68102DBLPjournals/nn/Pestov08arXiv0712.2063OpenAlexW1489992831WikidataQ51895521 ScholiaQ51895521MaRDI QIDQ1931997FDOQ1931997

Authors: Vladimir G. Pestov 

Publication date: 17 January 2013

Published in: Neural Networks (Search for Journal in Brave)

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 (arXiv:cs/0703125). 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 prohibitevely high computational complexity (computing it is an $NP$-complete problem). We outline a possible way to overcome these difficulties.

Full work available at URL: https://arxiv.org/abs/0712.2063

Recommendations

• Intrinsic dimension of geometric data sets
• Intrinsic dimension estimation: advances and open problems
• Intrinsic dimension estimation of data: An approach based on Grassberger-Procaccia's algorithm
• Intrinsic dimension estimation: relevant techniques and a benchmark framework
• Intrinsic dimension identification via graph-theoretic methods
• A fundamental bias in calculating dimensions from finite data sets
• scientific article

zbMATH Keywords

curse of dimensionalityfeaturesconcentration of measureGromov distancehigh-dimensional noiseintrinsic dimension of datasetsrandom sample of a manifoldspace with metric and measure

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Searching and sorting (68P10)

Cites Work

• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• The concentration of measure phenomenon
• Title not available (Why is that?)
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Neural Network Learning
• On the geometry of similarity search: dimensionality curse and concentration of measure
• Geodesic Entropic Graphs for Dimension and Entropy Estimation in Manifold Learning
• In search of non-Gaussian components of a high-dimensional distribution
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distance-based classification with Lipschitz functions

Cited In (12)

• Prequential analysis of complex data with adaptive model reselection
• A new inductive approach for counting dimension in large scale
• Intrinsic dimension estimation: advances and open problems
• Measuring evolving data streams' behavior through their intrinsic dimension
• Indexability, concentration, and VC theory
• Intrinsic dimension estimation: relevant techniques and a benchmark framework
• Intrinsic dimension of geometric data sets
• Dimension estimation using weighted correlation dimension method
• Anderson relaxation test for intrinsic dimension selection in model-based clustering
• Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions
• Is the \(k\)-NN classifier in high dimensions affected by the curse of dimensionality?
• A fundamental bias in calculating dimensions from finite data sets

Uses Software

• IntDim

This page was built for publication: An axiomatic approach to intrinsic dimension of a dataset

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1931997)