Orthogonal Rank-One Matrix Pursuit for Low Rank Matrix Completion
  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.
