Hashing embeddings of optimal dimension, with applications to linear least squares
The aim of this paper is two-fold: firstly, to present subspace embedding properties for s-hashing sketching matrices, with s ≥ 1, that are optimal in the projection dimension m of the sketch, namely, m = O(d), where d is the dimension of the subspace. A diverse set of results are presented that add...
| Main Authors: | , , |
|---|---|
| Format: | Internet publication |
| Language: | English |
| Published: |
2021
|
| _version_ | 1826314910904090624 |
|---|---|
| author | Cartis, C Fiala, J Shao, Z |
| author_facet | Cartis, C Fiala, J Shao, Z |
| author_sort | Cartis, C |
| collection | OXFORD |
| description | The aim of this paper is two-fold: firstly, to present subspace embedding properties for s-hashing sketching matrices, with s ≥ 1, that are optimal in the projection dimension m of the sketch, namely, m = O(d), where d is the dimension of the subspace. A diverse set of results are presented that address the case when the input matrix has sufficiently low coherence (thus removing the log2 d factor dependence in m, in the low-coherence result of Bourgain et al (2015) at the expense of a smaller coherence requirement); how this coherence changes with the number s of column nonzeros (allowing a scaling of √ s of the coherence bound), or is reduced through suitable transformations (when considering hashedinstead of subsampled- coherence reducing transformations such as randomised Hadamard). Secondly, we apply these general hashing sketching results to the special case of Linear Least Squares (LLS), and develop Ski-LLS, a generic software package for these problems, that builds upon and improves the Blendenpik solver on dense input and the (sequential) LSRN performance on sparse problems. In addition to the hashing sketching improvements, we add suitable linear algebra tools for rank-deficient and for sparse problems that lead SkiLLS to outperform not only sketching-based routines on randomly generated input, but also state of the art direct solver SPQR and iterative code HSL on certain subsets of the sparse Florida matrix collection; namely, on least squares problems that are significantly overdetermined, or moderately sparse, or difficult. |
| first_indexed | 2024-12-09T03:16:26Z |
| format | Internet publication |
| id | oxford-uuid:549c6c15-94e7-4ea9-a5be-30414fdf3e38 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:16:26Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | oxford-uuid:549c6c15-94e7-4ea9-a5be-30414fdf3e382024-10-21T10:43:17ZHashing embeddings of optimal dimension, with applications to linear least squaresInternet publicationhttp://purl.org/coar/resource_type/c_7ad9uuid:549c6c15-94e7-4ea9-a5be-30414fdf3e38EnglishSymplectic Elements2021Cartis, CFiala, JShao, ZThe aim of this paper is two-fold: firstly, to present subspace embedding properties for s-hashing sketching matrices, with s ≥ 1, that are optimal in the projection dimension m of the sketch, namely, m = O(d), where d is the dimension of the subspace. A diverse set of results are presented that address the case when the input matrix has sufficiently low coherence (thus removing the log2 d factor dependence in m, in the low-coherence result of Bourgain et al (2015) at the expense of a smaller coherence requirement); how this coherence changes with the number s of column nonzeros (allowing a scaling of √ s of the coherence bound), or is reduced through suitable transformations (when considering hashedinstead of subsampled- coherence reducing transformations such as randomised Hadamard). Secondly, we apply these general hashing sketching results to the special case of Linear Least Squares (LLS), and develop Ski-LLS, a generic software package for these problems, that builds upon and improves the Blendenpik solver on dense input and the (sequential) LSRN performance on sparse problems. In addition to the hashing sketching improvements, we add suitable linear algebra tools for rank-deficient and for sparse problems that lead SkiLLS to outperform not only sketching-based routines on randomly generated input, but also state of the art direct solver SPQR and iterative code HSL on certain subsets of the sparse Florida matrix collection; namely, on least squares problems that are significantly overdetermined, or moderately sparse, or difficult. |
| spellingShingle | Cartis, C Fiala, J Shao, Z Hashing embeddings of optimal dimension, with applications to linear least squares |
| title | Hashing embeddings of optimal dimension, with applications to linear least squares |
| title_full | Hashing embeddings of optimal dimension, with applications to linear least squares |
| title_fullStr | Hashing embeddings of optimal dimension, with applications to linear least squares |
| title_full_unstemmed | Hashing embeddings of optimal dimension, with applications to linear least squares |
| title_short | Hashing embeddings of optimal dimension, with applications to linear least squares |
| title_sort | hashing embeddings of optimal dimension with applications to linear least squares |
| work_keys_str_mv | AT cartisc hashingembeddingsofoptimaldimensionwithapplicationstolinearleastsquares AT fialaj hashingembeddingsofoptimaldimensionwithapplicationstolinearleastsquares AT shaoz hashingembeddingsofoptimaldimensionwithapplicationstolinearleastsquares |