Name
Abstract | ||
|---|---|---|
The CUR decomposition of an m×n matrix A finds an m×c matrix C with a small subset of c < n columns of A, together with an r×n matrix R with a small subset of r < m rows of A, as well as a c×r low rank matrix U such that the matrix CUR approximates the input matrix A, that is, ||A --- CUR||2F ≤ (1 + ε)||A --- Ak||2F, where ||.||F denotes the Frobenius norm, 0 < ε < 1 is an accuracy parameter, and Ak is the best m × n matrix of rank k constructed via the SVD of A. We present input-sparsity-time and deterministic algorithms for constructing such a CUR matrix decomposition of A where c = O(k/ε) and r = O(k/ε) and rank(U) = k. Up to constant factors, our construction is simultaneously optimal in c, r, and rank(U). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1137/140977898 | SIAM J. Comput. |
Keywords | Field | DocType |
algorithms,leverage scores,adaptive sampling,low rank matrix decomposition,input-sparsity-time,numerical linear algebra,theory,cur,svd,spectral sparsification,column subset selection | Singular value decomposition,Discrete mathematics,Combinatorics,Matrix (mathematics),Matrix decomposition,Low rank matrix decomposition,Matrix norm,Low-rank approximation,Mathematics | Conference |
Volume | Issue | ISSN |
46 | 2 | 0097-5397 |
Citations | PageRank | References |
23 | 0.87 | 32 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christos Boutsidis | 1 | 610 | 33.37 |
| David P. Woodruff | 2 | 2156 | 142.38 |