Conference proceeding
Sampling-based dimension reduction for subspace approximation
Proceedings of the thirty-ninth annual ACM symposium on theory of computing, pp.641-650
STOC '07
06/11/2007
DOI: 10.1145/1250790.1250884
Abstract
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.
Details
- Title: Subtitle
- Sampling-based dimension reduction for subspace approximation
- Creators
- Amit Deshpande - Massachusetts Institute of TechnologyKasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the thirty-ninth annual ACM symposium on theory of computing, pp.641-650
- Publisher
- ACM
- Series
- STOC '07
- DOI
- 10.1145/1250790.1250884
- ISSN
- 0737-8017
- Language
- English
- Date published
- 06/11/2007
- Academic Unit
- Computer Science
- Record Identifier
- 9984259491702771
Metrics
6 Record Views