Linear-Scaling Tensor Train Sketching
This work addresses a bottleneck in tensor computations for fields like quantum chemistry by providing a more efficient sketching method, though it is incremental as it builds on existing tensor train sketching operators.
The paper tackles the problem of exponential scaling in tensor order for sketching in tensor train format by introducing the Block Sparse Tensor Train (BSTT) sketch, which achieves linear scaling in tensor order and subspace dimension, as proven with error bounds for applications like QB factorization and TT rounding.
We introduce the Block Sparse Tensor Train (BSTT) 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$, BSTT interpolates between the Khatri-Rao sketch ($R=1$) and the Gaussian TT sketch ($P=1$). We prove that BSTT satisfies an oblivious subspace embedding (OSE) property with parameters $R = \mathcal{O}(d(r+\log 1/δ))$ and $P = \mathcal{O}(\varepsilon^{-2})$, and an oblivious subspace injection (OSI) property under the condition $R = \mathcal{O}(d)$ and $P = \mathcal{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.