An axiomatic approach to intrinsic dimension of a dataset

DOI10.1016/J.NEUNET.2007.12.030MaRDI QIDQ1931997zbMATHOpenAlexDBLPWikidataFDO

Authors Vladimir G. Pestov

Publication date 17 January 2013

Published in Neural Networks (Search for Journal in Brave)

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

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)

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.

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 DE number 3864315

Cites work

• scientific article; zbMATH DE number 1643847 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1950575 (Why is no real title available?)
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Distance-based classification with Lipschitz functions
• Geodesic Entropic Graphs for Dimension and Entropy Estimation in Manifold Learning
• In search of non-Gaussian components of a high-dimensional distribution
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• 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
• The concentration of measure phenomenon

Cited in

(13)

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

Describes a project that uses

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)