  The Kronecker product is an important matrix operation with a wide range of
applications in supporting fast linear transforms, including signal processing,
graph theory, quantum computing and deep learning. In this work, we introduce a
generalization of the fast Johnson-Lindenstrauss projection for embedding
vectors with Kronecker product structure, the Kronecker fast
Johnson-Lindenstrauss transform (KFJLT). The KFJLT reduces the embedding cost
to an exponential factor of the standard fast Johnson-Lindenstrauss transform
(FJLT)'s cost when applied to vectors with Kronecker structure, by avoiding
explicitly forming the full Kronecker products. We prove that this
computational gain comes with only a small price in embedding power: given $N =
\prod_{k=1}^d n_k$, consider a finite set of $p$ points in a tensor product of
$d$ constituent Euclidean spaces $\bigotimes_{k=d}^{1}\mathbb{R}^{n_k} \subset
\mathbb{R}^{N}$. With high probability, a random KFJLT matrix of dimension $N
\times m$ embeds the set of points up to multiplicative distortion $(1\pm
\varepsilon)$ provided by $m \gtrsim \varepsilon^{-2} \cdot \log^{2d - 1} (p)
\cdot \log N$. We conclude by describing a direct application of the KFJLT to
the efficient solution of large-scale Kronecker-structured least squares
problems for fitting the CP tensor decomposition.
