JOHNSON-LINDENSTRAUSS EMBEDDINGS WITH KRONECKER STRUCTURE

We prove the Johnson-Lindenstrauss property for matrices ΦD_ξ, where Φ has the restricted isometry property and D_ξ is a diagonal matrix containing the entries of a Kronecker product ξ = ξ⁽¹⁾ ⊗ ․․․ ⊗ ξ^(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 Φ 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.