Interlacing polynomial method for matrix approximation via generalized column and row selection

DOI10.1007/S10208-025-09719-5MaRDI QIDQ7285630zbMATH OpenFDO

Authors Jian-Feng Cai, Zhiqiang Xu, Zi-Li Xu

Publication date 22 June 2026

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10208-025-09719-5

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Inequalities involving eigenvalues and eigenvectors (15A42) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Cites work

• 10.1162/153244303322753616
• A note on column subset selection
• An elementary proof of the restricted invertibility theorem
• An Identity for the Schur Complement of a Matrix
• An improved approximation algorithm for the column subset selection problem
• Applications of stable polynomials to mixed determinants: Johnson's conjectures, unimodality, and symmetrized Fischer products
• Asymptotically optimal multi-paving
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Efficient volume sampling for row/column subset selection
• Fast algorithms for the characteristic polynomial
• Finite free convolutions of polynomials
• scientific article; zbMATH DE number 4205183 (Why is no real title available?)
• scientific article; zbMATH DE number 4144774 (Why is no real title available?)
• scientific article; zbMATH DE number 733242 (Why is no real title available?)
• scientific article; zbMATH DE number 6982912 (Why is no real title available?)
• scientific article; zbMATH DE number 7307477 (Why is no real title available?)
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Interlacing families. III: Sharper restricted invertibility estimates
• Interlacing polynomial method for the column subset selection problem
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• John's decompositions: Selecting a large part
• Matrix Analysis and Applied Linear Algebra, Second Edition
• Matrix approximation and projective clustering via volume sampling
• Mixed determinants and the Kadison-Singer problem
• Multivariate Pólya-Schur classification problems in the Weyl algebra
• Multivariate stable polynomials: theory and applications
• Near-optimal column-based matrix reconstruction
• On the zeros of convex combinations of polynomials
• Principal submatrices of normal and Hermitian matrices
• Principal submatrices, restricted invertibility, and a quantitative Gauss-Lucas theorem
• Projection matrices, generalized inverse matrices, and singular value decomposition.
• Projections and the Kadison-Singer problem
• Random sampling and approximation of MAX-CSPs
• Rank-Revealing QR Factorizations and the Singular Value Decomposition
• Relative-Error CUR Matrix Decompositions
• Restricted invertibility revisited
• Sampling from large matrices
• Some Applications of the Rank Revealing QR Factorization
• Subset selection for matrices with fixed blocks
• The Kadison-Singer problem in mathematics and engineering
• Twice-Ramanujan sparsifiers

This page was built for publication: Interlacing polynomial method for matrix approximation via generalized column and row selection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7285630)