# Faster Johnson-Lindenstrauss Transforms via Kronecker Products

### Abstract

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 drastically 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.

Type
Publication
Information and Inference: A Journal of the IMA
Date
Tags
Citation
R. Jin, T. G. Kolda, R. Ward. Faster Johnson-Lindenstrauss Transforms via Kronecker Products. Information and Inference: A Journal of the IMA, 2020. https://doi.org/10.1093/imaiai/iaaa028

### Keywords

Johnson-Lindenstrauss embedding, fast Johnson-Lindenstrauss transform (FJLT), Kronecker structure, concentration inequality, restricted isometry property

### BibTeX

@article{JiKoWa20,
author = {Ruhui Jin and Tamara G. Kolda and Rachel Ward},
title = {Faster {Johnson-Lindenstrauss} Transforms via {Kronecker} Products},
journal = {Information and Inference: A Journal of the IMA},
month = {October},
year = {2020},
doi = {10.1093/imaiai/iaaa028},
eprint = {1909.04801},
}