Optimal Embedding Dimension for Sparse Subspace Embeddings
Shabarish Chenakkod Michał Dereziński Xiaoyu Dong Mark Rudelson
A random $m\times n$ matrix $S$ is an oblivious subspace embedding (OSE) with
parameters $\epsilon>0$, $\delta\in(0,1/3)$ and $d\leq m\leq n$, if for any
$d$-dimensional subspace $W\subseteq R^n$,
  $P\big(\,\forall_{x\in W}\ (1+\epsilon)^{-1}\|x\|\leq\|Sx\|\leq
(1+\epsilon)\|x\|\,\big)\geq 1-\delta.$
  It is known that the embedding dimension of an OSE must satisfy $m\geq d$,
and for any $\theta > 0$, a Gaussian embedding matrix with $m\geq (1+\theta) d$
is an OSE with $\epsilon = O_\theta(1)$. However, such optimal embedding
dimension is not known for other embeddings. Of particular interest are sparse
OSEs, having $s\ll m$ non-zeros per column, with applications to problems such
as least squares regression and low-rank approximation.
  We show that, given any $\theta > 0$, an $m\times n$ random matrix $S$ with
$m\geq (1+\theta)d$ consisting of randomly sparsified $\pm1/\sqrt s$ entries
and having $s= O(\log^4(d))$ non-zeros per column, is an oblivious subspace
embedding with $\epsilon = O_{\theta}(1)$. Our result addresses the main open
question posed by Nelson and Nguyen (FOCS 2013), who conjectured that sparse
OSEs can achieve $m=O(d)$ embedding dimension, and it improves on
$m=O(d\log(d))$ shown by Cohen (SODA 2016). We use this to construct the first
oblivious subspace embedding with $O(d)$ embedding dimension that can be
applied faster than current matrix multiplication time, and to obtain an
optimal single-pass algorithm for least squares regression. We further extend
our results to construct even sparser non-oblivious embeddings, leading to the
first subspace embedding with low distortion $\epsilon=o(1)$ and optimal
embedding dimension $m=O(d/\epsilon^2)$ that can be applied in current matrix
multiplication time.