Abstract
We present an efficient low-rank approximation algorithm for non-negative tensors. The algorithm is derived from our two findings: First, we show that rank-1 approximation for tensors can be viewed as a mean-field approximation by treating each tensor as a probability distribution. Second, we theoretically provide a sufficient condition for distribution parameters to reduce Tucker ranks of tensors; interestingly, this sufficient condition can be achieved by iterative application of the mean-field approximation. Since the mean-field approximation is always given as a closed formula, our findings lead to a fast low-rank approximation algorithm without using a gradient method. We empirically demonstrate that our algorithm is faster than the existing non-negative Tucker rank reduction methods and achieves competitive or better approximation of given tensors.
Introduction
Tensors, or multidimensional arrays, are fundamental data structures in modern machine learning, appearing in contexts ranging from recommendation systems to computer vision. To manage the high dimensionality of these arrays, researchers often employ low-rank approximations, such as the Tucker decomposition, which compresses a large tensor into a smaller core tensor and several factor matrices.
However, finding an optimal low-rank approximation for tensors is a notoriously difficult, often NP-hard, problem. Traditional methods for non-negative tensors typically rely on gradient-based optimization. These approaches are computationally demanding, sensitive to initialization, and require meticulous tuning of hyperparameters like learning rates. This paper introduces Legendre Tucker Rank Reduction (LTR), a gradient-free alternative that leverages statistical physics and information geometry to achieve significant speedups.
Theoretical Framework: Tensors as Distributions
The core innovation of LTR lies in re-envisioning non-negative tensors as discrete probability distributions. This perspective allows the application of Information Geometry, which explores the geometric structure of statistical manifolds.
A key theoretical bridge established by the authors is the equivalence between rank-1 tensor approximation and mean-field approximation. In statistical physics, mean-field theory approximates complex joint distributions as products of independent marginal distributions. Mathematically, the authors prove that finding the best rank-1 approximation (in terms of KL divergence) is identical to a mean-field approximation.
As shown in Figure 2, the process involves projections within the statistical manifold. The rank-1 approximation corresponds to an $m$-projection, which is well-defined and unique in this geometric context.
The LTR Algorithm and the "Bingo Rule"
Beyond rank-1 approximations, the authors provide a sufficient condition for reducing the Tucker rank of a tensor. They identify a specific set of parameters in the $\theta$-coordinate system (the natural parameters of the distribution) that, when set to zero, guarantee a reduction in rank. They colloquially refer to this as the "bingo rule."
The LTR algorithm iteratively applies the closed-form mean-field approximation to specific subtensors identified by this bingo rule. Because the solution is obtained via a closed-form formula rather than iterative gradient steps, the algorithm is exceptionally fast and stable.
Figure 4 illustrates the structure of the target Tucker rank and the corresponding sets of indices (the "bingo" sets) that the algorithm targets for reduction.
Experimental Results
The authors evaluated LTR against state-of-the-art methods, including Non-negative Tucker Decomposition (NTD) and lraSNTD, across synthetic and real-world datasets:
- Synthetic Tensors: LTR demonstrated orders of magnitude speed improvement as tensor size increased, maintaining linear scalability.
- 4D Light Field Dataset (4DLFD): In computer vision tasks, LTR provided competitive accuracy with significantly lower computational overhead.
- AT&T Database of Faces: LTR achieved lower reconstruction errors (both Least Squares and KL divergence) compared to traditional gradient-based benchmarks.
Conclusion
LTR represents a paradigm shift in tensor decomposition by moving from optimization-based approaches to geometric, closed-form solutions. By connecting tensor rank to mean-field theory, the authors provide a robust, fast, and scalable tool for data compression. While currently limited to non-negative and strictly positive tensors, this geometric framework opens new avenues for exploring other tensor formats and integrating these efficient approximations into deep learning architectures.
Summary updated