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.
3. Progressive Heuristic Search
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.