Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:	Doctor Zili Xu,The Hong Kong University of Science and Technology
Inviter:	Professor Zhiqiang Xu
Title:	Asymptotically Sharp Bound on the Column Subset Selection Problem
Language:	Chinese
Time & Venue:	2023.06.19 15:00-16:00 N702
Abstract:	The column subset selection has gained significant attention recently due to its wide applications in machine learning. Given a matrix A and a positive integer k, 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. In this talk I will introduce our recent work on this problem. 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 A can be partitioned into r subsets such that A 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.