用随机数值线性代数加速大规模最小二乘求解，快50倍。
Sketch 'n Solve: An Efficient Python Package for Large-Scale Least Squares Using Randomized Numerical Linear Algebra
- 采用随机化技术降低计算复杂度，支持稠密与稀疏矩阵。
- 相比传统LSQR方法，最快提升50倍速度，精度仍高。
- 适合机器学习、信号处理等需要快速求解的场景。
我们提出Sketch 'n Solve，一个开源Python工具包，利用随机数值线性代数（RandNLA）高效求解大规模最小二乘问题。尽管这类算法在理论上表现优异，但实际应用受限于缺乏稳定易用的实现。本工具包基于NumPy和SciPy构建，提供稠密与稀疏的随机化压缩算子，具有简洁的API。通过大量基准测试，结果显示其相比传统LSQR方法最快可提升50倍性能，即使在病态矩阵下仍保持高精度。该工具包在机器学习优化、信号处理及科学计算等领域具有显著应用潜力。
原文摘要 · Abstract (English)
We present Sketch 'n Solve, an open-source Python package that implements efficient randomized numerical linear algebra (RandNLA) techniques for solving large-scale least squares problems. While sketch-and-solve algorithms have demonstrated theoretical promise, their practical adoption has been limited by the lack of robust, user-friendly implementations. Our package addresses this gap by providing an optimized implementation built on NumPy and SciPy, featuring both dense and sparse sketching operators with a clean API. Through extensive benchmarking, we demonstrate that our implementation achieves up to 50x speedup over traditional LSQR while maintaining high accuracy, even for ill-conditioned matrices. The package shows particular promise for applications in machine learning optimization, signal processing, and scientific computing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。