A Closed Form Solution to Best Rank-1 Tensor Approximation via KL divergence Minimization

Kazu Ghalamkari, Mahito Sugiyama

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 essential for representing complex data structures in fields ranging from recommendation systems to signal processing. A critical task in tensor analysis is low-rank approximation, which compresses high-dimensional data while preserving its core features. However, unlike the Singular Value Decomposition (SVD) for 2D matrices, finding the optimal low-rank approximation for higher-order tensors is often NP-hard.

Existing methods for non-negative Tucker decomposition (NTD) typically rely on iterative gradient descent. These optimization-based approaches are computationally expensive, sensitive to initialization, and prone to local minima. This paper introduces the Legendre Tucker Rank Reduction (LTR) algorithm, which bypasses these issues by leveraging the geometric properties of probability distributions to provide a closed-form solution.

Methodology: Information Geometry and Mean-Field Approximation

The LTR algorithm is built upon the framework of information geometry. By treating a non-negative tensor as a discrete probability distribution, the authors map tensors onto a "statistical manifold." This manifold is characterized by two sets of coordinates: $\theta$ (canonical parameters) and $\eta$ (expectation parameters).

The Rank-1 and Mean-Field Connection

A central discovery of this work is that the best rank-1 approximation of a tensor (minimizing Kullback–Leibler divergence) is mathematically equivalent to a mean-field approximation. In statistical physics, mean-field theory approximates a joint distribution as a product of independent marginal distributions.

Geometric interpretation of mean-field and rank-1 approximations on a statistical manifold.

As shown in Figure 1, the rank-1 approximation is achieved via an m-projection onto the rank-1 subspace. Because this projection has a closed-form solution, the LTR algorithm can efficiently update tensor components without needing gradient-based optimization. The "conservation law" of $\eta$-parameters during this projection allows for direct analytical calculation of the target state.

Key Insights: The "Bingo Rule" for Tucker Rank Reduction

Beyond rank-1 approximations, the authors identified a specific condition on the $\theta$-coordinates that forces a tensor to have a lower Tucker rank. Termed the "bingo rule," this condition translates complex rank constraints into simple linear constraints within the coordinate system of the manifold.

Visual representation of Tucker rank reduction for different target ranks.

By iteratively applying the mean-field approximation across different dimensions of the tensor, the LTR algorithm satisfies these "bingo" conditions. This process effectively reduces the Tucker rank of the tensor in a step-wise, analytical fashion (Figure 2).

Experimental Evaluation

The LTR algorithm was evaluated against standard NTD and efficient variants like lraSNTD using both synthetic and real-world datasets, including the AT&T Database of Faces (AttFace) and a 4D Light Field Dataset (4DLFD).

  • Performance: LTR demonstrated significant speed advantages, with running times that remained relatively flat as tensor dimensionality increased, whereas gradient-based methods scaled poorly.
  • Accuracy: LTR achieved competitive or superior accuracy in terms of Least Squares (LS) and KL divergence errors.
  • Robustness: Due to its reliance on closed-form geometric projections rather than local search, the method is less sensitive to initialization than traditional optimization techniques.

Conclusion

The Legendre Tucker Rank Reduction algorithm represents a shift from optimization-centric to geometry-centric tensor approximation. By bridging tensor algebra with statistical physics and information geometry, the authors provide a fast, robust, and theoretically grounded method for non-negative tensor decomposition. Future work may extend this framework to handle tensors with negative values or establish further theoretical guarantees for tensors containing zero elements.

Summary updated

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.
BibTeX
@inproceedings{ghalamkari2021closed,
  author = {Kazu Ghalamkari and Mahito Sugiyama},
  title = {{A Closed Form Solution to Best Rank-1 Tensor Approximation via KL divergence Minimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=RwdHpzTTGl},
}
Figure