Matrix Completion via Non-Convex Relaxation and Adaptive Correlation Learning
This work addresses efficiency and accuracy issues in matrix completion for applications like recommendation systems, though it appears incremental as it builds on existing models with theoretical validation.
The paper tackles the slow convergence and limited use of prior knowledge in matrix completion by proposing a non-convex surrogate optimized via closed-form solutions, achieving convergence in dozens of iterations, and incorporating adaptive correlation learning to exploit column-wise correlations while maintaining fast convergence.
The existing matrix completion methods focus on optimizing the relaxation of rank function such as nuclear norm, Schatten-p norm, etc. They usually need many iterations to converge. Moreover, only the low-rank property of matrices is utilized in most existing models and several methods that incorporate other knowledge are quite time-consuming in practice. To address these issues, we propose a novel non-convex surrogate that can be optimized by closed-form solutions, such that it empirically converges within dozens of iterations. Besides, the optimization is parameter-free and the convergence is proved. Compared with the relaxation of rank, the surrogate is motivated by optimizing an upper-bound of rank. We theoretically validate that it is equivalent to the existing matrix completion models. Besides the low-rank assumption, we intend to exploit the column-wise correlation for matrix completion, and thus an adaptive correlation learning, which is scaling-invariant, is developed. More importantly, after incorporating the correlation learning, the model can be still solved by closed-form solutions such that it still converges fast. Experiments show the effectiveness of the non-convex surrogate and adaptive correlation learning.