A Scalable And Feasible Matrix Completion Using Random Projection

Matrix completion is to recover the missing entries based on the observed ones.And it has been widely used in the in many machine learning applications such as collaborative filtering and recommendation systems,where the data is usually represented as a matrix.Moreover,such a data matrix has a low-rank property.However,the matrix is incomplete with lots of missing entries,yielding the problem of matrix completion.For example,in recommendation systems(e.g.,MovieLens),there are some ratings of the movies made by some users.Then matrix completion techniques are used to predict the ratings of a movie for users and recommend movies that people may be interested in based on the data observed.Taking the low rank property of matrix completion into consideration,the matrix completion problem is a rank minmization problem which is NP-hard.So the problem is usually relaxed into a matrix nuclear norm minimization,which is always calculated iteratively including doing singular value decomposition(SVD).However,it is limited in use in large-scale matrices due to the high computational complexity of singular value decomposition(SVD).In this paper we introduce random projection to handle this limitation.In particular,we use a randomized SVD to accelerate the classical Soft-Impute algorithm for the matrix completion problem.Moreover,we present analysis for time complexity of our approach.The empirical results on two typical recommendation data sets: Jester and MovieLens,show that our approach is more efficient while achieving a better performance.