Low-rank approximation pursuit for matrix completion

We consider the matrix completion problem that aims to construct a low rank matrix X that approximates a given large matrix Y from partially known sample data in Y. In this paper we introduce an efficient greedy algorithm for such matrix completions. The greedy algorithm generalizes the orthogonal rank-one matrix pursuit method (OR1MP) by creating s⩾1 candidates per iteration by low-rank matrix approximation. Due to selecting s⩾1 candidates in each iteration step, our approach uses fewer iterations than OR1MP to achieve the same results. Our algorithm is a randomized low-rank approximation method which makes it computationally inexpensive. The algorithm comes in two forms, the standard one which uses the Lanzcos algorithm to find partial SVDs, and another that uses a randomized approach for this part of its work. The storage complexity of this algorithm can be reduced by using an weight updating rule as an economic version algorithm. We prove that all our algorithms are linearly convergent. Numerical experiments on image reconstruction and recommendation problems are included that illustrate the accuracy and efficiency of our algorithms.