Fast matrix-vector products in tensor-train format via structured sketching
Abstract
We propose a randomized, streamable algorithm that computes a tensor-train approximation of a matrix-vector product without ever forming the full intermediate tensor. We develop three contraction strategies for streaming tensor-train approximation (STTA): sequential, fused, and pre-sketched. We focus on the regime of large operator mode sizes and show that pre-sketching can provide significant speed-ups when a lower-rank approximation of the input is sought, by pre-computing all sketch-related contractions with the operator. The pre-sketched strategy can also accelerate successive randomized compression (SRC), although to a lesser extent since its second sweep depends on the input vector and cannot be pre-computed. We compare the three strategies in terms of computational cost and memory, and demonstrate their performance on synthetic and application-driven examples where rank reduction is relevant.
Related
- Functional Tensor Trains for High-Order Greeks and Exposure Tails of Multi-Asset Structured Products
- Generative modeling via hierarchical tensor sketching
- AWE: Adaptive Weight Encoding for Exact Integer Matrix Products with Fewer GEMMs on FP4 Tensor Cores
- New hierarchical matrices for fast kernel matrix-vector products with Applications to Gaussian processes and kernel ridge regression
- Sketch-and-Restart: Randomized Sketching in Quadrature-Based Restarting for Matrix Functions
BibTeX
@misc{bucci2026fast,
title = {{Fast matrix-vector products in tensor-train format via structured sketching}},
author = {Alberto Bucci and Stefan Güttel and John W. Pearson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23451},
eprint = {2610.23451},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23451},
}
RIS
TY - UNPB
TI - Fast matrix-vector products in tensor-train format via structured sketching
AU - Alberto Bucci
AU - Stefan Güttel
AU - John W. Pearson
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23451
UR - https://arxiv.org/abs/2610.23451
AB - We propose a randomized, streamable algorithm that computes a tensor-train approximation of a matrix-vector product without ever forming the full intermediate tensor. We develop three contraction strategies for streaming tensor-train approximation (STTA): sequential, fused, and pre-sketched. We focus on the regime of large operator mode sizes and show that pre-sketching can provide significant speed-ups when a lower-rank approximation of the input is sought, by pre-computing all sketch-related contractions with the operator. The pre-sketched strategy can also accelerate successive randomized compression (SRC), although to a lesser extent since its second sweep depends on the input vector and cannot be pre-computed. We compare the three strategies in terms of computational cost and memory, and demonstrate their performance on synthetic and application-driven examples where rank reduction is relevant.
ER -