Projective Clustering in High Dimensions using Core-Sets

Sariel Har-Peled and Kasturi R. Varadarajan

In this paper, we show that there exists a small core-set for the problem of computing the ``smallest'' radius k-flat for a given point-set in R^d. The size of the core-set is dimension independent. Such small core-sets yield immediate efficient algorithms for finding the (1+µ)-approximate smallest radius k-flat for the points in d n^{O(k/µ^5 log(1/µ))} time. Furthermore, we can use it to (1+µ)-approximate the the smallest radius k-flat for a prespecified fraction of the given points, in the same running time. Our algorithm can also be used for computing the min-max such coverage of the point-set by j flats, each one of them of dimension k.

No previous efficient approximation algorithms were known for those problems in high-dimensions, when k>1 or j>1.

@string{SOCG_2002 = "Proc. 18th Annu. ACM Sympos. Comput. Geom."}

@inproceedings{hv-pchdu-02,
  author =       "S. {Har-Peled} and K. R. Varadarajan",
  booktitle =    SOCG_2002,
  title =        "Projective Clustering in High Dimensions using Core-Sets",
  year =         2002,
  pages =        {312--318}
}