QQ客服 官方微博 反馈留言

	Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition
	Wang, Shusen ; Zhang, Zhihua ; Zhang, Tong
	2016
关键词	Kernel approximation matrix factorization the Nystrom method CUR matrix decomposition NYSTROM METHOD ALGORITHMS
英文摘要	Symmetric positive semi-definite (SPSD) matrix approximation methods have been extensively used to speed up large-scale eigenvalue computation and kernel learning methods. The standard sketch based method, which we call the prototype model, produces relatively accurate approximations, but is inefficient on large square matrices. The Nystrom method is highly efficient, but can only achieve low accuracy. In this paper we propose a novel model that we call the fast SPSD matrix approximation model. The fast model is nearly as efficient as the Nystrom method and as accurate as the prototype model. We show that the fast model can potentially solve eigenvalue problems and kernel learning problems in linear time with respect to the matrix size n to achieve 1 + epsilon relative-error, whereas both the prototype model and the Nystrom method cost at least quadratic time to attain comparable error bound. Empirical comparisons among the prototype model, the Nystrom method, and our fast model demonstrate the superiority of the fast model. We also contribute new understandings of the Nystrom method. The Nystrom method is a special instance of our fast model and is approximation to the prototype model. Our technique can be straightforwardly applied to make the CUR matrix decomposition more efficiently computed without much affecting the accuracy.; Cray Inc.; Defense Advanced Research Projects Agency; National Science Foundation; Baidu Scholarship; National Natural Science Foundation of China [61572017]; MSRA Collaborative Research Grant awards; NSF [IIS-1250985, IIS-1407939, R01AI116744]; SCI(E); ARTICLE; shusen@berkeley.edu; zhzhang@math.pku.edu.cn; tzhang@stat.rutgers.edu; 17
语种	英语
出处	SCI
出版者	JOURNAL OF MACHINE LEARNING RESEARCH
内容类型	其他
源URL	[http://hdl.handle.net/20.500.11897/459069]
专题	数学科学学院
推荐引用方式 GB/T 7714	Wang, Shusen,Zhang, Zhihua,Zhang, Tong. Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition. 2016-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。