Diverse Landmark Sampling from Determinantal Point Processes for Scalable Manifold Learning
This addresses scalability issues in manifold learning for researchers and practitioners dealing with large datasets, though it is incremental as it builds on existing landmark selection strategies.
The paper tackled the high computational cost of manifold learning for large datasets by proposing an efficient landmark sampling method using determinantal point processes, achieving significant performance improvements over state-of-the-art techniques.
High computational costs of manifold learning prohibit its application for large point sets. A common strategy to overcome this problem is to perform dimensionality reduction on selected landmarks and to successively embed the entire dataset with the Nyström method. The two main challenges that arise are: (i) the landmarks selected in non-Euclidean geometries must result in a low reconstruction error, (ii) the graph constructed from sparsely sampled landmarks must approximate the manifold well. We propose the sampling of landmarks from determinantal distributions on non-Euclidean spaces. Since current determinantal sampling algorithms have the same complexity as those for manifold learning, we present an efficient approximation running in linear time. Further, we recover the local geometry after the sparsification by assigning each landmark a local covariance matrix, estimated from the original point set. The resulting neighborhood selection based on the Bhattacharyya distance improves the embedding of sparsely sampled manifolds. Our experiments show a significant performance improvement compared to state-of-the-art landmark selection techniques.