Theory Lunch Seminar

  • Gates Hillman 8102 and Zoom
  • In Person and Virtual ET
  • Ph.D. Student, Theoretical Computer Science
  • Department of Electrical Engineering and Computer Science.
  • Massachusetts Institute of Technology

Dimensionality Reduction for Clustering Problems

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(d_X)-dimensional subspace (where d_X 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 log(log n) term and the approximation factor being arbitrarily close to 1. Furthermore, we extend these results to approximating solutions instead of just their costs. 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. Some open problems will also be discussed.

In Person and Zoom Participation. See announcement.

For More Information, Please Contact: