Fast Low Rank Matrix Completion Methods Based On Weighted Residual Error And Matrix Factorization

Low rank matrix completion aims at recovering an incomplete matrix from a small subset of its entries and has attracted a great deal of attention in the research area of machine learning.Most popular matrix completion methods can be categoried into two classes:methods based on nuclear norm or weighted nuclear norm and methods based on matrix factorization.The methods in the first class,such as Truncated Nuclear Norm Regularization?TNNR?and Iteratively Reweighted Nclear Norm minimization?IRNN?,always have high accuracy but low efficiency,because of the large number of Singular Value Decomposition?SVD?iterations.The methods in the second class,such as Low rank Matrix Fatrix Fitting?LMaFit?,Fast matrix Tri-Factorization based method?FTF?and Matrix Bi-Factorization based method?MBF?,can obtain convergence rapidly.However,they are always not as accurate as the former ones.Therefore,it is necessary to investigate matrix completion methods which can take both advantages of convergence accuracy and convergence speed.Our work mainly includes the following parts:?1?In order to reduce the iteration number of the TNNR method,a Truncated Nuclear Norm Regularization method based on Weighted Residual Error for matrix completion?TNNR-WRE?and an extention method?ETNNR-WRE?are proposed.By arranging differents weights to the rows of a residual error matrix and recovering the rows with more observed entries with higher accuracies,TNNR-WRE and ETNNR-WRE can recover the original incomplete matrix very fast.Compared with TNNR-WRE,ETNNR-WRE is much more robust to its parameters.?2?In order to investigate fast and accurate SVD free matrix completion methods,a method of computing an approximate SVD of a matrix by QR decomposition is proposed first,which is called CSVD-QR.This method can compute the largest r?r>0?singular values and the corresponding vectors by QR decomposition iteratively.Then,a QR decomposition and L_2,1 Norm Minimization based method for fast matrix completion?LNM-QR?is proposed.Under the framework of matrix tri-factorization,LNM-QR can make use of the output of CSVD-QR with one iteration to recover the missing entries.Thus,this method is much faster than the traditional methods.To improve the accuracy of LNM-QR,a QR decomposition and Iteratively Reweighted L_2,1 Norm Minimization method is proposed,which can be called IRLNM-QR.Theoreatical analyses and sufficient experiment results show that IRLNM-QR can converge as accurately as an iteratively reweighted nuclear norm minimization method.?3?Motivated by the IRLNM-QR method,an Iteratively Reweighted L_2,1 Norm Minimization method based on Matrix Bi-Factorization is proposed for fast and accurate matrix completion,which is called MBF-IRLNM.This method can use QR decomposition to extract the orthogonal basis of columns of a matrix first.Then,it recovers the missing entries by optimizing an iteratively reweighted L_2,1 norm minimization problem.Compared with IRLNM-QR,the MBF-IRLN method shows much better convergence speed.The reason is that there is only one time of QR decomposition at each iteration of MBF-IRLN,while there are two times of QR decomposition at each iteration of IRLNM-QR.Theoreatical analyses show that MBF-IRLN can converge as accurately as the IRNN method.?4?The ETNNR-WRE method has much better paratemeter robustness,iteration number and convergence accuracy than TNNR method.However,ETNNR-WRE is much slower than matrix factorization based methods,because it is still a SVD based method.Motivated by MBF-IRLN,a Weighted Residual Error and Truncated L_2,1 Norm minimization based matrix completion method is proposed,which is called TLN-WRE.Under the framework of matrix bi-factorization,a truncated L_2,1 norm with weighted residual error minimization is applied to matrix completion tasks.In TLN-WRE,the optimal solution is searched in the direction computed by QR decomposition.Sufficient experiment results show that TLN-WRE can converge as accurately as TNNR-WRE and can converge faster than TNNR-WRE.