Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization

CORC > 西安光学精密机械研究所 > 中国科学院西安光学精密机械研究所 > 光学影像学习与分析中心

	Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization
	Hu, Yao 1; Zhang, Debing 1; Ye, Jieping 2,3; Li, Xuelong4 ; He, Xiaofei 1
刊名	ieee transactions on pattern analysis and machine intelligence
	2013-09-01
卷号	35 期号:9 页码:2117-2130
关键词	Matrix completion nuclear norm minimization alternating direction method of multipliers accelerated proximal gradient method
英文摘要	recovering a large matrix from a small subset of its entries is a challenging problem arising in many real applications, such as image inpainting and recommender systems. many existing approaches formulate this problem as a general low-rank matrix approximation problem. since the rank operator is nonconvex and discontinuous, most of the recent theoretical studies use the nuclear norm as a convex relaxation. one major limitation of the existing approaches based on nuclear norm minimization is that all the singular values are simultaneously minimized, and thus the rank may not be well approximated in practice. in this paper, we propose to achieve a better approximation to the rank of matrix by truncated nuclear norm, which is given by the nuclear norm subtracted by the sum of the largest few singular values. in addition, we develop a novel matrix completion algorithm by minimizing the truncated nuclear norm. we further develop three efficient iterative procedures, tnnr-admm, tnnr-apgl, and tnnr-admmap, to solve the optimization problem. tnnr-admm utilizes the alternating direction method of multipliers (admm), while tnnr-agpl applies the accelerated proximal gradient line search method (apgl) for the final optimization. for tnnr-admmap, we make use of an adaptive penalty according to a novel update rule for admm to achieve a faster convergence rate. our empirical study shows encouraging results of the proposed algorithms in comparison to the state-of-the-art matrix completion algorithms on both synthetic and real visual datasets.
WOS标题词	science & technology ; technology
类目[WOS]	computer science, artificial intelligence ; engineering, electrical & electronic
研究领域[WOS]	computer science ; engineering
关键词[WOS]	alternating direction method ; low-rank ; thresholding algorithm ; minimization ; entries
收录类别	SCI ; EI
语种	英语
WOS记录号	WOS:000322029000006
公开日期	2015-06-30
内容类型	期刊论文
源URL	[http://ir.opt.ac.cn/handle/181661/23452]
专题	西安光学精密机械研究所_光学影像学习与分析中心
作者单位	1.Zhejiang Univ, Coll Comp Sci, State Key Lab CAD&CG, Hangzhou 310058, Zhejiang, Peoples R China 2.Arizona State Univ, Dept Comp Sci & Engn, Tempe, AZ 85287 USA 3.Arizona State Univ, Ctr Evolutionary Med & Informat, Biodesign Inst, Tempe, AZ 85287 USA 4.Chinese Acad Sci, Xian Inst Opt & Precis Mech, State Key Lab Transicent Opt & Photon, Ctr Opt IMagery Anal & Learning OPTIMAL, Xian 710119, Shaanxi, Peoples R China
推荐引用方式 GB/T 7714	Hu, Yao,Zhang, Debing,Ye, Jieping,et al. Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization[J]. ieee transactions on pattern analysis and machine intelligence,2013,35(9):2117-2130.
APA	Hu, Yao,Zhang, Debing,Ye, Jieping,Li, Xuelong,&He, Xiaofei.(2013).Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization.ieee transactions on pattern analysis and machine intelligence,35(9),2117-2130.
MLA	Hu, Yao,et al."Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization".ieee transactions on pattern analysis and machine intelligence 35.9(2013):2117-2130.