Interlacing Polynomial Method for Matrix Approximation via Generalized Column and Row Selection.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 194201088 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Interlacing Polynomial Method for Matrix Approximation via Generalized Column and Row Selection. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Cai%2C+Jian-Feng%22">Cai, Jian-Feng</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> jfcai@ust.hk</i><br /><searchLink fieldCode="AR" term="%22Xu%2C+Zhiqiang%22">Xu, Zhiqiang</searchLink><relatesTo>2,3</relatesTo> (AUTHOR)<i> xuzq@lsec.cc.ac.cn</i><br /><searchLink fieldCode="AR" term="%22Xu%2C+Zili%22">Xu, Zili</searchLink><relatesTo>4,5,6</relatesTo> (AUTHOR)<i> zlxu@math.ecnu.edu.cn</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Foundations+of+Computational+Mathematics%22">Foundations of Computational Mathematics</searchLink>. Jun2026, Vol. 26 Issue 3, p1759-1808. 50p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Subset+selection%22">Subset selection</searchLink><br /><searchLink fieldCode="DE" term="%22Matrix+norms%22">Matrix norms</searchLink><br /><searchLink fieldCode="DE" term="%22Deterministic+algorithms%22">Deterministic algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Matrix+decomposition%22">Matrix decomposition</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=194201088 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s10208-025-09719-5 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 50 StartPage: 1759 Subjects: – SubjectFull: Subset selection Type: general – SubjectFull: Matrix norms Type: general – SubjectFull: Deterministic algorithms Type: general – SubjectFull: Polynomials Type: general – SubjectFull: Matrix decomposition Type: general Titles: – TitleFull: Interlacing Polynomial Method for Matrix Approximation via Generalized Column and Row Selection. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Cai, Jian-Feng – PersonEntity: Name: NameFull: Xu, Zhiqiang – PersonEntity: Name: NameFull: Xu, Zili IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 06 Text: Jun2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 16153375 Numbering: – Type: volume Value: 26 – Type: issue Value: 3 Titles: – TitleFull: Foundations of Computational Mathematics Type: main |
| ResultId | 1 |
