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:	Interlacing Polynomial Methods for the Generalized Column and Row Subset Selection
Language:	Chinese
Time & Venue:	2024.01.11 10:30-11:30 N702
Abstract:	In this talk we will introduce our recent work on the spectral norm version of the Generalized Column and Row Subset Selection (GCRSS) problem. Given a target matrix A, the objective of GCRSS is to select a column submatrix from the source matrix B and a row submatrix from the source matrix C, with the aim of minimizing the spectral norm of the residual matrix. By employing the interlacing polynomials method, we show that the largest root of the expected characteristic polynomial of the residual matrix serves as an upper bound on the smallest spectral norm of the residual matrix. We estimate this root for two specific GCRSS case: the Generalized Column Subset Selection (GCSS) problem and the submatrix selection problem. In the GCSS scenario, we connect the expected characteristic polynomials to the convolution of multi-affine polynomials, leading to the derivation of the first provable reconstruction bound on the spectral norm of the residual matrix for the GCSS problem. In the submatrix selection scenario, we show that any square matrix A contains a submatrix with a small spectral norm. Unlike previous studies that have produced comparable results for very special cases where the matrix is either a zero-diagonal or a positive semidefinite matrix, our results apply universally to any matrix A.