UC Irvine

Matrix factorization is a popular machine learning technique, with applications in variety of domains, such as recommendation systems [16, 28], natural language processing [26], and computer vision [10]. Due to this widespread use of these models, there has been considerable theoretical analysis of the various properties of low-rank approximations of real-valued matrices, including approximation rank [1, 5] and sample complexity [2].

Rather than assume real-valued data, a number of studies (particularly ones on practical applications) focus on more specific data types, such as binary data [23], integer data [17], and ordinal data [12, 30]. For such matrices, existing approaches have used different link functions, applied in an element-wise manner to the low-rank representation [21], i.e. the output Y is ψ(U^TV) instead of the conventional U^TV. These link functions have been justified from a probabilistic point of view [4, 27], and have provided considerable success in empirical settings. However, theoretical results for linear factorization do not apply here, and thus the expressive power of the factorization models with non-linear link functions is not clear, and neither is the relation of the rank of a matrix to the link function used.

In this work, we first define a generalized notion of rank based on the link function ψ, as the rank of a latent matrix before the link function is applied. We focus on a link function that applies to factorization of integer-valued matrices: the generalized round function (GRF), and define the corresponding generalized round-rank (GRR). After providing background on GRR, we show that there are many low-GRR matrices that are full rank [1]. Moreover, we also study the approximation limitations of linear rank, by showing, for example, that low GRR matrices often cannot be approximated by low-rank linear matrices. We define uniqueness for GRR-based matrix completion, and derive its necessary and sufficient conditions. These properties demonstrate that many full linear-rank matrices can be factorized using low-rank matrices if an appropriate link function is used.

We also present an empirical evaluation of factorization with different link functions for matrix reconstruction and completion. We show that using link functions is efficient compared to linear rank, in that gradient-based optimization approach learns more accurate reconstructions using a lower rank representation and fewer training samples. We also perform experiments on matrix completion on two recommendation datasets, and demonstrate that appropriate link function outperform linear factorization, thus can play a crucial role in accurate matrix completion.