Shape Dimension and Intrinsic Metric from Samples of Manifolds

Joachim Giesen, Uli WagnerDiscret. Comput. Geom 2004 · DOI

Abstract

This paper addresses the "curse of dimensionality" in manifold learning by introducing the adaptive neighborhood graph, a computationally efficient data structure. Unlike traditional methods that scale exponentially with ambient space, this approach correctly infers a manifold's dimension and connectivity with a complexity primarily dependent on its intrinsic dimension. We present the theoretical foundations of this method, including its adaptive construction, dimension detection algorithms, and proofs of geodesic convergence.

The Challenge of High-Dimensional Manifold Learning

Manifold learning seeks to recover the structure of a low-dimensional $k$-dimensional manifold embedded within a high-dimensional space $\mathbb{R}^d$. A classic example is a 2D sheet of paper crumpled in 3D space, or complex speech features represented by high-dimensional audio samples. The primary obstacle is the curse of dimensionality: standard geometric tools like Delaunay triangulations have a complexity of $n^{d/2}$, rendering them impractical when the ambient dimension $d$ is large. While various heuristics exist, they often lack the theoretical guarantees necessary for robust analysis. Giesen and Wagner propose a method that is both provably correct and computationally feasible when $d \gg k$.

The Adaptive Neighborhood Graph

The authors propose the adaptive neighborhood graph ($G_c(P)$) to overcome the limitations of fixed-radius or fixed-neighbor approaches, which typically fail under varying sampling densities.

Construction and Adaptivity

The graph construction utilizes a relative distance metric: a point $q$ is connected to $p$ if the distance $\|p-q\|$ is at most $c$ times the distance from $p$ to its absolute nearest neighbor. This allows the graph to "adapt" to local density, zooming in where data is dense and out where it is sparse. This construction relies on an $(\epsilon, \delta)$-sampling condition, which ensures the sample is dense enough to capture the manifold's local feature size without excessive clutter.

Dimension Detection

To identify the intrinsic dimension $k$, the algorithm iteratively fits $l$-dimensional subspaces to local neighborhoods. Using a specialized approximation algorithm, it identifies $k$ as the smallest dimension where the sample points lie sufficiently close to a flat subspace. Crucially, the dependence on the ambient dimension $d$ in this process is linear, not exponential.

Key Results and Theoretical Insights

  • Intrinsic Complexity: By focusing on the intrinsic dimension $k$, the complexity is reduced from $n^{d/2}$ to approximately $2^{O(k)}n$. In many applications where $k$ is small, this results in a graph of linear size.
  • Provable Connectivity: The authors prove that with adequate sampling, the graph maintains the same number of connected components as the underlying manifold.
  • Geodesic Convergence: As sampling density increases, the shortest path in the graph converges to the true geodesic distance on the manifold with an error factor of $(1 + O(\epsilon^2))$. This was illustrated using synthetic examples, such as mapping a regular hexagonal grid onto a manifold to observe how the constant $c$ affects distance approximation.
  • Computational Speed: The dimension detection algorithm runs in $d 2^{O(k^7 \log k)}$ time per connected component, ensuring scalability for high-dimensional data.

Limitations and Future Work

The $(\epsilon, \delta)$-sampling condition is theoretically robust but practically strict, as real-world data often contains noise and outliers. The authors suggest that hybrid approaches—combining adaptive neighborhood graphs with $k$-nearest neighbor strategies—may offer better practical performance. Future research will also target full manifold reconstruction, extending beyond the current focus on dimension, connectivity, and distance metrics.

Summary updated

BibTeX
@article{giesen2004shape,
  author = {Joachim Giesen and Uli Wagner},
  title = {{Shape Dimension and Intrinsic Metric from Samples of Manifolds}},
  journal = {Discret. Comput. Geom.},
  year = {2004},
  doi = {10.1007/s00454-004-1120-8},
}
Figure