Abstract
Manifold learning is essential for uncovering low-dimensional structures in high-dimensional data. However, traditional algorithms often produce negative weights that distort the data's intrinsic geometry. This paper introduces Local Non-negative Pursuit (LNP), an iterative method that ensures sparse, non-negative, and convex representations. By enforcing these constraints, LNP accurately preserves local manifold patches and provides a reliable estimate of intrinsic dimensionality. Experimental results on synthetic and real-world datasets show that LNP outperforms state-of-the-art methods in neighborhood alignment and clustering stability.
The Challenge of Negative Weights in Manifold Learning
Manifold learning aims to uncover the low-dimensional "shape" of high-dimensional data—analogous to flattening a 3D crumpled paper into its original 2D form. Algorithms like Locally Linear Embedding (LLE) typically analyze a data point and its neighbors to reconstruct this shape.
A critical flaw in many existing methods is the generation of negative weights in their mathematical representations. While mathematically convenient for minimizing reconstruction error, negative values imply "subtractive" relationships between data points that lack physical or geometric reality. This "improper neighborhood selection" breaks the intrinsic structure of the manifold, leading to embeddings that fail to reflect the data's true geometry.
Local Non-negative Pursuit (LNP)
The authors propose Local Non-negative Pursuit (LNP), an iterative algorithm designed to select neighbors that guarantee a non-negative, sparse, and convex representation. Unlike standard K-Nearest Neighbors (KNN) which uses a fixed heuristic, LNP is adaptive. It starts with the single nearest neighbor and greedily adds more from a candidate set only if they satisfy a specific geometric condition ensuring the point's projection remains within a "non-negative affine subspace."
This approach results in a Sparse Convex Representation (SCR) where weights are non-negative, sum to one, and are naturally sparse. Because the SCR is sparse, the number of non-zero weights provides a direct hint about the manifold's actual dimensionality ($d$). The authors utilize a "manifold dimensionality estimation vector" (dev) to calculate this intrinsic dimension accurately.
Experimental Evaluation
The researchers evaluated LNP against state-of-the-art methods, including LLE, Laplacian Eigenmaps (LEM), and Sparse Manifold Clustering Embedding (SMCE), using a variety of datasets:
- Synthetic Manifolds: A Trefoil knot (110 points in 100D space) and intertwined "2-trefoil-knots" (400 points).
- Real-world Data: The COIL-20 object dataset and the Extended YaleB face database, which contains over 2,400 images under varying illumination.
Key Results and Insights
The core finding is that negative weights equal distorted reality. By forcing representations to be convex combinations, LNP ensures every point is represented as a "weighted average" of its neighbors, keeping it firmly within the local geometry.
Key performance highlights include:
- Superior Preservation: LNP consistently outperformed other methods in neighborhood alignment accuracy (
nalac), keeping local structures intact after compression. - Robust Clustering: On intertwined trefoil knots—a notoriously difficult test—LNP achieved stable, low misclassification rates, whereas other methods fluctuated wildly based on neighborhood size.
- Efficiency: LNP proved significantly faster than SMCE, particularly as dataset sizes increased.
- Dimensionality Accuracy: The proposed dev vector accurately identified intrinsic dimensions where traditional methods struggled with noise.
Conclusion
LNP provides a robust solution for manifold preservation by addressing the fundamental issue of negative components. While the algorithm relies on the "Manifold Assumption" (requiring sufficiently dense sampling), it offers a more natural and adaptive way to define neighborhoods. Future work may explore the algorithm's sensitivity to extreme noise and its scalability for massive, billion-point datasets through parallelization.
Summary updated