Journal article
Efficient Subspace Approximation Algorithms
Discrete & Computational Geometry, Vol.47(1), pp.44-63
01/2012
DOI: 10.1007/s00454-011-9384-2
Abstract
We consider the problem of fitting a subspace of a specified dimension k to a set P of n points in ℝ d . The fit of a subspace F is measured by the L τ norm, that is, it is defined as the τ-root of the sum of the τth powers of the Euclidean distances of the points in P from F, for some τ≥1. Our main result is a randomized algorithm that takes as input P, k, and a parameter 0<ε<1; runs in $nd \cdot2^{O(\frac{\tau k^{2}}{\varepsilon} \log^{2} \frac {k}{\varepsilon})}$ time, and returns a k-subspace that with probability at least 1/2 has a fit that is at most (1+ε) times that of the optimal k-subspace.
Details
- Title: Subtitle
- Efficient Subspace Approximation Algorithms
- Creators
- Nariankadu Shyamalkumar - grid.214572.7 0000000419368294 Department of Statistics and Actuarial Science University of Iowa Iowa City IA USAKasturi Varadarajan - grid.214572.7 0000000419368294 Department of Computer Science University of Iowa Iowa City IA USA
- Resource Type
- Journal article
- Publication Details
- Discrete & Computational Geometry, Vol.47(1), pp.44-63
- Publisher
- Springer-Verlag; New York
- DOI
- 10.1007/s00454-011-9384-2
- ISSN
- 0179-5376
- eISSN
- 1432-0444
- Language
- English
- Date published
- 01/2012
- Academic Unit
- Statistics and Actuarial Science; Computer Science
- Record Identifier
- 9983985937102771
Metrics
14 Record Views