Matrix Factorization in Tropical and Mixed Tropical-Linear Algebras

Ioannis Kordonis, Emmanouil Theodosis, George Retsinas, Petros Maragos

Abstract

This paper investigates Matrix Factorization (MF) within tropical and mixed tropical-linear algebraic frameworks. Tropical algebra, where addition is replaced by "maximum" and multiplication by "addition," is well-suited for modeling piecewise-linear and concave structures like human utility functions. However, Tropical Matrix Factorization (TMF) is NP-hard and prone to local optima due to "ineffective" entries with zero gradients. We propose Noise-Enhanced Gradient Descent algorithms—Gradient Descent with Multiplicative Noise (GDMN) and Additive Noise (GDAN)—to overcome these optimization hurdles. Furthermore, we introduce Tropical Compression (TC), a hybrid model combining linear feature extraction with tropical utility mapping. Empirical results on synthetic and MovieLens datasets demonstrate that our noise-enhanced algorithms significantly outperform standard methods and that TC provides superior performance in recommendation tasks compared to traditional linear factorization.

Introduction

Matrix Factorization is a cornerstone of modern machine learning, used for tasks ranging from recommendation systems to dimensionality reduction. While typically performed in standard linear algebra, many real-world phenomena exhibit non-linear, piecewise-linear behaviors. Tropical algebra provides a natural framework for these structures, but it introduces significant optimization challenges. In tropical products, only the "maximum" entry receives a gradient update, causing other "ineffective" entries to become stuck. This paper addresses these challenges through noise-enhanced optimization and a novel hybrid modeling approach.

Methodology

Noise-Enhanced Gradient Descent

To prevent parameters from becoming trapped in poor local optima, we introduce small perturbations to "ineffective" entries. We propose Gradient Descent with Multiplicative Noise (GDMN) and Additive Noise (GDAN). These perturbations ensure that parameters continue to move, allowing them to eventually contribute to the "max" operation and improve the overall fit.

Convergence analysis of Gradient Descent variants on synthetic data.

Tropical Compression (TC)

We introduce a "mixed" factorization problem: $Y \approx A \boxplus (BX)$, where $BX$ is a standard linear matrix product and $\boxplus$ denotes the tropical product. This model, termed Tropical Compression, naturally mimics concave utility functions in economics. We solve this using a Projected Gradient Descent approach, utilizing Singular Value Decomposition (SVD) to project the intermediate tropical product back into a low-rank linear space.

Experimental Results

Optimization on Synthetic Data

The proposed algorithms were tested on randomly generated matrices to evaluate robustness. As shown in the table below, the GDAN-NZM (Non-Zero Mean Additive Noise) variant significantly outperformed both standard Gradient Descent and the state-of-the-art FastSTMF algorithm. For a noise level of $a=0.1$, GDAN-NZM achieved a Frobenius error of $0.60 \pm 0.28$, compared to $1.38 \pm 0.52$ for FastSTMF.

Comparison of Frobenius error across different algorithms and noise levels.

Recommendation Performance

On the MovieLens 1M dataset, the Tropical Compression (TC) model achieved a Hit Rate at 10 (HR@10) of 0.743. This performance exceeds that of a carefully optimized linear factorization model (0.731), demonstrating the power of combining linear feature extraction with tropical utility mapping.

Conclusion

By integrating noise-enhanced optimization and hybrid tropical-linear modeling, we significantly improve the efficacy of Matrix Factorization in non-linear domains. Future research will focus on incorporating formal regularization and scaling these methods to handle the extreme sparsity found in large-scale recommendation systems.

Summary updated

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