Projective clustering in high dimensions using core-sets

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 max_pε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 dn^{O(κ/ε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.