# Hashing embeddings of optimal dimension, with applications to linear least squares

arXiv: https://arxiv.org/abs/2105.11815 · HTML: https://mlsanity.com/paper/2105.11815/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 56 references that are in the map.
- First posted on arXiv 25 May 2021.

## Builds on (most cited first, 13 of 13)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013)
- [Lower bounds for oblivious subspace embeddings](https://mlsanity.com/paper/1308.3280/) (2013)
- [Fully Understanding the Hashing Trick](https://mlsanity.com/paper/1805.08539/) (2018)
- [Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares](https://mlsanity.com/paper/1912.08294/) (2019)
- [Optimal Randomized First-Order Methods for Least-Squares Problems](https://mlsanity.com/paper/2002.09488/) (2020)
- [Understanding Sparse JL for Feature Hashing](https://mlsanity.com/paper/1903.03605/) (2019)
- [Gradient-based Sampling: An Adaptive Importance Sampling for Least-squares](https://mlsanity.com/paper/1803.00841/) (2018)
- [Convergence Analysis of Inexact Randomized Iterative Methods](https://mlsanity.com/paper/1903.07971/) (2019)
- [Faster Least Squares Optimization](https://mlsanity.com/paper/1911.02675/) (2019)
- [Error Estimation for Randomized Least-Squares Algorithms via the Bootstrap](https://mlsanity.com/paper/1803.08021/) (2018)
- [Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip](https://mlsanity.com/paper/1909.12176/) (2019)
- [Stable Sparse Subspace Embedding for Dimensionality Reduction](https://mlsanity.com/paper/2002.02844/) (2020)

## Built on by (most cited first, 4 of 4)

- [Optimal Embedding Dimension for Sparse Subspace Embeddings](https://mlsanity.com/paper/2311.10680/) (2023)
- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)
- [Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity](https://mlsanity.com/paper/2411.08773/) (2024)
- [Johnson-Lindenstrauss embeddings for noisy vectors -- taking advantage of the noise](https://mlsanity.com/paper/2209.01006/) (2022)

## Abstract (arXiv)

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 hashed -- instead 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 Ski-LLS 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.