子采样版Davis-Kahan定理问世，大规模矩阵谱分析终于能跑得动了！
A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation
📖 AI 总结
本文针对大规模对称矩阵特征空间估计中计算成本过高的问题，提出了一种基于独立伯努利采样的子采样方案，并给出了相应的Davis-Kahan型误差界。Davis-Kahan定理是谱分析中的基础工具，用于量化对称矩阵与其扰动之间特征空间的距离，但当矩阵维数很大时，计算前导特征向量的代价极为高昂，限制了谱方法在现代大规模场景中的实际应用。作者证明，子采样矩阵的前导左奇异向量能够可靠逼近低秩对称矩阵的目标子空间，其核心结果是一个显式依赖于采样概率的子采样Davis-Kahan界。该界揭示了一个关键权衡：计算成本随采样概率线性增长，而统计误差则按采样概率的平方根反比缩放。这一结果将经典Davis-Kahan定理推广至子采样情形，为大规模对称矩阵的可扩展谱分析提供了理论支撑。
🔑 关键词速览
| Davis-Kahan 定理 | 谱分析中的基本定理，用于量化对称矩阵扰动前后特征子空间之间的距离。 |
| 子采样 Davis-Kahan 界 | 本文提出的误差上界，显式依赖于采样概率，将经典 Davis-Kahan 定理推广到子采样场景。 |
| 独立 Bernoulli 采样 | 一种随机采样方案，每个矩阵元素以独立同分布的概率被保留，用于降低计算复杂度。 |
| 前导左奇异向量 | 矩阵奇异值分解中对应最大奇异值的左奇异向量，用于近似矩阵的主要子空间。 |
| 低秩对称矩阵 | 秩远小于其维数的对称矩阵，常见于大规模数据分析中，其谱结构具有低维特性。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅