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.
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.
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