Johnson–Lindenstrauss Embeddings with Kronecker Structure

DOI10.1137/21M1432491OpenAlexW3173508658MaRDI QIDQ5885797

Felix Krahmer, Rachel Ward, Stefan Bamberger

Publication date: 30 March 2023

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

Kronecker productrestricted isometry propertyJohnson-Lindenstrauss embeddingshigher-order chaos

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Random matrices (algebraic aspects) (15B52) Multilinear algebra, tensor calculus (15A69) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Related Items

On fast Johnson-Lindenstrauss embeddings of compact submanifolds of \(\mathbb{R}^N\) with boundary

Cites Work

• Unnamed Item
• Unnamed Item
• A mathematical introduction to compressive sensing
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• A variant of the Johnson-Lindenstrauss lemma for circulant matrices
• An algorithmic theory of learning: robust concepts and random projection
• Estimates of moments and tails of Gaussian chaoses
• Decoupling inequalities for polynomial chaos
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• On decoupling, series expansions, and tail behavior of chaos processes
• Problems and results in extremal combinatorics. I.
• The geometry of graphs and some of its algorithmic applications
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• The Hanson-Wright inequality for random tensors
• Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Computational Advertising: Techniques for Targeting Relevant Ads
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Extensions of Lipschitz mappings into a Hilbert space
• Improved bounds for the RIP of Subsampled Circulant matrices
• The Restricted Isometry Property of Subsampled Fourier Matrices
• A Practical Randomized CP Tensor Decomposition
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Tensor-Structured Sketching for Constrained Least Squares
• Faster Johnson–Lindenstrauss transforms via Kronecker products
• Oblivious Sketching of High-Degree Polynomial Kernels
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares