Interlacing Polynomial Method for the Column Subset Selection Problem

Jian-Feng Cai, Zhiqiang Xu, Zili Xu

This paper investigates the spectral norm version of the column subset selection problem. Given a matrix $\mathbf{A}\in {\mathbb{R}}^{n\times d}$ and a positive integer $k\leq\text{ra…