Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings

Yi Li, Mingmou Liu

An oblivious subspace embedding (OSE), characterized by parameters $m,n,d,\epsilon ,\delta$, is a random matrix $\Pi \in {\mathbb{R}}^{m\times n}$ such that for any $d$-dimensional subspace $T\subse…