A fast automatic low-rank determination algorithm for noisy matrix completion

Rank estimation is an important factor for low-rank based matrix completion, and most works devoted to this problem have considered the minimization of nuclear norm instead of matrix rank. However, when nuclear norm minimization shifts to `regularization´ due to noise, it is difficult to estimate original matrix rank, precisely. In present paper, we propose a new fast algorithm to precisely estimate matrix rank and perform completion without using nuclear norm. In our extensive experiments, the proposed algorithm significantly outperformed nuclear-norm based method for accuracy, especially and Incremental OptSpace regarding computational time. Our model selection scheme has many promising extensions for constrained matrix factorizations and tensor decompositions, and these extensions could be useful for wide range of practical applications.