sampling-based dimension reduction for subspace approximation
We give a randomized bi-criteria algorithm for the problem of finding a k -dimensional subspace that minimizesthe L p -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  pk 3 (k/?) 2p ) andproduces a subset of size  (pk 2 (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  (pk 2(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.
subspace approximation