Faster Johnson-Lindenstrauss Transforms via Kronecker Products

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$,considerafinitesetof$p$pointsinatensorproductof$d$constituentEuclideanspaces$\bigotimes_{k=d}^{1}$\mathbb{R}$^{n_k} \subset $\mathbb{R}$^{N}$\mathrm{.}Withhighprobability,arandomKFJLTmatrixofdimension$N \times m$embedsthesetofpointsuptomultiplicativedistortion$(1\pm \varepsilon)$providedby$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.