Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity

Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong

An oblivious subspace embedding is a random $m\times n$ matrix $\Pi$ such that, for any $d$-dimensional subspace, with high probability $\Pi$ preserves the norms of all vectors in that…