Name
Abstract | ||
|---|---|---|
Frieze et al. [17] proved that a small sample of rows of a given matrix A contains a low-rank approximation D that minimizes ||A - D||F to within small additive error, and the sampling can be done efficiently using just two passes over the matrix [12]. In this paper, we generalize this result in two ways. First, we prove that the additive error drops exponentially by iterating the sampling in an adaptive manner. Using this result, we give a pass-efficient algorithm for computing low-rank approximation with reduced additive error. Our second result is that using a natural distribution on subsets of rows (called volume sampling), there exists a subset of k rows whose span contains a factor (k + 1) relative approximation and a subset of k + k(k + 1)/ε rows whose span contains a 1+ε relative approximation. The existence of such a small certificate for multiplicative low-rank approximation leads to a PTAS for the following projective clustering problem: Given a set of points P in Rd, and integers k, j, find a set of j subspaces F1, . . ., Fj, each of dimension at most k, that minimize Σp∈Pminid(p, Fi)2.
|
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1109557.1109681 | SODA: Symposium on Discrete Algorithms |
Keywords | Field | DocType |
small sample,reduced additive error,matrix approximation,relative approximation,small additive error,low-rank approximation,projective clustering.,k row,projective clustering,small certificate,additive error,algorithms,integers k,multiplicative low-rank approximation,volume sampling,polytope,vertex,cycle,linear inequalities,polyhedron,face,graph,facet | Integer,Discrete mathematics,Combinatorics,Multiplicative function,Vertex (geometry),Matrix (mathematics),Linear subspace,Polytope,Sampling (statistics),Linear inequality,Mathematics | Journal |
Volume | Issue | ISBN |
2 | 1 | 0-89871-605-5 |
Citations | PageRank | References |
103 | 7.21 | 30 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amit Deshpande | 1 | 676 | 40.91 |
| Luis Rademacher | 2 | 269 | 21.60 |
| Santosh Vempala | 3 | 3546 | 523.21 |
| Grant Wang | 4 | 342 | 27.05 |