{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicnlseldxqqpyjkv3zc2nyqehmx6vhudki77arfsqjydg3gh2qbdi",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mgvtzqtghnt2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.11009v1",
  "publishedAt": "2026-03-12T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Paul Cazeaux",
    "Mi-Song Dupuy",
    "Rodrigo Figueroa Justiniano"
  ],
  "textContent": "**Authors:** Paul Cazeaux, Mi-Song Dupuy, Rodrigo Figueroa Justiniano\n\nWe 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.",
  "title": "Linear-Scaling Tensor Train Sketching"
}