Breaking the Curse of Dimensionality with Tensor Trains

431 concepts254 papers1 proposal

Imagine a function or a dataset that depends on $d$ separate variables, where each variable is discretized into $N$ points. Storing this information as a dense grid requires $N^d$ parameters. If $N=100$ and $d=10$, you need $100^{10} = 10^{20}$ elements—a memory requirement that vastly exceeds the capacity of any modern supercomputer. This exponential explosion of data is known as the curse of dimensionality.

As noted by Martin Stoll in a comprehensive survey of numerical linear algebra, traditional matrix methods struggle to scale when moving from two-dimensional tables to high-order tensors. While deep neural networks are frequently used as a black-box solution to bypass this curse, they often suffer from training instabilities and lack exact mathematical tractability.

The Tensor Train (TT) decomposition provides a rigorous, linear-algebraic alternative. It allows us to compress exponential state spaces into polynomial or even linear representations, and crucially, it lets us perform complex mathematical operations directly within this compressed format.


The Core Intuition: Chaining the Dimensions

How do we break an exponential space into something manageable? The core intuition behind the Tensor Train format—originally popularized in quantum physics as Matrix Product States—is to factorize a high-dimensional tensor into a linear chain of low-order tensors.

Instead of indexing every combination of dimensions simultaneously, a $d$-dimensional tensor $\mathcal{A}$ is represented as a sequence of $d$ interconnected third-order "core" tensors. As Yannis Panagakis explains, this structure allows for extreme compression ratios. To find a single entry $\mathcal{A}(i_1, i_2, \dots, i_d)$ in the full tensor, we evaluate a sequence of matrix multiplications:

$$\mathcal{A}(i_1, i_2, \dots, i_d) = G_1(i_1) G_2(i_2) \dots G_d(i_d)$$

where each $G_k(i_k)$ is a small matrix of size $R_{k-1} \times R_k$ extracted from the $k$-th core tensor. The internal dimensions $R_k$ are known as the tensor ranks.

   i₁          i₂          i₃                  id
   │           │           │                   │
┌──┴──┐     ┌──┴──┐     ┌──┴──┐             ┌──┴──┐
│ G₁  ├──R₁─┤ G₂  ├──R₂─┤ G₃  ├──R₃─ ··· ───┤ Gd  │
└─────┘     └─────┘     └─────┘             └─────┘

If the maximum rank is bounded by $R$, the total storage drops from $O(N^d)$ to $O(d \cdot N \cdot R^2)$. The complexity shifts from exponential to linear with respect to the number of dimensions $d$. This allows researchers to manipulate massive state spaces by maintaining them entirely in a compressed, factorized format—a property leveraged by Kim Batselier to scale Kalman filters to astronomical state dimensions without ever explicitly constructing the full covariance matrices.


Operating on Compressed Spaces

The true power of the TT format is that you can add, multiply, integrate, and differentiate tensors directly within the compressed format without ever decompressing them back into the exponential $O(N^d)$ space. This makes it an ideal engine for solving high-dimensional differential equations and control problems.

Solving High-Dimensional PDEs

In physical and financial modeling, partial differential equations (PDEs) often suffer from high dimensionality due to numerous interacting state variables. Lorenz Richter et al. demonstrated that the TT format provides a computationally efficient alternative to neural networks for high-dimensional parabolic PDEs. By transforming the continuous PDE into a series of small, interconnected linear systems, the authors bypass the curse of dimensionality entirely, achieving solutions orders of magnitude faster than deep learning approaches.

Optimal Control and the Bellman Equation

In reinforcement learning and optimal control, calculating the value function requires solving the Hamilton–Jacobi–Bellman equation across a multi-dimensional state space. Mathias Oster et al. and Leon Sallandt et al. utilized hierarchical tensor formats to compress these value functions. By factorizing the multi-variable coefficient tensor into a sequence of low-rank 3D cores, they reduced the degrees of freedom to polynomial growth, enabling real-time feedback control for complex systems. Peter Kritzer et al. similarly demonstrated that this algebraic compression makes previously intractable physical and financial control systems manageable on standard computing hardware.


Generalizing to Continuous Fields and Machine Learning

The concept extends naturally beyond discrete grids. When dealing with continuous functions or probability distributions, researchers use Functional Tensor Trains (FTT), where the cores represent continuous univariate basis functions rather than discrete indices.

Scalable Integration and Sampling

For high-dimensional uncertainty quantification, Chunfeng Cui developed a framework where multivariate integrals are computed efficiently by decomposing them into a sequence of low-dimensional matrix-vector products using an FTT representation. This strategy allows for scalable integration across hundreds of highly correlated parameters.

Similarly, Paul Hagemann et al. utilized low-rank functional tensor formats to represent high-dimensional velocity fields for sampling from complex Boltzmann densities, avoiding the mode collapse and heavy hyperparameter tuning typical of neural network approaches.

Probabilistic Modeling and Language

In machine learning, the TT format serves as a powerful structural prior. Georgii S. Novikov et al. applied tensor trains to density estimation, representing high-dimensional probability densities as linear basis expansions with compressed coefficient tensors.

For sequential data, Zhan Su et al. introduced a Tensor Train Language Model (TTLM). By representing sentences as a tensor product of constituent vectors and factorizing the resulting high-dimensional space into a sequence of smaller cores, the authors capture high-order correlations without suffering from exponential state growth.


Advanced Extensions: Quantization and Hybrid Formats

To push the boundaries of compression even further, the TT format can be combined with other tensor structures or quantization techniques.

Quantized Tensor Trains (QTT)

For problems requiring extreme grid resolution, a long vector (e.g., of size $2^L$) can be reshaped into a high-dimensional virtual tensor of size $2 \times 2 \times \dots \times 2$ ($L$ times). Applying the TT format to this reshaped tensor results in a representation where the parameter count scales logarithmically ($O(L)$) with the grid size. Carlo Marcati et al. proved that QTT compression can efficiently solve singularly perturbed boundary value problems on virtual grids as large as $2^{50}$ points, reducing computational complexity to a polylogarithmic scale.

Hybrid Formats

Sometimes a single format is not enough to capture all structural redundancies. Yuning Qiu et al. proposed a hybrid model combining Tucker decomposition (which excels at initial dimensionality reduction per mode) with Tensor Train decomposition (which excels at capturing global correlations across modes). This hybrid approach leverages the strengths of both formats to accelerate Tensor Robust Principal Component Analysis and image denoising.


Why It Works

The Tensor Train decomposition works because it exploits a fundamental property of many physical and mathematical systems: high-dimensional variables rarely interact all at once in a fully dense, chaotic fashion. Instead, their correlations are often localized or can be chained together sequentially. By organizing high-dimensional spaces into a train of low-order cores, the TT format replaces the intractable exponential wall of the curse of dimensionality with a clear, computationally efficient path forward.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 285 papers
  2. Version 1 · 2026-10-04 · 394 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_tensor_train_decomposition_low_rank_tens_d0161c1d,
  title = {tensor train decomposition (low-rank tensor decomposition)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tensor-train-decomposition-low-rank-tensor-decomposition/rdr_d0161c1d622c4e0790b848f56bded4ee},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_tensor_train_decomposition_low_rank_tens_d0161c1d_v2,
  title = {tensor train decomposition (low-rank tensor decomposition)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tensor-train-decomposition-low-rank-tensor-decomposition/rdr_d0161c1d622c4e0790b848f56bded4ee/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake