Name
Abstract | ||
|---|---|---|
We study the following problem of subset selection for matrices: given a matrix X is an element of R-nxm (m > n) and a sampling parameter k (n <= k <= m), select a subset of k columns from X such that the pseudoinverse of the sampled matrix has as small a norm as possible. In this work, we focus on the Frobenius and the spectral matrix norms. We describe several novel (deterministic and randomized) approximation algorithms for this problem with approximation bounds that are optimal up to constant factors. Additionally, we show that the combinatorial problem of finding a low-stretch spanning tree in an undirected graph corresponds to subset selection, and discuss various implications of this reduction. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/120867287 | SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS |
Keywords | DocType | Volume |
subset selection,low-stretch spanning trees,volume sampling,low-rank approximations,k-means clustering,feature selection,sparse approximation | Journal | 34 |
Issue | ISSN | Citations |
4 | 0895-4798 | 17 |
PageRank | References | Authors |
0.81 | 28 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Avron, Haim | 1 | 316 | 28.52 |
| Christos Boutsidis | 2 | 610 | 33.37 |