Sketch 'n Solve: An Efficient Python Package for Large-Scale Least Squares Using Randomized Numerical Linear Algebra
This provides a user-friendly tool for researchers and practitioners in machine learning, signal processing, and scientific computing, though it is incremental as it focuses on implementation rather than new algorithmic breakthroughs.
The authors tackled the lack of practical implementations for sketch-and-solve algorithms in large-scale least squares problems by developing Sketch 'n Solve, an open-source Python package that achieves up to 50x speedup over traditional LSQR while maintaining high accuracy.
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.