Abstract In this paper we focus on the greedy matrix completion problem. A simple atom selection strategy is proposed to find the optimal atom in each iteration by alternating minimization. Based on this per-iteration strategy, we devise a greedy algorithm and establish an upper bound of the approximating error. To evaluate different weight refinement methods, several variants are designed. We prove that our algorithm and three of its variants have the property of linear convergence. Experiments of Recommendation and Image Recovery are conducted to make empirical evaluation with promising results. The proposed algorithm takes only 700 seconds to process Yahoo Music dataset in PC, and achieves a root mean square error 24.5 on the test set.