Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR06-042 | 16th March 2006 00:00

#### Adaptive Sampling and Fast Low-Rank Matrix Approximation

TR06-042
Authors: Amit Deshpande, Santosh Vempala
Publication: 21st March 2006 14:40
Keywords:

Abstract:

We prove that any real matrix \$A\$ contains a subset of at most
\$4k/\eps + 2k \log(k+1)\$ rows whose span ``contains" a matrix of
rank at most \$k\$ with error only \$(1+\eps)\$ times the error of the
best rank-\$k\$ approximation of \$A\$. This leads to an algorithm to
find such an approximation with complexity essentially
\$O(Mk/\eps)\$, where \$M\$ is the number of nonzero entries of \$A\$.
The algorithm maintains sparsity, and in the streaming model, it
can be implemented using only \$2(k+1)(\log(k+1)+1)\$ passes over
the input matrix. Previous algorithms for low-rank approximation
use only one or two passes but obtain an additive approximation.

ISSN 1433-8092 | Imprint