Projective clustering in high dimensions using core-sets

Abstract

(MATH) Let P be a set of n points in $\Red, and for any integer 0 ≤ k ≤ d--1, let $\RDk(P) denote the minimum over all k-flats $\FLAT$ of maxpε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;) \RDk(P) from each point of P. The running time of the algorithm is dnO(k/ε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 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.