Fast Tucker Rank Reduction for Non-Negative Tensors Using Mean-Field Approximation

Kazu Ghalamkari, Mahito Sugiyama

Tensors—multidimensional arrays—are the backbone of modern machine learning, used in everything from recommendation systems to image denoising. However, compressing these massive data structures into a "low-rank" form is a notorious computational headache. Traditional methods often rely on slow, iterative gradient descent that can easily get stuck in local minima.

In their NeurIPS 2021 paper, Kazu Ghalamkari and Mahito Sugiyama introduce a clever geometric shortcut called Legendre Tucker Rank reduction (LTR). By treating tensors as probability distributions, they have found a way to achieve low-rank approximations using fast, closed-form solutions instead of gradients.

TL;DR

Legendre Tucker Rank reduction (LTR) is a high-speed algorithm for approximating non-negative tensors. By leveraging information geometry and the "mean-field approximation" from physics, it provides a closed-form solution for rank reduction that is significantly faster than traditional gradient-based methods while maintaining competitive accuracy.

What Problem Does This Paper Address?

Finding a low-rank approximation for a matrix (a 2D tensor) is relatively straightforward thanks to Singular Value Decomposition (SVD). But for tensors of higher order (3D, 4D, etc.), the problem becomes much harder—often NP-hard.

For non-negative tensors (where every value is $\ge 0$), researchers typically use Non-negative Tucker Decomposition (NTD). The catch? NTD relies on gradient descent, which is computationally expensive, sensitive to initialization, and requires careful tuning of learning rates. The authors set out to find a "gradient-free" way to reduce the Tucker rank of a tensor without sacrificing quality.

Methods

The core innovation of LTR lies in Information Geometry. The authors treat a non-negative tensor as a discrete probability distribution and map it onto a statistical manifold.

  1. Mean-Field Connection: They prove that a rank-1 approximation of a tensor is mathematically equivalent to a "mean-field approximation"—a well-known technique in physics for approximating complex joint distributions as a product of independent ones.
  2. The Bingo Rule: They introduce a theoretical condition called the "bingo rule." If certain parameters in the geometric representation of the tensor are set to zero (a "bingo"), the Tucker rank of the tensor is guaranteed to drop.
  3. m-Projection: Instead of "sliding" down a gradient to find a low-rank version, LTR performs an m-projection. This is a geometric operation that projects the high-rank tensor onto a lower-rank subspace (the "bingo space").
  4. Closed-Form Iteration: Because the m-projection for these distributions has an exact analytical solution, the algorithm can iteratively reduce the rank of different "modes" of the tensor using simple closed-form formulas.
The relationship between rank-1 approximation, Legendre decomposition, and the mean-field equation.

Datasets

The authors evaluated LTR against standard NTD methods using both synthetic and real-world data:

  • Synthetic Tensors: Randomly generated non-negative tensors of order 3 and 5 with varying sizes.
  • 4DLFD: A 5th-order tensor dataset used in light-field depth estimation.
  • AttFace: A 3rd-order tensor dataset commonly used for face identification benchmarks.

Key Insights and Ideas

  • Physics Meets Linear Algebra: The realization that rank-1 tensor approximation is just mean-field theory in disguise is a powerful "aha moment." It bridges two seemingly disparate fields.
  • Geometry over Optimization: By reframing rank reduction as a projection on a manifold rather than a standard optimization problem, the authors bypassed the need for gradients entirely.
  • Efficiency through Structure: The "bingo rule" provides a structured way to enforce low-rank constraints that plays perfectly with the math of exponential families.
Visualizing how the bingo rule reduces the Tucker rank of a tensor.

Key Results

  • Massive Speedups: In synthetic tests, LTR was orders of magnitude faster than existing methods like NTD and lraSNTD. While other methods' runtimes exploded as tensor size increased, LTR remained remarkably efficient.
  • Competitive Accuracy: Despite being a "shortcut," LTR achieved Least Squares (LS) errors that were competitive with, and sometimes better than, the much slower gradient-based alternatives.
  • Robustness: Because it uses a closed-form solution, LTR isn't plagued by the initialization sensitivity or convergence issues that often haunt gradient descent.

Limitations and Future Work

  • Non-Negativity Only: The current framework relies heavily on the math of probability distributions, meaning it only works for non-negative tensors. Extending this to general tensors (with negative values) is a major open question.
  • Strict Positivity Assumption: The theoretical proofs assume all tensor elements are strictly positive ($>0$). While the algorithm works fine with zeros in practice, the theory needs further refinement to formally cover those cases.
  • Subspace Constraints: LTR searches a specific subspace defined by the bingo rules. While effective, this search space is technically smaller than that of a general Tucker decomposition, which might limit its flexibility in some edge cases.

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{ghalamkari2021fast,
  author = {Kazu Ghalamkari and Mahito Sugiyama},
  title = {{Fast Tucker Rank Reduction for Non-Negative Tensors Using Mean-Field Approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=RwdHpzTTGl},
}
Figure