2021/06/24 by Stefan Bamberger, Bamberger, Stefan, Felix Krahmer +3 · 1 citation
Computer Science · Engineering · Mathematics · #15A69 #68Q87 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2106.13349
openalex publication_date 2021/06/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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) (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.