| |
|
| |
|
Amit Deshpande
MIT -Theory Seminar
Sampling techniques in low-rank matrix approximation
March 22, 2006 12:40pm
Abstract:
We consider the problem of approximating a given m by n matrix A by an another matrix of rank k, where k is much smaller than m or n. The "best" such approximation can be computed using Singular Value Decomposition (SVD) but that takes time O(min{mn^2, nm^2}), which is too large for certain applications.
Frieze-Kannan-Vempala (FKV) showed that from a small sample of the rows of A we can compute a low-rank approximation, which is (in
expectation) only an additive error worse than the "best" low-rank approximation. This can be turned into a randomized algorithm to compute this additive low-rank approximation in "linear" (in the number of non-zero entries in A) time.
But in principle, this additive error is unbounded compared to the error of the "best" low-rank approximation. So how about low-rank approximation within a multiplicative error?
Our results are the following.
1. Two different generalizations (Adaptive Sampling and Volume
Sampling) of the sampling technique of FKV.
2. A multiplicative approximation using almost the same number of rows needed for an additive approximation in the FKV result.
3. An algorithm based on this computes a multiplicative low-rank approximation in "linear" time.
(This is joint work with Luis Rademacher, Santosh Vempala, and Grant
Wang.)
If you have questions, or would like to meet the speaker, please contact Ponda at 4-1994 or pondabarnes@tti-c.org. For information on future TTI-C talks or events, please go to the TTI-C Events page.