1. JOHNSON--LINDENSTRAUSS EMBEDDINGS WITH KRONECKER STRUCTURE.
- Author
-
BAMBERGER, STEFAN, KRAHMER, FELIX, and WARD, RACHEL
- Subjects
- *
RESTRICTED isometry property , *HADAMARD matrices , *KRONECKER products - Abstract
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 ξ=ξ(1)⊕...⊕ξ(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)(logp)d. In the case of subsampled Hadamard matrices, this can improve the dependence of the embedding dimension on p to (logp)d while the best previously known result required (logp)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. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF