SCM论文 | 矩阵子集选择问题

从一个矩阵的列向量中选出一部分，使所得列子矩阵具有良好性质，是数学和科学计算中的基本问题之一。1987 年，Bourgain 和 Tzafriri 建立了著名的限制可逆性原理[1]，揭示了从矩阵中选取具有良好可逆性的大子矩阵的可能性。此后，矩阵选择问题逐渐成为 Banach 空间几何、数值线性代数和矩阵分析中的重要研究方向，并与特征选择、实验设计、压缩感知及相位恢复等问题产生了密切联系。

根据对子矩阵性质的不同要求，矩阵选择问题具有多种形式。本文关注的是如何选出一个最小奇异值尽可能大的子矩阵。具体而言，我们研究以下问题:

问题: 给定矩阵 ，用表示由指标集合对应的列组成的子矩阵。对于给定的整数，如何选取一个满足的集合，使尽可能大？这里，表示的第大奇异值。

根据选列数量 与矩阵行数的关系，这一问题可以分为、和三种情形。其中，当且满行秩时，问题就变为：如何从一个生成整个空间的向量组中，选出一组稳定的基？对于不同的选列数量，已有研究采用了贪婪算法、矩阵分析等多种方法，建立了相应的最小奇异值下界。

近年来，交错多项式族方法为这类问题提供了新的研究途径。Marcus、Spielman 和 Srivastava 在解决二分图情形的 Bilu-Linial 猜想[5]以及 Kadison-Singer 问题[6]的过程中，提出并发展了这一方法。随后，他们将这一方法用于限制可逆性问题，得到了更精细的定量估计[7]。

在此基础上，本文作者及其合作者将交错多项式族方法用于列子集选择、广义行列选择以及高秩半正定矩阵的谱估计等问题[8,2,3,9]， 逐步探索这一方法在数据科学中的系统应用。本文延续了这一研究思路，并统一研究了 、和 三种情形。

近期我们在Science China Mathematics发表论文，利用交错多项式族方法，在统一框架下研究不同选列数量对应的矩阵选择问题，给出了所选子矩阵最小奇异值的显式下界。这些结果涵盖 、和 三种情形，并在多个参数范围内改进了已有估计。

特别地，对于稳定基提取所对应的 情形，新结果在相应参数范围内严格改进了经典的 Hong-Pan 下界[4]。从框架理论的角度看，这意味着：从同一个 Parseval 紧框架中提取基时，我们能够给出比经典估计更强的稳定性保证。

上述改进的关键，在于对期望特征多项式相关根的估计。虽然不同选列数量对应的多项式具有不同的形式，但交错性质为它们提供了共同的分析途径：通过估计相应多项式的根，可以保证存在满足谱界的子矩阵。不同于交错多项式方法中常用的障碍函数方法，本文直接从根与系数的关系入手，将多项式的系数与根的倒数之和联系起来，进而建立约束最小根的二次不等式，得到所需的显式下界。这一分析展示了如何利用多项式的系数信息改进根估计，也为交错多项式方法的应用提供了新的思路。

这一证明过程也是一个多项式时间选择列子集的过程。因此，本文不仅给出了更强的存在性结论，也为实际选取具有良好谱性质的列子集提供了算法依据。

【参考文献】

[1] Bourgain J, Tzafriri L. Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis. Israel J Math, 1987, 57: 137--224.

[2] Cai J F, Xu Z Q, Xu Z L. Interlacing polynomial method for the column subset selection problem. Int Math Res Not IMRN, 2024, 2024: 7798--7819.

[3] Cai J F, Xu Z Q, Xu Z L. Interlacing polynomial method for matrix approximation via generalized column and row selection. Found Comput Math, 2026, 26: 1759--1808.

[4] Hong Y P, Pan C T. Rank-revealing QR factorizations and the singular value decomposition. Math Comp, 1992, 58: 213--232.

[5] Marcus A W, Spielman D A, Srivastava N. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann of Math (2), 2015, 182: 307--325.

[6] Marcus A W, Spielman D A, Srivastava N. Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem. Ann of Math (2), 2015, 182: 327--350.

[7] Marcus A W, Spielman D A, Srivastava N. Interlacing families III: Sharper restricted invertibility estimates. Israel J Math, 2022, 247: 519--546.

[8] Xie J X, Xu Z Q. Subset selection for matrices with fixed blocks. Israel J Math, 2021, 245: 1--26.

[9] Xu Z Q, Xu Z L, Zhu Z H. Improved bounds in Weaver's conjecture for high rank positive semidefinite matrices. J Funct Anal, 2023, 285: 109978.

作者简介

许志强，中国科学院数学与系统科学研究院研究员，主要研究方向包括计算调和分析、数据科学、压缩感知和机器学习。