A Universal Nearest-Neighbor Estimator for Intrinsic Dimensionality

• URL: http://arxiv.org/abs/2603.10493v1
• Date: Wed, 11 Mar 2026 07:40:45 GMT
• Title: A Universal Nearest-Neighbor Estimator for Intrinsic Dimensionality
• Abstract summary: Estimating the intrinsic dimensionality (ID) of data is a fundamental problem in machine learning and computer vision.<n>We introduce a novel ID estimator based on nearest-neighbor distance ratios that involves simple calculations and achieves state-of-the-art results.
• Score: 5.803951735793419
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Estimating the intrinsic dimensionality (ID) of data is a fundamental problem in machine learning and computer vision, providing insight into the true degrees of freedom underlying high-dimensional observations. Existing methods often rely on geometric or distributional assumptions and can significantly fail when these assumptions are violated. In this paper, we introduce a novel ID estimator based on nearest-neighbor distance ratios that involves simple calculations and achieves state-of-the-art results. Most importantly, we provide a theoretical analysis proving that our estimator is \emph{universal}, namely, it converges to the true ID independently of the distribution generating the data. We present experimental results on benchmark manifolds and real-world datasets to demonstrate the performance of our estimator.

Related papers

• Manifold Dimension Estimation: An Empirical Study [0.0]
  The manifold hypothesis suggests that high-dimensional data often lie on or near a low-dimensional manifold.<n>Estimating the dimension of this manifold is essential for leveraging its structure.<n>This article provides a comprehensive survey for both researchers and practitioners.
  arXiv  Detail & Related papers  (2025-09-19T01:48:58Z)
• A Survey of Dimension Estimation Methods [0.0]
  It is important to understand the real dimension of the data, hence the complexity of the dataset at hand.<n>This survey reviews a wide range of dimension estimation methods, categorising them by the geometric information they exploit.<n>The paper evaluates the performance of these methods, as well as investigating varying responses to curvature and noise.
  arXiv  Detail & Related papers  (2025-07-18T13:05:42Z)
• Graph-based Complexity for Causal Effect by Empirical Plug-in [56.14597641617531]
  This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. We show that computation can be done efficiently, potentially in time linear in the data size, depending on the estimand's hypergraph.
  arXiv  Detail & Related papers  (2024-11-15T07:42:01Z)
• (Deep) Generative Geodesics [57.635187092922976]
  We introduce a newian metric to assess the similarity between any two data points. Our metric leads to the conceptual definition of generative distances and generative geodesics. Their approximations are proven to converge to their true values under mild conditions.
  arXiv  Detail & Related papers  (2024-07-15T21:14:02Z)
• Intrinsic Dimensionality Estimation within Tight Localities: A Theoretical and Experimental Analysis [0.0]
  We propose a local ID estimation strategy stable even for tight' localities consisting of as few as 20 sample points. Our experimental results show that our proposed estimation technique can achieve notably smaller variance, while maintaining comparable levels of bias, at much smaller sample sizes than state-of-the-art estimators.
  arXiv  Detail & Related papers  (2022-09-29T00:00:11Z)
• Intrinsic Dimension Estimation [92.87600241234344]
  We introduce a new estimator of the intrinsic dimension and provide finite sample, non-asymptotic guarantees. We then apply our techniques to get new sample complexity bounds for Generative Adversarial Networks (GANs) depending on the intrinsic dimension of the data.
  arXiv  Detail & Related papers  (2021-06-08T00:05:39Z)
• OR-Net: Pointwise Relational Inference for Data Completion under Partial Observation [51.083573770706636]
  This work uses relational inference to fill in the incomplete data. We propose Omni-Relational Network (OR-Net) to model the pointwise relativity in two aspects.
  arXiv  Detail & Related papers  (2021-05-02T06:05:54Z)
• High-Dimensional Multi-Task Averaging and Application to Kernel Mean Embedding [0.0]
  We propose an improved estimator for the multi-task averaging problem. We prove theoretically that this approach provides a reduction in mean squared error. An application of this approach is the estimation of multiple kernel mean embeddings.
  arXiv  Detail & Related papers  (2020-11-13T07:31:30Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  We propose to use a nearest-neighbor-based $gamma$-divergence estimator as a data discrepancy measure. Our method achieves significantly higher robustness than existing discrepancy measures.
  arXiv  Detail & Related papers  (2020-06-13T06:09:27Z)
• Distribution Approximation and Statistical Estimation Guarantees of Generative Adversarial Networks [82.61546580149427]
  Generative Adversarial Networks (GANs) have achieved a great success in unsupervised learning. This paper provides approximation and statistical guarantees of GANs for the estimation of data distributions with densities in a H"older space.
  arXiv  Detail & Related papers  (2020-02-10T16:47:57Z)
• Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence [7.011897575776511]
  We show that the estimator is robust to both dependence and to the presence of outliers in the dataset.<n>We provide a theoretical study of the gradient descent algorithm used to compute the estimator.
  arXiv  Detail & Related papers  (2019-12-12T02:28:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.