Faster Johnson-Lindenstrauss transforms via Kronecker products

DOI10.1093/IMAIAI/IAAA028zbMATH Open1483.94017arXiv1909.04801OpenAlexW3094211687MaRDI QIDQ5033281FDOQ5033281

Authors: Ruhui Jin, Rachel Ward, Tamara G. Kolda 

Publication date: 22 February 2022

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: The Kronecker product is an important matrix operation with a wide range of applications in supporting fast linear transforms, including signal processing, graph theory, quantum computing and deep learning. In this work, we introduce a generalization of the fast Johnson-Lindenstrauss projection for embedding vectors with Kronecker product structure, the Kronecker fast Johnson-Lindenstrauss transform (KFJLT). The KFJLT reduces the embedding cost to an exponential factor of the standard fast Johnson-Lindenstrauss transform (FJLT)'s cost when applied to vectors with Kronecker structure, by avoiding explicitly forming the full Kronecker products. We prove that this computational gain comes with only a small price in embedding power: given $N=pro{d}_{k=1}^d{n}_k$, consider a finite set of $p$ points in a tensor product of $d$ constituent Euclidean spaces $$. With high probability, a random KFJLT matrix of dimension $Nimesm$ embeds the set of points up to multiplicative distortion $(1pmvarepsilon)$ provided by $mgtrsimvarepsilo{n}^{-2}cdotlo{g}^{2d-1}(p)cdotlogN$. We conclude by describing a direct application of the KFJLT to the efficient solution of large-scale Kronecker-structured least squares problems for fitting the CP tensor decomposition.

Full work available at URL: https://arxiv.org/abs/1909.04801

Recommendations

• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets

zbMATH Keywords

concentration inequalityrestricted isometry propertyJohnson-Lindenstrauss embeddingKronecker structurefast Johnson-Lindenstrauss transform (FJLT)

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (probabilistic aspects) (60B20) Numerical linear algebra (65F99)

Cited In (17)

• Randomized numerical linear algebra: Foundations and algorithms
• A Kronecker Product Representation of the Fast Gauss Transform
• The Hanson-Wright inequality for random tensors
• A sparse Johnson-Lindenstrauss transform
• Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• Filament plots for data visualization
• Practical leverage-based sampling for low-rank tensor decomposition
• A sequential multilinear Nyström algorithm for streaming low-rank approximation of tensors in Tucker format
• A multilinear Nyström algorithm for low-rank approximation of tensors in Tucker format
• Norm and trace estimation with random rank-one vectors
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Tracking tensor ring decompositions of streaming tensors
• Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
• The Johnson-Lindenstrauss Transform: An Empirical Study
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• Randomized tensor wheel decomposition

This page was built for publication: Faster Johnson-Lindenstrauss transforms via Kronecker products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5033281)