Unsupervised Dimensionality Estimation and Manifold Learning in high-dimensional Spaces by Tensor Voting

Philippos Mordohai, Gérard G. Medioni

Abstract

Manifold learning seeks to uncover low-dimensional structures hidden within high-dimensional data. Traditional global methods, such as Isomap and LLE, often struggle with non-convex shapes, require pre-specified target dimensions, and suffer from high computational complexity. This paper introduces a local, unsupervised framework that utilizes tensor voting to estimate the intrinsic dimensionality and orientation of data. By representing data points as second-order tensors and employing an efficient voting mechanism, the proposed method handles datasets with varying local dimensions and scales linearly with the number of points, demonstrating significant robustness in high-dimensional ambient spaces.

Introduction

The goal of manifold learning is to discover the underlying low-dimensional structure of data points embedded in a high-dimensional space. Existing state-of-the-art methods face three primary hurdles: global optimization constraints that are computationally expensive ($O(n^2)$ or $O(n^3)$), the assumption of a fixed target dimensionality across the entire dataset, and a reliance on local linearity that fails in the presence of high intrinsic curvature.

To address these challenges, this work proposes a purely local method that "senses" the manifold's structure point-by-point. By avoiding global "unfolding," the approach can naturally represent complex structures like spheres or mixed-dimensional datasets that are topologically difficult to flatten.

The Tensor Voting Framework

The core of the approach is the extension of tensor voting—a technique originally developed for 2D and 3D computer vision—to $D$-dimensional spaces.

Data Representation and Voting

Each data point is represented as a second-order, symmetric, non-negative definite tensor, visualized as an ellipsoid. The shape of this ellipsoid encodes the structural type: a "stick" shape implies a 1D curve, while a "sphere" shape implies an isotropic structure or lack of orientation preference.

Figure 3: (a) Example tensors representing different structural types and (b) the basic geometry of vote generation between a voter and a receiver.

During the voting process, every point casts a vote to its neighbors. A vote is a tensor that communicates the likely orientation of the manifold at the receiver's location, based on the voter's own orientation and the smooth arc (geodesic) connecting them. This allows the system to maintain a rich representation of uncertainty and multiple potential orientations simultaneously.

Efficient High-Dimensional Computation

Standard tensor voting requires expensive numerical integration in high dimensions. To overcome this, the authors introduced a novel approximation that decomposes tensors into a new basis, allowing for direct computation. This reduces the complexity to $O(Dn \log n)$, where $n$ is the number of points and $D$ is the ambient dimension.

Figure 5: Visualization of the tensor decomposition used to efficiently compute votes in higher dimensions, showing the relationship between normal and tangential components.

Dimensionality Estimation

After votes are accumulated, the local dimensionality $d$ is determined by finding the maximum gap between sorted eigenvalues of the resulting tensor. This parameter-free method allows the algorithm to discover that different parts of a dataset may have different intrinsic dimensions (e.g., a line intersecting a sphere) without user intervention.

Experimental Results

The method was evaluated on several benchmarks:

  • Swiss Roll: Achieved over 99% accuracy in local dimensionality estimation across various scale parameters.
  • Mixed Dimensions: Successfully classified points into 1D, 2D, and 3D structures within a single 4D space—a task where Isomap and LLE typically fail due to their global $d$ assumptions.
  • High-D Robustness: In 150-dimensional space, the method maintained 97.3% accuracy in estimating intrinsic dimensionality, even in the presence of uniform noise.
  • Efficiency: A 135,000-point dataset was processed in approximately 2 hours on standard contemporary hardware, demonstrating superior scalability compared to global matrix-inversion methods.

Conclusion

Tensor voting provides a robust, local, and scalable alternative for manifold learning. By propagating tensors rather than scalars or vectors, the framework preserves structural information and handles non-manifold topologies effectively. While the method is sensitive to sampling density and ambient dimensionality (limited to a few hundred dimensions due to $O(D^2)$ storage), it represents a significant step toward parameter-free, unsupervised structural analysis of high-dimensional data.

Summary updated

Abstract

We address dimensionality estimation and nonlinear manifold inference starting from point inputs in high dimensional spaces using tensor voting. The proposed method operates locally in neighborhoods and does not involve any global computations. It is based on information propagation among neighboring points implemented as a voting process. Unlike other local approaches for manifold learning, the quantity propagated from one point to another is not a scalar, but is in the form of a tensor that provides considerably richer information. The accumulation of votes at each point provides a reliable estimate of local dimensionality, as well as of the orientation of a potential manifold going through the point. Reliable dimensionality estimation at the point level is a major advantage over competing methods. Moreover, the absence of global operations allows us to process significantly larger datasets. We demonstrate the effectiveness of our method on a variety of challenging datasets.
BibTeX
@inproceedings{mordohai2005unsupervised,
  author = {Philippos Mordohai and Gérard G. Medioni},
  title = {{Unsupervised Dimensionality Estimation and Manifold Learning in high-dimensional Spaces by Tensor Voting}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure