Orthogonal Rank-One Matrix Pursuit for Low Rank Matrix Completion
Preprint
Abstract
In this paper, we propose an efficient and scalable low rank matrix completion algorithm. The key idea is to extend orthogonal matching pursuit method from the vector case to the matrix case. We further propose an economic version of our algorithm by introducing a novel weight updating rule to reduce the time and storage complexity. Both versions are computationally inexpensive for each matrix pursuit iteration, and find satisfactory results in a few iterations. Another advantage of our proposed algorithm is that it has only one tunable parameter, which is the rank. It is easy to understand and to use by the user. This becomes especially important in large-scale learning problems. In addition, we rigorously show that both versions achieve a linear convergence rate, which is significantly better than the previous known results. We also empirically compare the proposed algorithms with several state-of-the-art matrix completion algorithms on many real-world datasets, including the large-scale recommendation dataset Netflix as well as the MovieLens datasets. Numerical results show that our proposed algorithm is more efficient than competing algorithms while achieving similar or better prediction performance.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Penalty decomposition methods for rank minimizationOptimization Methods and Software, 2014
- Parallel stochastic gradient algorithms for large-scale matrix completionMathematical Programming Computation, 2013
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithmMathematical Programming Computation, 2012
- An implementable proximal point algorithmic framework for nuclear norm minimizationMathematical Programming, 2011
- Matrix Factorization Techniques for Recommender SystemsComputer, 2009
- A coordinate gradient descent method for ℓ 1-regularized convex minimizationComputational Optimization and Applications, 2009
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samplesApplied and Computational Harmonic Analysis, 2009
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Scope of validity of PSNR in image/video quality assessmentElectronics Letters, 2008
- Eigentaste: A Constant Time Collaborative Filtering AlgorithmInformation Retrieval Journal, 2001