Linear-Scaling Tensor Train Sketching
2026-03-11 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors present a new method called Block Sparse Tensor Train (BSTT) sketch, which is a technique to efficiently compress and work with high-dimensional data in a format called tensor train. By adjusting two parameters, BSTT can mimic other existing sketch methods, providing flexibility. They prove that BSTT works well in preserving important features of the data (oblivious subspace embedding and injection) with guarantees that grow only linearly with the data's complexity, unlike previous methods that grew exponentially. Their findings also improve error bounds for common tensor operations, and they validate their theory through experiments including applications in quantum chemistry.
Block Sparse Tensor Train (BSTT)Tensor Train (TT) formatRandom projectionOblivious subspace embedding (OSE)Oblivious subspace injection (OSI)Khatri-Rao sketchGaussian TT sketchQB factorizationRandomized TT roundingQuantum chemistry
Authors
Paul Cazeaux, Mi-Song Dupuy, Rodrigo Figueroa Justiniano
Abstract
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.