Linear-Scaling Tensor Train Sketching

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.