Tensorized Random Projections

We introduce a novel random projection technique for efficiently reducing the dimension of very high-dimensional tensors. Building upon classical results on Gaussian random projections and Johnson-Lindenstrauss transforms~(JLT), we propose two tensorized random projection maps relying on the tensor train~(TT) and CP decomposition format, respectively. The two maps offer very low memory requirements and can be applied efficiently when the inputs are low rank tensors given in the CP or TT format. Our theoretical analysis shows that the dense Gaussian matrix in JLT can be replaced by a low-rank tensor implicitly represented in compressed form with random factors, while still approximately preserving the Euclidean distance of the projected inputs. In addition, our results reveal that the TT format is substantially superior to CP in terms of the size of the random projection needed to achieve the same distortion ratio. Experiments on synthetic data validate our theoretical analysis and demonstrate the superiority of the TT decomposition.

• Publication year

  2020

• Venue

  International Conference on Artificial Intelligence and Statistics

• Publication date

  2020-03-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 2003.05101
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Tensor Random Projection for Low Memory Dimension Reduction

  2021influential reference
• Multi-dimensional Tensor Sketch

  2019cited by this paper
• Faster Johnson-Lindenstrauss Transforms via Kronecker Products

  2019influential reference
• Higher-Order Count Sketch: Dimensionality Reduction that Retains Efficient Tensor Operations

  2019cited by this paper
• Expressive power of recurrent neural networks

  2017cited by this paper
• Tensor Decomposition for Signal Processing and Machine Learning

  2016cited by this paper
• Tensorizing Neural Networks

  2015cited by this paper
• Putting MRFs on a Tensor Train

  2014cited by this paper
• Fast Multivariate Spatio-temporal Analysis via Low Rank Tensor Learning

  2014cited by this paper
• Fast and scalable polynomial kernels via explicit feature maps

  2013cited by this paper
• Multilinear Subspace Learning: Dimensionality Reduction of Multidimensional Data

  2013cited by this paper
• Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality

  2012cited by this paper
• Tensor Regression with Applications in Neuroimaging Data Analysis

  2012cited by this paper
• Random Projections for Support Vector Machines

  2012cited by this paper
• Concentration and moment inequalities for polynomials of independent random variables

  2011cited by this paper
• Tensor-Train Decomposition

  2011cited by this paper
• An almost optimal unrestricted fast Johnson-Lindenstrauss transform

  2010cited by this paper
• Random Projections for $k$-means Clustering

  2010cited by this paper
• NONNEGATIVEMATRIXANDTENSORFACTORIZATIONS APPLICATIONS TO EXPLORATORY MULTI-WAY DATA ANALYSIS AND BLIND SOURCE SEPARATION

  2009cited by this paper
• Tensor Decompositions and Applications

  2009cited by this paper
• The Fast Johnson--Lindenstrauss Transform and Approximate Nearest Neighbors

  2009cited by this paper
• Learning Multiple Layers of Features from Tiny Images

  2009cited by this paper
• Nonnegative Matrix and Tensor Factorizations - Applications to Exploratory Multi-way Data Analysis and Blind Source Separation

  2009cited by this paper
• Nonnegative Matrix and Tensor Factorization T

  2007cited by this paper
• MATLAB Tensor Toolbox

  2006cited by this paper
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

  2006cited by this paper
• Very sparse random projections

  2006cited by this paper
• The Random Projection Method

  2005cited by this paper
• An elementary proof of a theorem of Johnson and Lindenstrauss

  2003cited by this paper
• Finding frequent items in data streams

  2002cited by this paper
• Random projection in dimensionality reduction: applications to image and text data

  2001cited by this paper
• Experiments with Random Projection

  2000cited by this paper
• Matrix Variate Distributions

  1999cited by this paper
• Learning mixtures of Gaussians

  1999cited by this paper
• Two algorithms for nearest-neighbor search in high dimensions

  1997cited by this paper
• Extensions of Lipschitz mappings into Hilbert space

  1984cited by this paper
• Some mathematical notes on three-mode factor analysis

  1966cited by this paper
• The Expression of a Tensor or a Polyadic as a Sum of Products

  1927cited by this paper
• ON A FORMULA FOR THE PRODUCT-MOMENT COEFFICIENT OF ANY ORDER OF A NORMAL FREQUENCY DISTRIBUTION IN ANY NUMBER OF VARIABLES

  1918cited by this paper

• Oblivious Johnson--Lindenstrauss embeddings for compressed Tucker decompositions

  2025cites this paper
• Compressed Bayesian Tensor Regression

  2025influential citation
• Improved Analysis of Khatri-Rao Random Projections and Applications

  2025cites this paper
• Prismatic Synthesis: Gradient-based Data Diversification Boosts Generalization in LLM Reasoning

  2025cites this paper
• A User's Guide to KSig: GPU-Accelerated Computation of the Signature Kernel

  2025influential citation
• Improving LSH via tensorized random projection

  2024influential citation
• Long Sequence Modeling with Attention Tensorization: From Sequence to Tensor Learning

  2024cites this paper
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm

  2024cites this paper
• Oblivious subspace embeddings for compressed Tucker decompositions

  2024cites this paper
• Subspace embedding with random Khatri-Rao products and its application to eigensolvers

  2024cites this paper
• Random Fourier Signature Features

  2023cites this paper
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions

  2022cites this paper
• Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs

  2022influential citation
• Fast algorithms for least square problems with Kronecker lower subsets

  2022cites this paper
• Fast Algorithms for Monotone Lower Subsets of Kronecker Least Squares Problems

  2022cites this paper
• More Efficient Sampling for Tensor Decomposition

  2021cites this paper
• Rademacher Random Projections with Tensor Networks

  2021influential citation
• Randomized algorithms for rounding in the Tensor-Train format

  2021cites this paper
• Modewise Operators, the Tensor Restricted Isometry Property, and Low-Rank Tensor Recovery

  2021cites this paper
• Efficient Tensor Contraction via Fast Count Sketch

  2021cites this paper
• Tensor Train Random Projection

  2020influential citation
• Nearly sharp structured sketching for constrained optimization

  2020cites this paper
• The ITensor Software Library for Tensor Network Calculations

  2020cites this paper
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares

  2019cites this paper
• Guarantees for the Kronecker Fast Johnson-Lindenstrauss Transform Using a Coherence and Sampling Argument

  2019cites this paper
• Fast randomized matrix and tensor interpolative decomposition using CountSketch

  2019cites this paper