用快速压缩加速幂法，大幅提升大秩低秩近似效率
Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
- 引入快速压缩技术优化幂法迭代过程
- 在基准测试中实现强数值性能，收敛更快
- 适合需要高效低秩分解的大规模数据场景
幂法是通过低秩矩阵近似提取数据主成分的核心方法。然而当目标秩较大时，伴随的矩阵乘法开销成为主要瓶颈。本文提出一种基于快速压缩的算法与理论框架，加速幂法运算。该框架可导出简单且可证明高效的奇异值分解、低秩分解和Nyström近似方法，在基准问题上表现出优异的数值性能。分析中的关键创新在于使用正则化谱逼近——这一快速压缩方法的性质，比传统论证更具普适性，能更灵活地推广幂法的保证。
原文摘要 · Abstract (English)
The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。