IAN: Iterated Adaptive Neighborhoods for Manifold Learning and Dimensionality Estimation

Area of Science:

• Machine Learning
• Data Science
• Computational Geometry

Background:

• Manifold learning in machine learning often assumes known manifold geometry and dimension.
• Real-world data frequently exhibit limited sampling, non-uniformity, and unknown manifold properties.
• Adaptive neighborhoods are crucial for accurately reflecting local data structure.

Purpose of the Study:

• To develop an algorithm for inferring adaptive neighborhoods from data represented by a similarity kernel.
• To address the challenges posed by limited, non-uniformly sampled, and geometrically unknown data manifolds.
• To improve the performance of manifold learning algorithms under practical data constraints.

Main Methods:

• Iterative sparsification of an initial locally conservative neighborhood (Gabriel) graph.
• Utilizing a weighted graph counterpart for sparsification.
• Employing linear programming for minimal neighborhood determination and volumetric statistics for outlier detection.

Main Results:

• The algorithm successfully infers adaptive neighborhoods tailored to local data structure.
• Demonstrated effectiveness in nonlinear dimensionality reduction, geodesic computation, and dimension estimation.
• Outperformed standard algorithms, such as k-nearest neighbors, in comparative analyses.

Conclusions:

• The proposed adaptive neighborhood inference method enhances manifold learning robustness.
• It provides a valuable tool for analyzing complex, real-world datasets where manifold properties are not predefined.
• The approach offers significant improvements over traditional neighborhood selection techniques.