Intrinsic Dimension Estimation

Adam Block, Zeyu Jia, Yury Polyanskiy, Alexander RakhlinarXiv 2021 · OpenReview

Abstract

This paper introduces a novel framework for estimating the intrinsic dimension of high-dimensional data manifolds using Wasserstein distances. By leveraging graph-based metrics to approximate geodesic distances, the authors provide the first non-asymptotic guarantees for dimension estimation. The work demonstrates that the sample complexity of generative models like GANs is governed by the data's intrinsic dimensionality rather than its ambient dimension, offering a theoretical explanation for their success in high-dimensional spaces.

Introduction: The Manifold Hypothesis

In modern machine learning, datasets often reside in high-dimensional ambient spaces, such as the 784-pixel space of MNIST images. However, the Manifold Hypothesis posits that such data actually lies on a much lower-dimensional "surface" or manifold. Estimating this intrinsic dimension ($d$) is vital for manifold learning and hyperparameter tuning. Existing estimators frequently struggle with manifolds that are highly curved or folded, often lacking rigorous theoretical guarantees. This research provides a mathematically grounded estimator that remains efficient and accurate even under complex geometric conditions.

Methodology

The proposed approach utilizes a fundamental property of the Wasserstein distance ($W_1$): the distance between a population distribution and an empirical sample of size $n$ scales at a rate of approximately $n^{-1/d}$.

The authors introduce two primary estimators:

  1. $d_n$ (Euclidean): Employs standard Euclidean distance metrics.
  2. $\tilde{d}_n$ (Graph-based): Utilizes a $k$-Nearest Neighbor (kNN) graph to approximate geodesic distance—the distance measured along the manifold's surface.

By comparing two independent samples of sizes $n$ and $\alpha n$, the ratio of their Wasserstein distances allows for the direct calculation of $d$. The graph-based approach is particularly innovative as it handles manifolds with a small reach—areas where distant parts of the manifold are extrinsically close in space, which typically confounds Euclidean-based methods.

Theoretical Insights

A key contribution of this work is the distinction between reach ($\tau$), an extrinsic property of the manifold's embedding, and injectivity radius ($\iota$), an intrinsic property related to curvature. The authors prove that their graph-based estimator $\tilde{d}_n$ remains robust even when the reach is small, provided the injectivity radius is sufficiently large.

Furthermore, this framework provides a theoretical explanation for the success of Generative Adversarial Networks (GANs). The authors establish that GANs converge at a rate of $n^{-1/d}$. This implies that GANs do not suffer from the "curse of dimensionality" associated with the ambient pixel space ($D$), but instead scale according to the much smaller intrinsic dimension ($d$) of the data manifold.

Empirical Results

The effectiveness of the graph-based estimator was demonstrated using the MNIST dataset (specifically the digit '7'). The researchers compared the decay of Wasserstein distances as sample sizes increased for both Euclidean and kNN-based metrics.

Comparison of Euclidean and kNN-based Wasserstein distance scaling for MNIST digit 7.

As shown in the log-log plots, the graph-based approach yields a significantly cleaner linear trend compared to the Euclidean version. The residuals for the kNN-based estimator are more tightly clustered around zero, indicating a more stable and reliable dimension estimate for practitioners working with real-world, non-linear data.

Conclusion and Future Work

This paper establishes a rigorous foundation for intrinsic dimension estimation with finite-sample guarantees. While the current framework assumes data lies exactly on a manifold, future research aims to address "off-manifold" noise, which currently forces estimators to revert to the ambient dimension $D$. Additionally, while the kNN-based approach is more efficient than alternatives like those based on the Traveling Salesman Problem, optimizing the computational cost for massive datasets remains an area for ongoing development.

Summary updated

BibTeX
@misc{block2021intrinsic,
  author = {Adam Block and Zeyu Jia and Yury Polyanskiy and Alexander Rakhlin},
  title = {{Intrinsic Dimension Estimation}},
  year = {2021},
  url = {https://openreview.net/forum?id=Sh8_9AODVMn},
}
Figure