Intrinsic Dimension Estimation for Discrete Metrics
Open Access
- 8 February 2023
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 130 (6) , 067401
Abstract
Real-world datasets characterized by discrete features are ubiquitous: from categorical surveys to clinical questionnaires, from unweighted networks to DNA sequences. Nevertheless, the most common unsupervised dimensional reduction methods are designed for continuous spaces, and their use for discrete spaces can lead to errors and biases. In this Letter we introduce an algorithm to infer the intrinsic dimension (ID) of datasets embedded in discrete spaces. We demonstrate its accuracy on benchmark datasets, and we apply it to analyze a metagenomic dataset for species fingerprinting, finding a surprisingly small ID, of order 2. This suggests that evolutive pressure acts on a low-dimensional manifold despite the high dimensionality of sequences’ space.Keywords
All Related Versions
Funding Information
- Horizon 2020 Framework Programme (824143)
This publication has 25 references indexed in Scilit:
- Representation Learning: A Review and New PerspectivesIEEE Transactions on Pattern Analysis and Machine Intelligence, 2013
- Distance distributions in random networksAd Hoc Networks, 2012
- Computing the continuous discretely: integer-point enumeration in polyhedraChoice Reviews Online, 2007
- ON EFFICIENT BOX COUNTING ALGORITHMSInternational Journal of Modern Physics C, 1993
- Efficient box-counting determination of generalized fractal dimensionsPhysical Review A, 1990
- Towards a natural system of organisms: proposal for the domains Archaea, Bacteria, and Eucarya.Proceedings of the National Academy of Sciences, 1990
- Estimating fractal dimensionJournal of the Optical Society of America A, 1990
- On the evolutionary descent of organisms and organelles: a global phylogeny based on a highly conserved structural core in small subunit ribosomal RNANucleic Acids Research, 1984
- Fractal Dimension of Dielectric BreakdownPhysical Review Letters, 1984
- Characterization of Strange AttractorsPhysical Review Letters, 1983