Subset selection for matrices in spectral norm
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916867114795008 |
|---|---|
| author | Kozyrev, Ivan Osinsky, Alexander |
| author_facet | Kozyrev, Ivan Osinsky, Alexander |
| contents | We address the subset selection problem for matrices, where the goal is to select a subset of $k$ columns from a "short-and-fat" matrix $X \in \mathbb{R}^{m \times n}$, such that the pseudoinverse of the sampled submatrix has as small spectral or Frobenius norm as possible. For the NP-hard spectral norm variant, we propose a new deterministic approximation algorithm. Our method refines the potential-based framework of spectral sparsification by specializing it to a single barrier function. This key modification enables direct, unweighted column selection, bypassing the intermediate weighting step required by previous approaches. It also allows for a novel adaptive update strategy for the barrier. This approach yields a new, explicit bound on the approximation quality that improves upon existing guarantees in key parameter regimes, without increasing the asymptotic computational complexity. Furthermore, numerical experiments demonstrate that the proposed method consistently outperforms its direct competitors. A complete C++ implementation is provided to support our findings and facilitate future research. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_20435 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Subset selection for matrices in spectral norm Kozyrev, Ivan Osinsky, Alexander Numerical Analysis 65F55, 90C27, 15A18, 62K05 We address the subset selection problem for matrices, where the goal is to select a subset of $k$ columns from a "short-and-fat" matrix $X \in \mathbb{R}^{m \times n}$, such that the pseudoinverse of the sampled submatrix has as small spectral or Frobenius norm as possible. For the NP-hard spectral norm variant, we propose a new deterministic approximation algorithm. Our method refines the potential-based framework of spectral sparsification by specializing it to a single barrier function. This key modification enables direct, unweighted column selection, bypassing the intermediate weighting step required by previous approaches. It also allows for a novel adaptive update strategy for the barrier. This approach yields a new, explicit bound on the approximation quality that improves upon existing guarantees in key parameter regimes, without increasing the asymptotic computational complexity. Furthermore, numerical experiments demonstrate that the proposed method consistently outperforms its direct competitors. A complete C++ implementation is provided to support our findings and facilitate future research. |
| title | Subset selection for matrices in spectral norm |
| topic | Numerical Analysis 65F55, 90C27, 15A18, 62K05 |
| url | https://arxiv.org/abs/2507.20435 |