提出新方法求解矩阵主特征对,速度超幂法10倍以上。
Split-Merge: A Difference-based Approach for Dominant Eigenvalue Problem
- 用差值公式替代传统方法,理论证明可收敛到最优解。
- 新算法在合成与真实数据上提速超10倍,性能媲美子空间迭代。
- 无需调参且不依赖矩阵存储,适合大规模稀疏场景使用。
对称半正定矩阵的主特征对计算是数值优化的基础问题。本文将范式从经典的瑞利商转向无约束差值形式,其全局最优解即为主特征对。在此框架下,证明了固定步长α∈(0,1)的梯度下降几乎必然以局部线性速率收敛至全局最优。该分析重新解释经典幂法为α=1/2的保守特例,并严格确立其渐近次优性。为提升一阶方法性能,提出基于极大化-极小化原则的Split-Merge算法。通过分解矩阵并引入辅助向量融合因子,实现无需矩阵存储、无需参数调节的迭代,捕捉更精确曲率信息。理论证明Split-Merge几乎必然收敛至全局最小值,并展现出抑制目标特征空间的谱剥皮机制,可能超越幂法的静态线性收敛率。在合成与真实数据集上的数值实验表明,该方法具备可扩展效率,在多个测试中实现超过10倍于幂法的速度提升,性能接近子空间迭代。
原文摘要 · Abstract (English)
The computation of the dominant eigenpair for symmetric positive semidefinite matrices is fundamental in numerical optimization. This work shifts the paradigm from the classical Rayleigh quotient to an unconstrained difference formulation, whose global optimum recovers the dominant eigenpair. Within this framework, we prove that gradient descent with a constant step-size $α\in (0, 1)$ converges almost surely to the global optimum at a local linear rate. This analysis thereby reinterprets the classical power method as the conservative special case $α=1/2$ and rigorously establishes its asymptotic sub-optimality. To advance this first-order scheme, we propose the Split-Merge algorithm based on the majorization-minimization principle. After splitting the matrix, we introduce auxiliary vectors to effectively merge the decomposition factors, resulting in a matrix-free and parameter-free iteration that captures tighter curvature information. We establish that Split-Merge converges almost surely to a global minimizer, and show that the iteration exhibits a spectral peeling mechanism that suppresses the targeted eigenspace, potentially surpassing the static linear rate of power iterations. Numerical evaluations across synthetic and real-world datasets confirm that our method has scalable efficiency, achieving speed-ups exceeding $10\times$ over the power method, with performance comparable to subspace iterations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。