We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Interlacing Polynomial Method for the Column Subset Selection Problem.
- Authors
Cai, Jian-Feng; Xu, Zhiqiang; Xu, Zili
- Abstract
This paper investigates the spectral norm version of the column subset selection problem. Given a matrix |$\textbf{A}\in \mathbb{R}^{n\times d}$| and a positive integer |$k\leq \textrm{rank}(\textbf{A})$| , the objective is to select exactly |$k$| columns of |$\textbf{A}$| that minimize the spectral norm of the residual matrix after projecting |$\textbf{A}$| onto the space spanned by the selected columns. We use the method of interlacing polynomials introduced by Marcus–Spielman–Srivastava to derive a new upper bound on the minimal approximation error. This new bound is asymptotically sharp when the matrix |$\textbf{A}\in \mathbb{R}^{n\times d}$| obeys a spectral power-law decay. The relevant expected characteristic polynomial is a variation of the expected polynomial for the restricted invertibility problem, incorporating two extra variable substitution operators. Finally, we propose a deterministic polynomial-time algorithm that achieves this error bound up to a computational error.
- Subjects
POLYNOMIAL time algorithms; POLYNOMIALS; DETERMINISTIC algorithms; MATRIX norms; APPROXIMATION error; SUBSET selection
- Publication
IMRN: International Mathematics Research Notices, 2024, Vol 2024, Issue 9, p7798
- ISSN
1073-7928
- Publication type
Article
- DOI
10.1093/imrn/rnae001