  An $\ell_p$ oblivious subspace embedding is a distribution over $r \times n$
matrices $\Pi$ such that for any fixed $n \times d$ matrix $A$,
$$\Pr_{\Pi}[\textrm{for all }x, \ \|Ax\|_p \leq \|\Pi Ax\|_p \leq \kappa
\|Ax\|_p] \geq 9/10,$$ where $r$ is the dimension of the embedding, $\kappa$ is
the distortion of the embedding, and for an $n$-dimensional vector $y$,
$\|y\|_p$ is the $\ell_p$-norm. Another important property is the sparsity of
$\Pi$, that is, the maximum number of non-zero entries per column, as this
determines the running time of computing $\Pi \cdot A$. While for $p = 2$ there
are nearly optimal tradeoffs in terms of the dimension, distortion, and
sparisty, for the important case of $1 \leq p < 2$, much less was known. In
this paper we obtain nearly optimal tradeoffs for $\ell_p$ oblivious subspace
embeddings for every $1 \leq p < 2$.
  We show for every $1 \leq p < 2$, any oblivious subspace embedding with
dimension $r$ has distortion $\kappa = \Omega
\left(\frac{1}{\left(\frac{1}{d}\right)^{1 / p} \cdot \log^{2 / p}r +
\left(\frac{r}{n}\right)^{1 / p - 1 / 2}}\right).$ When $r = \mathrm{poly}(d)$
in applications, this gives a $\kappa = \Omega(d^{1/p}\log^{-2/p} d)$ lower
bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC,
2011) for $p = 1$ and the oblivious subspace embedding of Meng and Mahoney
(STOC, 2013) for $1 < p < 2$ are optimal up to $\mathrm{poly}(\log(d))$
factors. We also give sparse oblivious subspace embeddings for every $1 \leq p
< 2$ which are optimal in dimension and distortion, up to $\mathrm{poly}(\log
d)$ factors.
  Oblivious subspace embeddings are crucial for distributed and streaming
environments, as well as entrywise $\ell_p$ low rank approximation. Our results
give improved algorithms for these applications.
