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

Coralia Cartis, Jan Fiala, Zhen Shao

The aim of this paper is two-fold: firstly, to present subspace embedding properties for $s$-hashing sketching matrices, with $s\ge 1$, that are optimal in the projection dimensio…