  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{rank}(\mathbf{A})$, the objective is to select
exactly $k$ columns of $\mathbf{A}$ that minimize the spectral norm of the
residual matrix after projecting $\mathbf{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
$\mathbf{A}\in\mathbb{R}^{n\times d}$ obeys a spectral power-law decay. The
relevant expected characteristic polynomials can be written as an extension 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.
