Projective clustering in high dimensions using core-sets

Sariel Har-Peled, Kasturi Varadarajan

Research output: Contribution to conferencePaperpeer-review

Abstract

Let P be a set of n points in ℝd, and for any integer 0 ≤ κ ≤ d - 1, let RDκ(P) denote the minimum over all κ-flats ℱ of maxpεP dist(p, ℱ). We present an algorithm that computes, for any 0 < ε < 1, a κ-flat that is within a distance of (1 + ε)RDκ(P) from each point of P. The running time of the algorithm is dnO(κ/ε5log(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 κ and ε but is independent of the dimension. This approach also extends to the case where we want to find a κ-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 κ, that are close to the point set. No efficient approximation schemes were known for these problems in high-dimensions, when κ > 1 or j > 1.

Original languageEnglish (US)
Pages312-318
Number of pages7
StatePublished - Jan 1 2002
EventProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain
Duration: Jun 5 2002Jun 7 2002

Other

OtherProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02)
Country/TerritorySpain
CityBarcelona
Period6/5/026/7/02

Keywords

  • Computational convexity
  • Projective clustering

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Projective clustering in high dimensions using core-sets'. Together they form a unique fingerprint.

Cite this