View in EDS

Interlacing Polynomial Method for Matrix Approximation via Generalized Column and Row Selection.

Saved in:
Bibliographic Details
Title: Interlacing Polynomial Method for Matrix Approximation via Generalized Column and Row Selection.
Authors: Cai, Jian-Feng1 (AUTHOR) jfcai@ust.hk, Xu, Zhiqiang2,3 (AUTHOR) xuzq@lsec.cc.ac.cn, Xu, Zili4,5,6 (AUTHOR) zlxu@math.ecnu.edu.cn
Source: Foundations of Computational Mathematics. Jun2026, Vol. 26 Issue 3, p1759-1808. 50p.
Subjects: Subset selection, Matrix norms, Deterministic algorithms, Polynomials, Matrix decomposition
Abstract: This paper delves into the spectral norm aspect of the Generalized Column and Row Subset Selection (GCRSS) problem. Given a target matrix A ∈ R n × d , the objective of GCRSS is to select a column submatrix B : , S ∈ R n × k from the source matrix B ∈ R n × d B and a row submatrix C R , : ∈ R r × d from the source matrix C ∈ R n C × d , such that the residual matrix (I n - B : , S B : , S †) A (I d - C R , : † C R , :) has a small spectral norm. By employing the method of interlacing polynomials, we show that the smallest possible spectral norm of a residual matrix can be bounded by the largest root of a related expected characteristic polynomial. A deterministic polynomial time algorithm is provided for the spectral norm case of the GCRSS problem. We next apply our results to two specific GCRSS scenarios, one where r = 0 , simplifying the problem to the Generalized Column Subset Selection (GCSS) problem, and the other where B = C = I d , reducing the problem to 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 a residual matrix. In the submatrix selection scenario, we show that for any sufficiently small ε > 0 and any square matrix A ∈ R d × d , there exist two subsets S ⊂ [ d ] and R ⊂ [ d ] of sizes O (d · ε 2) such that ‖ A S , R ‖ 2 ≤ ε · ‖ A ‖ 2 . 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 square matrix A. [ABSTRACT FROM AUTHOR]
Copyright of Foundations of Computational Mathematics is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:This paper delves into the spectral norm aspect of the Generalized Column and Row Subset Selection (GCRSS) problem. Given a target matrix A ∈ R n × d , the objective of GCRSS is to select a column submatrix B : , S ∈ R n × k from the source matrix B ∈ R n × d B and a row submatrix C R , : ∈ R r × d from the source matrix C ∈ R n C × d , such that the residual matrix (I n - B : , S B : , S †) A (I d - C R , : † C R , :) has a small spectral norm. By employing the method of interlacing polynomials, we show that the smallest possible spectral norm of a residual matrix can be bounded by the largest root of a related expected characteristic polynomial. A deterministic polynomial time algorithm is provided for the spectral norm case of the GCRSS problem. We next apply our results to two specific GCRSS scenarios, one where r = 0 , simplifying the problem to the Generalized Column Subset Selection (GCSS) problem, and the other where B = C = I d , reducing the problem to 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 a residual matrix. In the submatrix selection scenario, we show that for any sufficiently small ε > 0 and any square matrix A ∈ R d × d , there exist two subsets S ⊂ [ d ] and R ⊂ [ d ] of sizes O (d · ε 2) such that ‖ A S , R ‖ 2 ≤ ε · ‖ A ‖ 2 . 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 square matrix A. [ABSTRACT FROM AUTHOR]
ISSN:16153375
DOI:10.1007/s10208-025-09719-5