Fast monte-carlo algorithms for finding low-rank approximations.
We consider the problem of approximating a given m × n matrix A by another matrix of specified rank k, which is smaller than m and n. The Singular Value Decomposition (SVD) can be used to find the "best" such approximation. However, it takes time polynomial in m, n which is prohibitive for...
| Publicado en: | Journal of the ACM 51, 6 (2004). |
|---|---|
| Autor Principal: | |
| Formato: | Artigo |
| Idioma: | inglés |
| Subjects: |