Sampling from Determinantal Point Processes for Scalable Manifold Learning.

Area of Science:

• Computational geometry
• Machine learning
• Data science

Background:

• Manifold learning is computationally expensive for large datasets.
• The Nyström method uses landmarks for dimensionality reduction, but challenges exist in non-Euclidean spaces.
• Selecting landmarks that minimize reconstruction error and accurately represent the manifold is crucial.

Purpose of the Study:

• To address the high computational costs of manifold learning for large datasets.
• To propose an efficient landmark selection strategy for non-Euclidean geometries.
• To improve the accuracy of manifold embedding with sparse landmark sampling.

Main Methods:

• Landmark sampling from determinantal distributions on non-Euclidean spaces.
• An efficient linear-complexity approximation for determinantal sampling.
• Local covariance matrix estimation for each landmark to recover geometry.
• Neighborhood selection using Bhattacharyya distance for improved embedding.

Main Results:

• Demonstrated significant performance improvements over state-of-the-art techniques.
• Successfully applied the method to both synthetic and medical datasets.
• The proposed method enhances the approximation of manifolds from sparsely sampled landmarks.

Conclusions:

• The novel determinantal sampling and local geometry recovery method effectively reduces manifold learning costs.
• This approach overcomes key challenges in landmark selection for non-Euclidean data.
• The technique offers a practical solution for applying manifold learning to large-scale, complex datasets.