Guarantees for the Kronecker Fast Johnson-Lindenstrauss Transform Using a Coherence and Sampling Argument

Abstract

In the recent paper [Jin, Kolda & Ward, arXiv:1909.04801], it is proved that the Kronecker fast Johnson-Lindenstrauss transform (KFJLT) is, in fact, a Johnson-Lindenstrauss transform, which had previously only been conjectured. In this paper, we provide an alternative proof of this, for when the KFJLT is applied to Kronecker vectors, using a coherence and sampling argument. Our proof yields a different bound on the embedding dimension, which can be combined with the bound in the paper by Jin et al. to get a better bound overall. As a stepping stone to proving our result, we also show that the KFJLT is a subspace embedding for matrices with columns that have Kronecker product structure. Lastly, we compare the KFJLT to four other sketch techniques in numerical experiments on both synthetic and real-world data.

arXiv commentAccepted to Linear Algebra and its Applications

References in corpus (6)

• Sketching as a Tool for Numerical Linear Algebra
• A Practical Randomized CP Tensor Decomposition
• Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound
• Optimal Sketching for Kronecker Product Regression and Low Rank Approximation
• Tensor Random Projection for Low Memory Dimension Reduction
• Tensorized Random Projections

Cited by in corpus (5)

• Faster Johnson-Lindenstrauss Transforms via Kronecker Products
• Fast Randomized Matrix and Tensor Interpolative Decomposition Using CountSketch
• Structured random sketching for PDE inverse problems
• Rademacher Random Projections with Tensor Networks
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares