# Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs

arXiv: https://arxiv.org/abs/2205.13163 · HTML: https://mlsanity.com/paper/2205.13163/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 60 references that are in the map.
- First posted on arXiv 26 May 2022.

## Builds on (most cited first, 13 of 13)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [TensorLy: Tensor Learning in Python](https://mlsanity.com/paper/1610.09555/) (2016)
- [Randomized Sketches of Convex Programs with Sharp Guarantees](https://mlsanity.com/paper/1404.7203/) (2014)
- [Solving high-dimensional parabolic PDEs using the tensor train format](https://mlsanity.com/paper/2102.11830/) (2021)
- [Tensorized Random Projections](https://mlsanity.com/paper/2003.05101/) (2020)
- [Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions](https://mlsanity.com/paper/2104.01101/) (2021)
- [More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees](https://mlsanity.com/paper/2110.07631/) (2021)
- [Spectral Tensor Train Parameterization of Deep Learning Layers](https://mlsanity.com/paper/2103.04217/) (2021)
- [Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time](https://mlsanity.com/paper/2202.04515/) (2022)
- [Efficient parallel CP decomposition with pairwise perturbation and multi-sweep dimension tree](https://mlsanity.com/paper/2010.12056/) (2020)
- [Tensor-structured sketching for constrained least squares](https://mlsanity.com/paper/2010.09791/) (2020)
- [Low Rank Approximation in Simulations of Quantum Algorithms](https://mlsanity.com/paper/2104.11396/) (2021)

## Built on by (most cited first, 5 of 5)

- [SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism](https://mlsanity.com/paper/2510.21599/) (2025)
- [Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions](https://mlsanity.com/paper/2207.07417/) (2022)
- [Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networks](https://mlsanity.com/paper/2210.03828/) (2022)
- [Projected Tensor-Tensor Products for Efficient Computation of Optimal Multiway Data Representations](https://mlsanity.com/paper/2409.19402/) (2024)
- [Constructing 3D Rotational Invariance and Equivariance with Symmetric Tensor Networks](https://mlsanity.com/paper/2508.12596/) (2025)

## Abstract (arXiv)

This work discusses tensor network embeddings, which are random matrices (S) with tensor network structure. These embeddings have been used to perform dimensionality reduction of tensor network structured inputs x and accelerate applications such as tensor decomposition and kernel regression. Existing works have designed embeddings for inputs x with specific structures, such that the computational cost for calculating Sx is efficient. We provide a systematic way to design tensor network embeddings consisting of Gaussian random tensors, such that for inputs with more general tensor network structures, both the sketch size (row size of S) and the sketching computational cost are low. We analyze general tensor network embeddings that can be reduced to a sequence of sketching matrices. We provide a sufficient condition to quantify the accuracy of such embeddings and derive sketching asymptotic cost lower bounds using embeddings that satisfy this condition and have a sketch size lower than any input dimension. We then provide an algorithm to efficiently sketch input data using such embeddings. The sketch size of the embedding used in the algorithm has a linear dependence on the number of sketching dimensions of the input. Assuming tensor contractions are performed with classical dense matrix multiplication algorithms, this algorithm achieves asymptotic cost within a factor of O(√m) of our cost lower bound, where m is the sketch size. Further, when each tensor in the input has a dimension that needs to be sketched, this algorithm yields the optimal sketching asymptotic cost. We apply our sketching analysis to inexact tensor decomposition optimization algorithms. We provide a sketching algorithm for CP decomposition that is asymptotically faster than existing work in multiple regimes, and show optimality of an existing algorithm for tensor train rounding.