  We prove the Johnson-Lindenstrauss property for matrices $\Phi D_\xi$ where
$\Phi$ has the restricted isometry property and $D_\xi$ is a diagonal matrix
containing the entries of a Kronecker product $\xi = \xi^{(1)} \otimes \dots
\otimes \xi^{(d)}$ of $d$ independent Rademacher vectors. Such embeddings have
been proposed in recent works for a number of applications concerning
compression of tensor structured data, including the oblivious sketching
procedure by Ahle et al. for approximate tensor computations. For preserving
the norms of $p$ points simultaneously, our result requires $\Phi$ to have the
restricted isometry property for sparsity $C(d) (\log p)^d$. In the case of
subsampled Hadamard matrices, this can improve the dependence of the embedding
dimension on $p$ to $(\log p)^d$ while the best previously known result
required $(\log p)^{d + 1}$. That is, for the case of $d=2$ at the core of the
oblivious sketching procedure by Ahle et al., the scaling improves from cubic
to quadratic. We provide a counterexample to prove that the scaling established
in our result is optimal under mild assumptions.
