Faster Johnson-Lindenstrauss transforms via Kronecker products

The Kronecker product is an important matrix operation with a wide range of applications in 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 by an exponential factor of the standard fast Johnson-Lindenstrauss transform'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: consider a finite set of p points in a tensor product of d constituent Euclidean spaces circle times(1)(k=d) R-nk, and let N = Pi(d)(k=1) n(k). With high probability, a random KFJLT matrix of dimension m x N embeds the set of points up to multiplicative distortion (1 +/- epsilon) provided m greater than or similar to epsilon(-2) log(2d-1)(p) logN. 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.