{"id":"arxiv/2603.11009","url":"https://arxiv.org/abs/2603.11009","tags":["math.NA","cs.DS"],"score":0,"title":"Linear-Scaling Tensor Train Sketching","domain":"math.NA","source":"arxiv","authors":["Paul Cazeaux","Mi-Song Dupuy","Rodrigo Figueroa Justiniano"],"reviews":0,"subject":"math.NA","summary":"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 = \\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 =…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-11","reactions":{}}