pylspack: Parallel algorithms and data structures for sketching, column subset selection, regression and leverage scores
arXiv:2203.02798 · doi:10.1145/3555370
Abstract
We present parallel algorithms and data structures for three fundamental operations in Numerical Linear Algebra: (i) Gaussian and CountSketch random projections and their combination, (ii) computation of the Gram matrix and (iii) computation of the squared row norms of the product of two matrices, with a special focus on "tall-and-skinny" matrices, which arise in many applications. We provide a detailed analysis of the ubiquitous CountSketch transform and its combination with Gaussian random projections, accounting for memory requirements, computational complexity and workload balancing. We also demonstrate how these results can be applied to column subset selection, least squares regression and leverage scores computation. These tools have been implemented in pylspack, a publicly available Python package (https://github.com/IBM/pylspack) whose core is written in C++ and parallelized with OpenMP, and which is compatible with standard matrix data structures of SciPy and NumPy. Extensive numerical experiments indicate that the proposed algorithms scale well and significantly outperform existing libraries for tall-and-skinny matrices.
To appear in ACM TOMS
References in corpus (6)
- Sketching as a Tool for Numerical Linear Algebra
- Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
- Efficiently Parallelizable Strassen-Based Multiplication of a Matrix by its Transpose
- Hashing embeddings of optimal dimension, with applications to linear least squares
- Estimating leverage scores via rank revealing methods and randomization
- A quantum-inspired algorithm for approximating statistical leverage scores