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.

Authors

• Amit Deshpande 0001
• Kasturi R. Varadarajan

Keywords

• subspace approximation