"Johnson-Lindenstrauss Embeddings with Kronecker Structure"Bamberger, StefanWe 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. 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$. 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}$. We provide a counterexample to prove that the scaling established in our result is optimal under mild assumptions. |
| http://univie.ac.at/projektservice-mathematik/e/talks/Bamberger_2021-06_JL_Kronecker.pdf |
« back