Subset selection for matrices by column exchange
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911596724355072 |
|---|---|
| author | Osinsky, Alexander Kozyrev, Ivan |
| author_facet | Osinsky, Alexander Kozyrev, Ivan |
| contents | The paper considers the problem of finding a submatrix $X_{\mathcal{S}} \in \mathbb{R}^{m \times k}$ in a matrix $X \in \mathbb{R}^{m \times n}$, such that the spectral or Frobenius norm of $X_{\mathcal{S}}^† X$ is limited, which guarantees it provides a good representation of the whole matrix. Such bounds can be reached by applying greedy algorithms, maximizing the submatrix volume. We suggest a modification of a greedy volume maximization, which performs column exchanges asymptotically faster for $n \gg m$ than the known alternatives, while guaranteeing the same bounds on $X_{\mathcal{S}}^† X$. In addition, we prove a new upper bound on the number of required exchanges, which is applicable to the new algorithm as well as to other greedy volume maximization algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_14418 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Subset selection for matrices by column exchange Osinsky, Alexander Kozyrev, Ivan Numerical Analysis 65F55, 90C27, 15A18, 62K05 The paper considers the problem of finding a submatrix $X_{\mathcal{S}} \in \mathbb{R}^{m \times k}$ in a matrix $X \in \mathbb{R}^{m \times n}$, such that the spectral or Frobenius norm of $X_{\mathcal{S}}^† X$ is limited, which guarantees it provides a good representation of the whole matrix. Such bounds can be reached by applying greedy algorithms, maximizing the submatrix volume. We suggest a modification of a greedy volume maximization, which performs column exchanges asymptotically faster for $n \gg m$ than the known alternatives, while guaranteeing the same bounds on $X_{\mathcal{S}}^† X$. In addition, we prove a new upper bound on the number of required exchanges, which is applicable to the new algorithm as well as to other greedy volume maximization algorithms. |
| title | Subset selection for matrices by column exchange |
| topic | Numerical Analysis 65F55, 90C27, 15A18, 62K05 |
| url | https://arxiv.org/abs/2604.14418 |