# Linear-Scaling Tensor Train Sketching

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2026.

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

- [Stochastic trace estimation with tensor train random vectors](https://mlsanity.com/paper/2606.15679/) (2026)

## Abstract (arXiv)

We introduce the TTStack sketch, a structured random projection tailored to the tensor train (TT) format that unifies existing TT-adapted sketching operators. By varying two integer parameters P and R, TTStack interpolates between the Khatri-Rao sketch (R=1) and the Gaussian TT sketch (P=1). We prove that TTStack satisfies an oblivious subspace embedding (OSE) property with parameters R = O(d(r+log 1/δ)) and P = O(varepsilon-2), and an oblivious subspace injection (OSI) property under the condition R = O(d) and P = O(varepsilon-2(r + log r/δ)). Both guarantees depend only linearly on the tensor order d and on the subspace dimension r, in contrast to prior constructions that suffer from exponential scaling in d. As direct consequences, we derive quasi-optimal error bounds for the QB factorization and randomized TT rounding. The theoretical results are supported by numerical experiments on synthetic tensors, Hadamard products, and a quantum chemistry application.