Compact Factorization of Matrices Using Generalized Round-Rank

Citations Over Time

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.

Related Papers

• → ILUT: A dual threshold incomplete LU factorization(1994)639 cited
• → Fine-Grained Parallel Incomplete LU Factorization(2015)179 cited
• → Incomplete WZ Factorization as an Alternative Method of Preconditioning for Solving Markov Chains(2008)7 cited
• → ThewwTfactorization of dense and sparse matrices(1995)1 cited
• → LU Methods for Solving Linear Systems(2015)