Conference proceeding
Projective clustering in high dimensions using core-sets
Proceedings of the eighteenth annual symposium on computational geometry, pp.312-318
SCG '02
06/05/2002
DOI: 10.1145/513400.513440
Abstract
(MATH) Let P be a set of n points in $\Re d , and for any integer 0 k d --1, let $\RD k ( P ) denote the minimum over all k -flats $\FLAT$ of max pε P Dist( p ,\FLAT). We present an algorithm that computes, for any 0 < ε < 1, a k -flat that is within a distance of (1 + $egr;) \RD k ( P ) from each point of P . The running time of the algorithm is d n O(k/ε 5 log(1/ε)) . The crucial step in obtaining this algorithm is a structural result that says that there is a near-optimal flat that lies in an affine subspace spanned by a small subset of points in P . The size of this "core-set" depends on k and ε but is independent of the dimension.This approach also extends to the case where we want to find a k -flat that is close to a prescribed fraction of the entire point set, and to the case where we want to find j flats, each of dimension k , that are close to the point set. No efficient approximation schemes were known for these problems in high-dimensions, when k >1 or j >1.
Details
- Title: Subtitle
- Projective clustering in high dimensions using core-sets
- Creators
- Sariel Har-Peled - University of Illinois Urbana-ChampaignKasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the eighteenth annual symposium on computational geometry, pp.312-318
- Publisher
- ACM
- Series
- SCG '02
- DOI
- 10.1145/513400.513440
- Language
- English
- Date published
- 06/05/2002
- Academic Unit
- Computer Science
- Record Identifier
- 9984259411902771
Metrics
10 Record Views