Learning the Optimal Rank in Tensor Decompositions

291 concepts230 papers1 proposal

In matrix algebra, finding a low-rank approximation is a solved problem. If you want to compress a two-dimensional dataset, you compute its Singular Value Decomposition (SVD), sort the singular values, and truncate the smallest ones. This gives you the mathematically optimal low-rank representation for any desired budget.

When we move from matrices to high-dimensional tensors, this mathematical luxury completely vanishes. Determining the rank of a tensor—or the optimal dimensions of its constituent cores—is an NP-hard problem. Yet, finding this rank is the single most critical step in tensor-based machine learning, signal processing, and scientific computing.

The Fundamental Trade-Off

Tensor decompositions break a massive, high-dimensional tensor into smaller, interconnected "core" tensors. The dimensions of these connections are known as the tensor rank or bond dimensions. Choosing these ranks forces a delicate balancing act between two opposing failure modes:

   Rank Too Low                                Rank Too High
  [ Underfitting ] <------------------------> [ Overfitting ]
  Information loss                             Computational explosion
  Poor expressivity                            Numerical instability

As explained by Andrzej Cichocki et al. in their foundational monograph, Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions, selecting a rank that is too low strips away critical structural information, leading to severe underfitting. Conversely, setting the rank too high causes the parameter count to explode, destroying the storage and computational benefits of the compression format and causing the model to overfit to noise.

This challenge is pervasive across domains. For instance, in deep learning compression, Anh Huy Phan 0001 et al. note in Stable Low-rank Tensor Decomposition for Compression of Convolutional Neural Network that finding the ideal rank for each layer of a deep network is computationally intractable using traditional methods. In multi-agent reinforcement learning, Anuj Mahajan et al. encounter the same barrier in Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning, where an incorrectly specified rank either cripples the expressivity of the joint action-value function or destroys sample efficiency.

Why Tensor Rank Selection is Hard

To understand why this is an NP-hard problem, consider the difference in geometry between matrices and advanced tensor networks like Tensor Trains (TT) or Tensor Rings (TR).

In a matrix, rank is a single integer. In a Tensor Ring decomposition, the rank is a vector of integers, where each element defines the bond dimension between adjacent cores. As highlighted by Nannan Li et al. in Heuristic rank selection with progressively searching tensor ring network, the number of possible rank combinations grows exponentially with the number of dimensions. If a tensor has 10 dimensions and you consider just 10 possible values for each bond dimension, the search space encompasses $10^{10}$ configurations. Manual grid search or brute-force cross-validation becomes instantly impossible.

Because there is no closed-form analytical solution, early implementations relied on fixed schedulers or empirical trial-and-error. As Yuchao Lin et al. point out in Tensor Decomposition Networks for Fast Machine Learning Interatomic Potential Computations, these rigid heuristics fail to adapt dynamically during training, leaving significant efficiency and accuracy on the table.

Modern Strategies for Automated Rank Selection

To bypass the exponential search space, recent research focuses on learning the optimal rank natively during the model's training phase. Three main paradigms have emerged:

1. Budget-Aware Optimization

Instead of treating rank selection as a preprocessing step, some methods formulate it as a constrained optimization problem solved during backpropagation. In BATUDE: Budget-Aware Neural Network Compression Based on Tucker Decomposition, Miao Yin et al. introduce a framework that learns the optimal tensor ranks in a single training run by optimizing under an explicit hardware or size budget, allowing the network to prune its own unneeded latent dimensions.

2. Probabilistic and Bayesian Rank Learning

Bayesian frameworks treat the tensor ranks as latent variables governed by sparsity-inducing priors. By maximizing the evidence lower bound (ELBO), these models automatically extinguish redundant rank dimensions.

For example, Yunzhi Jin et al. utilize variational inference in Variational Bayesian Logistic Tensor Regression with Application to Image Recognition to dynamically discover structural complexity during training. Similarly, in When Bayesian Tensor Completion Meets Multioutput Gaussian Processes: Functional Universality and Rank Learning, Siyuan Li et al. demonstrate that integrating rank learning into a probabilistic framework provides a principled way to balance the signal-to-noise ratio, preventing the model from overestimating the rank and fitting to noise.

When exact optimization is impossible, intelligent search algorithms can navigate the hyperparameter space efficiently. The aforementioned work by Nannan Li et al. leverages a progressive genetic algorithm that iteratively "zooms in" on high-performing rank regions, achieving up to a 200x speedup over standard heuristic searches.

By shifting from manual tuning to automated, adaptive rank determination, these methods unlock the true power of tensor networks—allowing models to achieve maximum compression and expressivity without human-in-the-loop guesswork.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_tensor_rank_selection_b3190d8a,
  title = {tensor rank selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tensor-rank-selection/rdr_b3190d8a15924a089e15afbfc1b93567},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_tensor_rank_selection_b3190d8a_v1,
  title = {tensor rank selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tensor-rank-selection/rdr_b3190d8a15924a089e15afbfc1b93567/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake