Interlacing Polynomial Method for the Column Subset Selection Problem
Interlacing Polynomial Method for the Column Subset Selection Problem
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 …