Compact Factorization of Matrices Using Generalized Round-Rank

Pouya Pezeshkpour, Carlos Guestrin, Sameer SingharXiv 2018 · arXiv

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.

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:

  1. Round Loss: A hinge-like loss function that penalizes the model when latent values fall outside the correct "bucket" for a given rating.
  2. 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.

Figure 1: Comparison of linear approximation error across different matrix structures as a function of relative rank (k/n). Linear models struggle to efficiently represent these ordinal structures.

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.

Figure 5: Training convergence for (a) Random, (b) Upper Triangle, and (c) Band Diagonal matrices. The Round and Multi-Sigmoid methods achieve near-zero error, significantly outperforming the linear baseline.

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

Abstract

Matrix factorization is a well-studied task in machine learning for compactly representing large, noisy data. In our approach, instead of using the traditional concept of matrix rank, we define a new notion of link-rank based on a non-linear link function used within factorization. In particular, by applying the round function on a factorization to obtain ordinal-valued matrices, we introduce generalized round-rank (GRR). We show that not only are there many full-rank matrices that are low GRR, but further, that these matrices cannot be approximated well by low-rank linear factorization. We provide uniqueness conditions of this formulation and provide gradient descent-based algorithms. Finally, we present experiments on real-world datasets to demonstrate that the GRR-based factorization is significantly more accurate than linear factorization, while converging faster and using lower rank representations.
BibTeX
@misc{pezeshkpour2018compact,
  author = {Pouya Pezeshkpour and Carlos Guestrin and Sameer Singh},
  title = {{Compact Factorization of Matrices Using Generalized Round-Rank}},
  year = {2018},
  eprint = {1805.00184},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.00184},
}
Figure