Constructive TT-representation of the tensors given as index interaction functions with applications

Gleb Ryzhakov, Ivan Oseledets

Overview

This paper introduces a method to directly construct Tensor Train (TT) representations of high-dimensional data when the underlying mathematical formula is known. By bypassing traditional iterative approximation methods, the authors achieve exact, sparse, and often rank-optimal decompositions. This approach significantly outperforms existing tools in speed and accuracy for complex problems spanning game theory, combinatorics, and matrix calculus.

The Curse of Dimensionality and the "Black Box" Problem

In the realm of high-dimensional data, researchers frequently encounter the "curse of dimensionality": as the number of dimensions ($d$) increases, the memory required to store a tensor grows exponentially ($n^d$). The Tensor Train (TT) format is a powerful compression tool that mitigates this by breaking a massive tensor into a chain of smaller "cores," reducing storage requirements to a manageable linear scale.

However, most existing techniques for finding these TT-cores—such as TT-cross or Alternating Least Squares (ALS)—treat the tensor as a "black box." They guess the values, check the error, and iterate. This iterative process is slow, prone to approximation errors, and ignores a crucial piece of information: often, we possess a symbolic formula (an "index interaction function") that dictates exactly how the indices relate to the value. The authors tackle the challenge of building TT-cores directly and exactly from these formulas, eliminating the need for guesswork.

Constructive Methods: From Logic to Tensors

The authors propose a constructive method based on what they term "derivative functions." The process unfolds in several key steps:

  1. Sequential Logic: They assume the tensor's value can be calculated by a sequence of functions where each step depends on the current index and the result of the previous step, much like a state machine.
  2. Linearization of States: The pivotal insight is mapping every possible output value of these intermediate functions to a unique basis vector. This transformation turns a sequence of potentially non-linear functions into a chain of matrix-vector multiplications.
  3. Core Construction: These matrices directly become the TT-cores. Because each input state maps to exactly one output state in the logic, the resulting cores are highly sparse (mostly zeros and ones), which makes subsequent mathematical operations incredibly fast.
  4. Rank Management: The "rank" of a TT-tensor determines its complexity. The authors provide a way to group "close" values together to keep the representation compact without losing significant accuracy.
Computation tree and corresponding Tensor Train (TT) format.

Applications and Benchmarks

Rather than standard image or text datasets, the paper evaluates the method on mathematically rigorous benchmarks where exact formulas are known:

  • Cooperative Games: Calculating payoffs and Shapley values for the "Shoes game," "Airport game," "Weighted majority," and "Bankruptcy" models.
  • Combinatorial Problems: The N-Queens puzzle (finding valid placements on a chessboard), the Partition problem, and the Knapsack problem.
  • Matrix Calculus: Calculating the Permanent of a matrix—a notoriously difficult problem in computer science.
  • Logic: Boolean Satisfiability (SAT) problems.

Key Insights

  • Formula as a Roadmap: If you know the "recipe" for your data, you shouldn't have to approximate it. Direct construction guarantees machine precision (e.g., $10^{-15}$ error), a level of accuracy that iterative methods rarely reach.
  • State Space = Rank: The complexity (rank) of the TT-representation is directly tied to the number of unique intermediate states in your calculation. If your logic has a small "memory," the tensor will be highly compressed.
  • Sparsity is a Superpower: Because the constructed cores are sparse, operations like summing all elements in a tensor become much faster than using dense approximate cores.
  • Unified Framework: The same underlying algorithm can solve a game theory problem, find a solution to the N-Queens puzzle, or calculate a matrix permanent simply by swapping the "derivative functions."

Key Results

Performance comparison on cooperative games.
  • Superior Accuracy: In cooperative game experiments, the constructive method achieved machine precision, while the standard "Cross" approximation method plateaued with significantly higher errors.
  • Speedup: The method is consistently faster than iterative alternatives. For example, in game theory applications, it provided results in a fraction of the time required by black-box solvers.
  • Optimal Complexity: For calculating matrix permanents, the method's complexity is $O(2^N N)$, which is remarkably close to the known optimal asymptotics of specialized algorithms like Ryser’s formula.
  • Rank Optimality: In many cases, the method automatically finds the lowest possible TT-rank, meaning the representation is as compressed as mathematically possible.

Limitations and Future Work

The primary limitation of this approach is state explosion. If the intermediate functions produce a massive number of unique values, the TT-ranks will explode, making the method memory-intensive. Additionally, the method currently requires manual design: a human must skillfully define the "derivative functions" for a specific problem, meaning it is not yet a fully automated "drop-in" replacement for arbitrary data.

Future work will likely focus on extending the algorithm to handle cases where the state space is large but the underlying tensor is still low-rank, potentially using more advanced rounding techniques during the construction phase.

Summary updated

Abstract

This paper presents a method to build explicit tensor-train (TT) representations. We show that a wide class of tensors can be explicitly represented with sparse TT-cores, obtaining, in many cases, optimal TT-ranks. Numerical experiments show that our method outperforms the existing ones in several practical applications, including game theory problems. Theoretical estimations of the number of operations show that in some problems, such as permanent calculation, our methods are close to the known optimal asymptotics, which are obtained by a completely different type of methods.
BibTeX
@inproceedings{ryzhakov2023constructive,
  author = {Gleb Ryzhakov and Ivan Oseledets},
  title = {{Constructive TT-representation of the tensors given as index interaction functions with applications}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=yLzLfM-Esnu},
}
Figure