Optimal Embedding Dimension for Sparse Subspace Embeddings

Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong +1

A random $m\times n$ matrix $S$ is an oblivious subspace embedding (OSE) with parameters $\epsilon >0$, $\delta \in (0,1/3)$ and $d\le m\le n$, if for any $d$-dimensional subspace $W\subseteq R…