Atom Decomposition with Adaptive Basis Selection Strategy for Matrix Completion

doi:10.1145/2903716

OPT OpenIR > 光谱成像技术研究室

	Atom Decomposition with Adaptive Basis Selection Strategy for Matrix Completion
	Hu, Yao 1; Zhao, Chen 1; Cai, Deng 1; He, Xiaofei 1; Li, Xuelong2
作者部门	光学影像学习与分析中心
	2016-06-01
发表期刊	ACM TRANSACTIONS ON MULTIMEDIA COMPUTING COMMUNICATIONS AND APPLICATIONS
ISSN	1551-6857
卷号	12 期号:3
产权排序	2
摘要	Estimating missing entries in matrices has attracted much attention due to its wide range of applications like image inpainting and video denoising, which are usually considered as low-rank matrix completion problems theoretically. It is common to consider nuclear norm as a surrogate of the rank operator since it is the tightest convex lower bound of the rank operator under certain conditions. However, most approaches based on nuclear norm minimization involve a number of singular value decomposition (SVD) operations. Given a matrix X is an element of R-mxn, the time complexity of the SVD operation is O(mn(2)), which brings prohibitive computational burden on large-scale matrices, limiting the further usage of these methods in real applications. Motivated by this observation, a series of atom-decomposition-based matrix completion methods have been studied. The key to these methods is to reconstruct the target matrix by pursuit methods in a greedy way, which only involves the computation of the top SVD and has great advantages in efficiency compared with the SVD-based matrix completion methods. However, due to gradually serious accumulation errors, atom-decomposition-based methods usually result in unsatisfactory reconstruction accuracy. In this article, we propose a new efficient and scalable atom decomposition algorithm for matrix completion called Adaptive Basis Selection Strategy (ABSS). Different from traditional greedy atom decomposition methods, a two-phase strategy is conducted to generate the basis separately via different strategies according to their different nature. At first, we globally prune the basis space to eliminate the unimportant basis as much as possible and locate the probable subspace containing the most informative basis. Then, another group of basis spaces are learned to improve the recovery accuracy based on local information. In this way, our proposed algorithm breaks through the accuracy bottleneck of traditional atom-decomposition-based matrix completion methods; meanwhile, it reserves the innate efficiency advantages over SVD-based matrix completion methods. We empirically evaluate the proposed algorithm ABSS on real visual image data and large-scale recommendation datasets. Results have shown that ABSS has much better reconstruction accuracy with comparable cost to atom-decomposition-based methods. At the same time, it outperforms the state-of-the-art SVD-based matrix completion algorithms by similar or better reconstruction accuracy with enormous advantages on efficiency.
文章类型	Article
关键词	Algorithms Experimentation Matrix Completion Atom Decomposition Basis Selection
WOS标题词	Science & Technology ; Technology
DOI	10.1145/2903716
收录类别	SCI ; EI
关键词[WOS]	NUCLEAR NORM REGULARIZATION ; OPTIMIZATION ; MINIMIZATION ; ALGORITHM ; PURSUIT ; NOISE
语种	英语
WOS研究方向	Computer Science
项目资助者	National Basic Research Program of China (973 Program)(2013CB336500) ; National Nature Science Foundation of China(61222207 ; 61233011)
WOS类目	Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS记录号	WOS:000379425400009
引用统计	被引频次：8[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.opt.ac.cn/handle/181661/28173
专题	光谱成像技术研究室
作者单位	1.Zhejiang Univ, State Key Lab CAD & CG, 388 Yu Hang Tang Rd, Hangzhou 310058, Zhejiang, Peoples R China 2.Chinese Acad Sci, Ctr OPT IMagery Anal & Learning OPTIMAL, State Key Lab Transient Opt & Photon, Xian Inst Opt & Precis Mech, Xian 710119, Shaanxi, Peoples R China
推荐引用方式 GB/T 7714	Hu, Yao,Zhao, Chen,Cai, Deng,et al. Atom Decomposition with Adaptive Basis Selection Strategy for Matrix Completion[J]. ACM TRANSACTIONS ON MULTIMEDIA COMPUTING COMMUNICATIONS AND APPLICATIONS,2016,12(3).
APA	Hu, Yao,Zhao, Chen,Cai, Deng,He, Xiaofei,&Li, Xuelong.(2016).Atom Decomposition with Adaptive Basis Selection Strategy for Matrix Completion.ACM TRANSACTIONS ON MULTIMEDIA COMPUTING COMMUNICATIONS AND APPLICATIONS,12(3).
MLA	Hu, Yao,et al."Atom Decomposition with Adaptive Basis Selection Strategy for Matrix Completion".ACM TRANSACTIONS ON MULTIMEDIA COMPUTING COMMUNICATIONS AND APPLICATIONS 12.3(2016).

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
Atom Decomposition w（1801KB）	期刊论文	作者接受稿	限制开放	CC BY-NC-SA	请求全文