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.
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.
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