Name
Abstract | ||
|---|---|---|
We consider low-rank reconstruction of a matrix using a subset of its columns and present asymptotically optimal algorithms for both spectral norm and Frobenius norm reconstruction. The main tools we introduce to obtain our results are (i) the use of fast approximate SVD-like decompositions for column-based matrix reconstruction, and (ii) two deterministic algorithms for selecting rows from matrices with orthonormal columns, building upon the sparse representation theorem for decompositions of the identity that appeared in [J. D. Batson, D. A. Spielman, and N. Srivastava, Twice-Ramanujan sparsifiers, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 2009, pp. 255-262]. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1137/12086755X | SIAM JOURNAL ON COMPUTING |
Keywords | Field | DocType |
randomized algorithms,numerical linear algebra,low-rank approximations | Discrete mathematics,Randomized algorithm,Combinatorics,Algebra,Matrix (mathematics),Matrix norm,Asymptotically optimal algorithm,Mathematics,Numerical linear algebra | Journal |
Volume | Issue | ISSN |
43 | SP2 | 0097-5397 |
Citations | PageRank | References |
10 | 0.60 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christos Boutsidis | 1 | 610 | 33.37 |
| Petros Drineas | 2 | 2165 | 201.55 |
| Malik Magdon-Ismail | 3 | 914 | 104.34 |