Interlacing Polynomial Method for the Column Subset Selection Problem

This paper investigates the spectral norm version of the column subset selection problem. Given a matrix A ∈ R^n×d and a positive integer k ≤ rank(A), the objective is to select exactly k columns of A that minimize the spectral norm of the residual matrix after projecting 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 A ∈ R^n×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.