Recursive Sketched Interpolation: Efficient Hadamard Products of Tensor Trains
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915809170817024 |
|---|---|
| author | Meng, Zhaonan Khoo, Yuehaw Li, Jiajia Stoudenmire, E. Miles |
| author_facet | Meng, Zhaonan Khoo, Yuehaw Li, Jiajia Stoudenmire, E. Miles |
| contents | The Hadamard product of two tensors in the tensor-train (TT) format is a fundamental operation across various applications, such as TT-based function multiplication for nonlinear differential equations or convolutions. However, conventional methods for computing this product typically scale as at least $\mathcal{O}(χ^4)$ with respect to the TT bond dimension (TT-rank) $χ$, creating a severe computational bottleneck in practice. By combining randomized tensor-train sketching with slice selection via interpolative decomposition, we introduce Recursive Sketched Interpolation (RSI), a ``scale product'' algorithm that computes the Hadamard product of TTs at a computational cost of $\mathcal{O}(χ^3)$. Benchmarks across various TT scenarios demonstrate that RSI offers superior scalability compared to traditional methods while maintaining comparable accuracy. We generalize RSI to compute more complex operations, including Hadamard products of multiple TTs and other element-wise nonlinear mappings, without increasing the complexity beyond $\mathcal{O}(χ^3)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_17974 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Recursive Sketched Interpolation: Efficient Hadamard Products of Tensor Trains Meng, Zhaonan Khoo, Yuehaw Li, Jiajia Stoudenmire, E. Miles Quantum Physics Numerical Analysis The Hadamard product of two tensors in the tensor-train (TT) format is a fundamental operation across various applications, such as TT-based function multiplication for nonlinear differential equations or convolutions. However, conventional methods for computing this product typically scale as at least $\mathcal{O}(χ^4)$ with respect to the TT bond dimension (TT-rank) $χ$, creating a severe computational bottleneck in practice. By combining randomized tensor-train sketching with slice selection via interpolative decomposition, we introduce Recursive Sketched Interpolation (RSI), a ``scale product'' algorithm that computes the Hadamard product of TTs at a computational cost of $\mathcal{O}(χ^3)$. Benchmarks across various TT scenarios demonstrate that RSI offers superior scalability compared to traditional methods while maintaining comparable accuracy. We generalize RSI to compute more complex operations, including Hadamard products of multiple TTs and other element-wise nonlinear mappings, without increasing the complexity beyond $\mathcal{O}(χ^3)$. |
| title | Recursive Sketched Interpolation: Efficient Hadamard Products of Tensor Trains |
| topic | Quantum Physics Numerical Analysis |
| url | https://arxiv.org/abs/2602.17974 |