Asymptotically Sharp Upper Bound for the Column Subset Selection Problem

03/14/2023

∙

by   Jian-Feng Cai, et al.

∙

0

∙

share

This paper investigates the spectral norm version of the column subset selection problem. Given a matrix 𝐀∈ℝ^n× d and a positive integer k≤rank(𝐀), the objective is to select exactly k columns of 𝐀 that minimize the spectral norm of the residual matrix after projecting 𝐀 onto the space spanned by the selected columns. We use the method of interlacing polynomials introduced by Marcus-Spielman-Srivastava to derive an asymptotically sharp upper bound on the minimal approximation error, and propose a deterministic polynomial-time algorithm that achieves this error bound (up to a computational error). Furthermore, we extend our result to a column partition problem in which the columns of 𝐀 can be partitioned into r≥ 2 subsets such that 𝐀 can be well approximated by subsets from various groups. We show that the machinery of interlacing polynomials also works in this context, and establish a connection between the relevant expected characteristic polynomials and the r-characteristic polynomials introduced by Ravichandran and Leake. As a consequence, we prove that the columns of a rank-d matrix 𝐀∈ℝ^n× d can be partitioned into r subsets S_1,… S_r, such that the column space of 𝐀 can be well approximated by the span of the columns in the complement of S_i for each 1≤ i≤ r.