Johnson-Lindenstrauss Embeddings with Kronecker Structure

Understand

We prove the Johnson-Lindenstrauss property for matrices $\Phi D_\xi$ where $\Phi$ has the restricted isometry property and $D_\xi$ is a diagonal matrix containing the entries of a Kronecker product $\xi = \xi^{(1)} \otimes \dots \otimes \xi^{(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 $\Phi$ to have the restricted isometry property for sparsity $C(d) (\log p)^d$.