Faster Johnson-Lindenstrauss transforms via Kronecker products

DOI10.1093/IMAIAI/IAAA028MaRDI QIDQ5033281zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

concentration inequalityfast Johnson-Lindenstrauss transform (FJLT)Johnson-Lindenstrauss embeddingKronecker structurerestricted isometry property

Mathematics Subject Classification ID

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

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.

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

Cited in

(24)

• Filament plots for data visualization
• The Hanson-Wright inequality for random tensors
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• A sparse Johnson-Lindenstrauss transform
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• A Kronecker Product Representation of the Fast Gauss Transform
• Practical leverage-based sampling for low-rank tensor decomposition
• Norm and trace estimation with random rank-one vectors
• The Johnson-Lindenstrauss Transform: An Empirical Study
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Randomized numerical linear algebra: Foundations and algorithms
• Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery
• Randomized tensor wheel 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
• Tracking tensor ring decompositions of streaming tensors
• Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
• Subspace method of moments for \textit{ab initio} 3-D single particle cryo-EM reconstruction
• Fast algorithms for least squares problems with Kronecker lower subsets
• Small ball probabilities for simple random tensors
• Tensor recovery from quantized measurements based on modewise operators
• Randomized sketched TT-GMRES for linear systems with tensor structure
• Efficient randomized algorithms for fixed precision problem of approximate Tucker decomposition
• Fast and low-memory compressive sensing algorithms for low Tucker-rank tensor approximation from streamed measurements

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)