Name
Abstract | ||
|---|---|---|
We consider low-rank reconstruction of a matrix using a subset of its columns and we 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 [1]. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/FOCS.2011.21 | foundations of computer science |
Keywords | DocType | Volume |
data structure,spectral norm | Conference | abs/1103.0995 |
ISSN | Citations | PageRank |
0272-5428 | 45 | 1.96 |
References | Authors | |
14 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christos Boutsidis | 1 | 610 | 33.37 |
| Petros Drineas | 2 | 2165 | 201.55 |
| Malik Magdon-Ismail | 3 | 914 | 104.34 |