Matrix Approximation and Projective Clustering via Iterative Sampling
We present two new results for the problem of approximating a given real m by n matrix A by a rank-k matrix D, where k < min{m, n}, so as to minimize ||A-D||_F^2. It is known that bysampling O(k/eps) rows of the matrix, one can find a low-rank approximation with additive error eps||A||_F^2. Our...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30530 |
| _version_ | 1826210241811841024 |
|---|---|
| author | Rademacher, Luis Vempala, Santosh Wang, Grant |
| author2 | Algorithms |
| author_facet | Algorithms Rademacher, Luis Vempala, Santosh Wang, Grant |
| author_sort | Rademacher, Luis |
| collection | MIT |
| description | We present two new results for the problem of approximating a given real m by n matrix A by a rank-k matrix D, where k < min{m, n}, so as to minimize ||A-D||_F^2. It is known that bysampling O(k/eps) rows of the matrix, one can find a low-rank approximation with additive error eps||A||_F^2. Our first result shows that with adaptive sampling in t rounds and O(k/eps) samples in each round, the additive error drops exponentially as eps^t; the computation time is nearly linear in the number of nonzero entries. This demonstrates that multiple passes can be highly beneficial for a natural (and widely studied) algorithmic problem. Our second result is that there exists a subset of O(k^2/eps) rows such that their span contains a rank-k approximation with multiplicative (1+eps) error (i.e., the sum of squares distance has a small \"core-set\" whose span determines a good approximation). This existence theorem leads to a PTAS for the following projective clustering probl! em: Given a set of points P in R^d, and integers k,j, find a set of j subspaces F_1,...,F_j, each of dimension at most k, that minimize \\sum_{p \\in P} min_i d(p,F_i)^2. |
| first_indexed | 2024-09-23T14:46:41Z |
| id | mit-1721.1/30530 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:46:41Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/305302019-04-11T06:23:23Z Matrix Approximation and Projective Clustering via Iterative Sampling Rademacher, Luis Vempala, Santosh Wang, Grant Algorithms We present two new results for the problem of approximating a given real m by n matrix A by a rank-k matrix D, where k < min{m, n}, so as to minimize ||A-D||_F^2. It is known that bysampling O(k/eps) rows of the matrix, one can find a low-rank approximation with additive error eps||A||_F^2. Our first result shows that with adaptive sampling in t rounds and O(k/eps) samples in each round, the additive error drops exponentially as eps^t; the computation time is nearly linear in the number of nonzero entries. This demonstrates that multiple passes can be highly beneficial for a natural (and widely studied) algorithmic problem. Our second result is that there exists a subset of O(k^2/eps) rows such that their span contains a rank-k approximation with multiplicative (1+eps) error (i.e., the sum of squares distance has a small \"core-set\" whose span determines a good approximation). This existence theorem leads to a PTAS for the following projective clustering probl! em: Given a set of points P in R^d, and integers k,j, find a set of j subspaces F_1,...,F_j, each of dimension at most k, that minimize \\sum_{p \\in P} min_i d(p,F_i)^2. 2005-12-22T02:25:21Z 2005-12-22T02:25:21Z 2005-03-29 MIT-CSAIL-TR-2005-018 MIT-LCS-TR-983 http://hdl.handle.net/1721.1/30530 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 19 p. 17195378 bytes 797052 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Rademacher, Luis Vempala, Santosh Wang, Grant Matrix Approximation and Projective Clustering via Iterative Sampling |
| title | Matrix Approximation and Projective Clustering via Iterative Sampling |
| title_full | Matrix Approximation and Projective Clustering via Iterative Sampling |
| title_fullStr | Matrix Approximation and Projective Clustering via Iterative Sampling |
| title_full_unstemmed | Matrix Approximation and Projective Clustering via Iterative Sampling |
| title_short | Matrix Approximation and Projective Clustering via Iterative Sampling |
| title_sort | matrix approximation and projective clustering via iterative sampling |
| url | http://hdl.handle.net/1721.1/30530 |
| work_keys_str_mv | AT rademacherluis matrixapproximationandprojectiveclusteringviaiterativesampling AT vempalasantosh matrixapproximationandprojectiveclusteringviaiterativesampling AT wanggrant matrixapproximationandprojectiveclusteringviaiterativesampling |