Matrix Factorization in Tropical and Mixed Tropical-Linear Algebras

Ioannis Kordonis, Emmanouil Theodosis, George Retsinas, Petros Maragos

TL;DR

This paper explores Matrix Factorization (MF) through the lens of tropical algebra—a mathematical framework where addition becomes "maximum" and multiplication becomes "addition." The authors propose improved algorithms to solve Tropical Matrix Factorization (TMF) and introduce a novel hybrid approach called Tropical Compression (TC) that outperforms traditional linear methods in recommendation system tasks.

What Problem Does This Paper Address?

Matrix Factorization is a cornerstone of modern machine learning, used for everything from suggesting movies to reducing data dimensions. Usually, this happens in standard linear algebra (multiplying and adding). However, many real-world phenomena—like human utility functions or certain geometric structures—are non-linear and "piecewise-linear."

Tropical algebra is perfectly suited for these structures, but it comes with a major headache: optimization. Tropical Matrix Factorization (TMF) is NP-hard. Standard Gradient Descent (GD) fails because the "max" operation creates "ineffective" entries—parameters that don't contribute to the current maximum and thus have a zero gradient. These entries get "stuck," leading the model into poor local optima.

Methods

The authors tackle these challenges with two primary contributions:

  1. Noise-Enhanced Gradient Descent for TMF: To prevent parameters from getting stuck, they introduce Gradient Descent with Multiplicative Noise (GDMN) and Additive Noise (GDAN). By adding small perturbations to the "ineffective" entries, they ensure these parameters keep moving, giving them a chance to eventually contribute to the "max" and improve the overall fit.
  2. Tropical Compression (TC): They propose a new "mixed" factorization problem: $Y \approx A \boxplus (BX)$. Here, $BX$ is a standard linear matrix product, which is then passed through a tropical product ($\boxplus$) with matrix $A$.
  3. The Algorithm: They solve this using a Projected Gradient Descent approach. They treat the internal product as a single matrix $C$, optimize it tropically, and then use Singular Value Decomposition (SVD) to project $C$ back into a low-rank space that can be decomposed into $B$ and $X$.

Datasets

The researchers evaluated their methods on:

  • Synthetic Data: Randomly generated matrices used to test the robustness of the GDMN and GDAN algorithms against standard GD and the existing FastSTMF algorithm.
  • MovieLens 100k: A classic benchmark containing 100,000 ratings from 943 users on 1,682 movies.
  • MovieLens 1M: A larger dataset with 1 million ratings from 6,000 users on 4,000 movies.

Key Insights and Ideas

  • The "Ineffective Entry" Problem: In tropical math, only the "winner" (the maximum value) gets a gradient update. The authors realized that "losing" entries shouldn't just sit still; they need a "nudge" (noise) to stay relevant for future iterations.
  • Modeling Human Preference: The TC formulation ($A \boxplus (BX)$) has a beautiful physical interpretation. In economics, utility functions are often modeled as concave. Because tropical polynomials are inherently piecewise-linear and concave, the TC model naturally mimics how users weigh different features of an item to decide if they like it.
  • Hybrid Power: By combining linear algebra (for feature extraction) with tropical algebra (for the final decision/utility mapping), the TC model captures nuances that purely linear models miss.

Key Results

  • Superior Optimization: On synthetic data, the GDAN-NZM (Non-Zero Mean Additive Noise) variant significantly outperformed standard Gradient Descent and the state-of-the-art FastSTMF, achieving much lower Frobenius error (e.g., 0.60 vs 1.38 for a specific noise level).
  • Recommendation Performance: On the MovieLens 1M dataset, the Tropical Compression (TC) model achieved a Hit Rate at 10 (HR@10) of 0.743. This outperformed a "carefully optimized and regularized linear factorization," which scored 0.731.
  • Efficiency: TC achieved these results with a smaller number of parameters compared to pure TMF while maintaining an intuitive interpretation.

Limitations and Future Work

  • Regularization: The authors note that while their results are promising, they haven't yet explored the use of formal regularization techniques (like L1 or L2) within the tropical framework, which could further improve generalization.
  • Sparsity: The current study focuses on dense approximations. Investigating how these tropical methods handle extremely sparse data—common in massive-scale recommendation systems—is a suggested next step.
  • Theoretical Bounds: While the noise-based GD works empirically, a formal theoretical analysis of its convergence properties in the tropical landscape remains an open challenge.

Summary updated

Abstract

Matrix Factorization (MF) has found numerous applications in Machine Learning and Data Mining, including collaborative filtering recommendation systems, dimensionality reduction, data visualization, and community detection. Motivated by the recent successes of tropical algebra and geometry in machine learning, we investigate two problems involving matrix factorization over the tropical algebra. For the first problem, Tropical Matrix Factorization (TMF), which has been studied already in the literature, we propose an improved algorithm that avoids many of the local optima. The second formulation considers the approximate decomposition of a given matrix into the product of three matrices where a usual matrix product is followed by a tropical product. This formulation has a very interesting interpretation in terms of the learning of the utility functions of multiple users. We also present numerical results illustrating the effectiveness of the proposed algorithms, as well as an application to recommendation systems with promising results.
BibTeX
@inproceedings{kordonis2024matrix,
  author = {Ioannis Kordonis and Emmanouil Theodosis and George Retsinas and Petros Maragos},
  title = {{Matrix Factorization in Tropical and Mixed Tropical-Linear Algebras}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=WgAhHl4NDg},
}
Figure