Abstract
Traditional matrix factorization assumes linear relationships, often requiring an artificially high rank to represent ordinal data like star ratings. We introduce Generalized Round-Rank (GRR), a framework that utilizes a non-linear rounding function to achieve more compact and accurate representations of discrete datasets. By modeling matrices as $Y = \text{Round}(U \times V^T)$ and optimizing latent factors and thresholds simultaneously via a smooth Multi-Sigmoid approximation, our method outperforms standard linear techniques on both synthetic and real-world recommendation benchmarks.
Introduction
Matrix factorization is a cornerstone of modern recommendation systems, typically relying on linear low-rank approximations to capture hidden patterns in user-item interactions. However, real-world data is frequently ordinal—discrete categories with a meaningful order, such as star ratings or qualitative assessments. Forcing these discrete values into linear models often necessitates a high rank to achieve a good fit, leading to inefficiencies. This research explores whether defining rank through a non-linear rounding lens can lead to more efficient and accurate data representations.
Methodology: Link-Rank Factorization
The authors propose a framework called Link-Rank Factorization. Instead of approximating a matrix $Y$ directly as $U \times V^T$, they model it as: $$Y = \text{Round}(U \times V^T)$$ Where "Round" is a Generalized Round Function (GRF) that maps continuous latent values into discrete ordinal buckets using a set of learned thresholds ($\tau$).
Optimization Strategies
Since the rounding function is non-differentiable, the authors introduce two primary optimization paths:
- Round Loss: A hinge-like loss function that penalizes the model when latent values fall outside the correct "bucket" for a given rating.
- Multi-Sigmoid Approximation: A smooth surrogate function composed of a sum of sigmoids. This allows for the use of standard Stochastic Gradient Descent (SGD) to learn both the latent factors ($U, V$) and the optimal thresholds ($\tau$) simultaneously.
The Linear Rank Gap
A key insight of this work is that linear rank often overestimates the true complexity of ordinal data. For instance, a simple identity matrix has a full linear rank of $n$, but its Generalized Round-Rank is only 2. This suggests that many seemingly complex datasets are actually simple when viewed through the right non-linear lens.
Experimental Evaluation
The proposed framework was evaluated against synthetic matrices (Identity, Upper Triangular, Band Diagonal) and real-world datasets (smallnetflix, MovieLens 100k).
Synthetic Recovery and Convergence
On structured synthetic matrices, the GRR-based models (specifically the Multi-Sigmoid and Round variants) consistently converged to near-zero error. In contrast, linear models often reached an error floor, unable to capture the underlying discrete structure regardless of training duration.
Real-World Performance
On the MovieLens 100k benchmark, the Multi-Sigmoid approach at rank $k=10$ outperformed specialized algorithms such as APG and AIS-Impute. The GRR methods showed a marked improvement in "accuracy"—defined as the percentage of predictions within $\pm 0.5$ of the true rating—confirming their ability to better model the discrete nature of user feedback.
Discussion and Conclusion
Generalized Round-Rank provides a powerful alternative to linear factorization for ordinal data. While the "Round" loss function offers theoretical purity, its optimization can be challenging due to zero-gradient regions. The Multi-Sigmoid approximation serves as a robust practical solution, though it introduces additional complexity. Future research will focus on developing convex relaxations to simplify optimization and analyzing the sample complexity required for unique solutions in the GRR framework. By moving beyond linear assumptions, GRR opens new avenues for highly compact and interpretable data compression in recommendation systems.
Summary updated