Title :
Matrix completion by Truncated Nuclear Norm Regularization
Author :
Debing Zhang ; Yao Hu ; Jieping Ye ; Xuelong Li ; Xiaofei He
Author_Institution :
State Key Lab. of CAD&CG, Zhejiang Univ., Hangzhou, China
Abstract :
Estimating missing values in visual data is a challenging problem in computer vision, which can be considered as a low rank matrix approximation problem. Most of the recent studies use the nuclear norm as a convex relaxation of the rank operator. However, by minimizing the nuclear norm, all the singular values are simultaneously minimized, and thus the rank can not be well approximated in practice. In this paper, we propose a novel matrix completion algorithm based on the Truncated Nuclear Norm Regularization (TNNR) by only minimizing the smallest N-r singular values, where N is the number of singular values and r is the rank of the matrix. In this way, the rank of the matrix can be better approximated than the nuclear norm. We further develop an efficient iterative procedure to solve the optimization problem by using the alternating direction method of multipliers and the accelerated proximal gradient line search method. Experimental results in a wide range of applications demonstrate the effectiveness of our proposed approach.
Keywords :
computer vision; gradient methods; matrix algebra; optimisation; search problems; TNNR; accelerated proximal gradient line search method; alternating direction method; computer vision; convex relaxation; iterative procedure; low rank matrix approximation problem; matrix completion algorithm; missing value estimation; multipliers; optimization problem; rank operator; singular value; truncated nuclear norm regularization; visual data; Acceleration; Approximation methods; Convergence; Educational institutions; Minimization; Optimization; Visualization;
Conference_Titel :
Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on
Conference_Location :
Providence, RI
Print_ISBN :
978-1-4673-1226-4
Electronic_ISBN :
1063-6919
DOI :
10.1109/CVPR.2012.6247927