Sampling-based dimension reduction for subspace approximation

Abstract

We give a randomized bi-criteria algorithm for the problem of finding a k-dimensional subspace that minimizesthe Lp-error for given points, i.e., p-th root of the sum of p-th powers of distances to given points,for any p ≥ 1. Our algorithm runs in time Õ (mn · pk3 (k/ε)2p) andproduces a subset of size Õ (pk2 (k/ε)2p) from the given points such that, withhigh probability, the span of these points gives a (1+ε)-approximation to the optimal k-dimensionalsubspace. We also show a dimension reduction type of result for this problem where we can efficiently find asubset of size Õ (pk2(p+1) + (k/ε)p+2) such that, with high probability, theirspan contains a k-dimensional subspace that gives (1+ε)-approximation to the optimum. We prove similarresults for the corresponding projective clustering problem where we need to find multiple k-dimensional subspaces.