Low-rank matrix recovery via efficient schatten p-norm minimization

As an emerging machine learning and information re-trieval technique, the matrix completion has been suc-cessfully applied to solve many scientific applications, such as collaborative prediction in information retrieval, video completion in computer vision, etc. The matrix completion is to recover a low-rank matrix with a frac-tion of its entries arbitrarily corrupted. Instead of solv-ing the popularly used trace norm or nuclear norm based objective, we directly minimize the original formula-tions of trace norm and rank norm. We propose a novel Schatten p-Norm optimization framework that unifies different norm formulations. An efficient algorithm is derived to solve the new objective and followed by the rigorous theoretical proof on the convergence. The pre-vious main solution strategy for this problem requires computing singular value decompositions- a task that requires increasingly cost as matrix sizes and rank in-crease. Our algorithm has closed form solution in each iteration, hence it converges fast. As a consequence, our algorithm has the capacity of solving large-scale matrix completion problems. Empirical studies on the recom-mendation system data sets demonstrate the promising performance of our new optimization framework and ef-ficient algorithm