Exemplar-based large-scale low-rank matrix decomposition for collaborative prediction

Abstract

Recommender system is one of the most effective tools to solve the problem of information overload. As a popular method for recommendation system, regularized singular value decomposition (RSVD) has the advantage of prediction accuracy. However, with the growing of the size of rating matrix A, RSVD suffers from both ‘out of memory’ and high computational cost. To alleviate these disadvantages, we utilize CUR decomposition approach to reduce the memory consumption before RSVD is applied. Additionally, the rating matrix A often is sparse, so we propose a novel column sampling algorithm and sparseness measure to solve the data sparse problem. The main computation cost in the original RSVD is to compute $M^{T}N$ and $M{N}^T$ respectively. While replacing N by CUR or C in RSVD, we can reduce the computational cost from $O(m^{2}n)$ to $O(c^{2}m+tcn{k}_c)$ (where c is the size of data subspace, m and n are the size of the input matrix, t is the number of iterations, $k_c$ is the number of features). Because CUR is explicitly expressed in terms of a small number of actual columns and actual rows of the original data matrix, the result of matrix decomposition has better interpretability. The advantage of what we devised CUR+RSVD and C+RSVD collaborative prediction approaches is that, they not only can deal with the large scale matrix rapidly but also preserve the sparsity of the original matrix, more interestingly, our approaches have higher prediction accuracy. Experimental results on Movielens, Joke data set, etc. show that what we proposed methods can handle the sparsity issue on large-scale low-rank matrix effectively. Compared with RSVD, it can achieve far better prediction accuracy and recommendation result, meanwhile save about 70% training time at the same dataset.

Keywords:

• CUR matrix decomposition
• product recommendation
• regularized singular value decomposition
• interpretability
• row column sampling

2010 Mathematics Subject Classification:

• 15A09

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported in part by the Natural Science Foundation of China [grant numbers 62273290, 61572419, 62072391], Natural Science Foundation of Shandong Province [grant number ZR2020MF148], Science and Technology Planning Project of Nanshan Group [grant number 2022-6-13].