Fast elementwise operations on tensor trains with alternating cross interpolation

• URL: http://arxiv.org/abs/2604.00037v1
• Date: Tue, 24 Mar 2026 18:23:00 GMT
• Title: Fast elementwise operations on tensor trains with alternating cross interpolation
• Abstract summary: Trains (TTs) are compressed representations of high-dimensional data that can be efficiently manipulated to perform calculations on the data.<n>In many applications, such as TT-based solvers for nonlinear partial differential equations, the most expensive step is an elementwise multiplication or similar elementwise operation on multiple TTs.<n>We present the alternating cross (ACI) algorithm that performs such operations in $O(3)$, while maintaining error control.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tensor trains (TTs), also known as matrix product states (MPS), are compressed representations of high-dimensional data that can be efficiently manipulated to perform calculations on the data. In many applications, such as TT-based solvers for nonlinear partial differential equations, the most expensive step is an elementwise multiplication or similar elementwise operation on multiple TTs. Known error-controlled algorithms for such operations scale as $O(χ^4)$, where $χ$ is the TT rank. If the rank of the output is smaller than $χ^2$, it is possible to formulate algorithms with better scaling. In this work, we present the alternating cross interpolation (ACI) algorithm that performs such operations in $O(χ^3)$, while maintaining error control. We demonstrate these properties on benchmark problems, achieving a significant speedup for TT ranks that are commonly encountered in practical applications.

Related papers

• Recursive Sketched Interpolation: Efficient Hadamard Products of Tensor Trains [3.1007879499686957]
  The Hadamard product of two tensors in the tensor-train (TT) format is a fundamental operation across various applications.<n>We introduce Recursive Sketched Interpolation (RSI), a scale product'' algorithm that computes the Hadamard product of TTs at a computational cost.
  arXiv  Detail & Related papers  (2026-02-20T04:07:37Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Efficient Network Automatic Relevance Determination [30.611086842690426]
  Network Automatic Relevance Determination (NARD) is an extension of ARD for linearly probabilistic models.<n>NARD simultaneously model sparse relationships between inputs $X in mathbb Rd times N$ and outputs $Y in mathbb Rm times N$.
  arXiv  Detail & Related papers  (2025-06-14T05:20:25Z)
• Tensor Train Multiplication [0.0]
  The computational complexity and memory requirements of the TTM algorithm scale as $chi3$ and $chi2$, respectively. This represents a significant improvement compared with the conventional approach. The TTM algorithm paves the way towards GPU accelerated tensor network simulations of computational fluid dynamics problems with large bond dimensions.
  arXiv  Detail & Related papers  (2024-10-10T12:36:49Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)
• Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
  We propose a linear-time approximation to compute the normalization constants of $rm SoftMax(XYT)$ for embedding vectors with bounded norms.<n>We show on some pre-trained embedding datasets that the proposed estimation method achieves higher or comparable accuracy with competing methods.<n>The proposed algorithm is interpretable and easily adapted to arbitrary embedding problems.
  arXiv  Detail & Related papers  (2023-03-30T15:48:26Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
  We propose two more efficient variants to compute the differentiable matrix square root and the inverse square root. For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP), and the other method is to use Matrix Pad'e Approximants (MPA) A series of numerical tests show that both methods yield considerable speed-up compared with the SVD or the NS iteration.
  arXiv  Detail & Related papers  (2022-01-29T10:00:35Z)
• Fast Differentiable Matrix Square Root [65.67315418971688]
  We propose two more efficient variants to compute the differentiable matrix square root. For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP) The other method is to use Matrix Pad'e Approximants (MPA)
  arXiv  Detail & Related papers  (2022-01-21T12:18:06Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem.
  arXiv  Detail & Related papers  (2021-06-02T12:50:56Z)
• Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
  The SOFT top-k operator approximates the output of the top-k operation as the solution of an Entropic Optimal Transport (EOT) problem. We apply the proposed operator to the k-nearest neighbors and beam search algorithms, and demonstrate improved performance.
  arXiv  Detail & Related papers  (2020-02-16T04:57:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.