[edit]
Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7948-7957, 2021.
Abstract
Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset X onto a random d=O(dX)-dimensional subspace (where dX is the doubling dimension of X), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension d having an extra loglogn term and the approximation factor being arbitrarily close to 1. Furthermore, we extend these results to approximating {\em solutions} instead of just their {\em costs}. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of k-means and k-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of X.