AN EFFICIENT GAUSS-NEWTON ALGORITHM FOR SYMMETRIC LOW-RANK PRODUCT MATRIX APPROXIMATIONS

doi:10.1137/140971464

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 计算数学与科学工程计算研究所

	AN EFFICIENT GAUSS-NEWTON ALGORITHM FOR SYMMETRIC LOW-RANK PRODUCT MATRIX APPROXIMATIONS
	Liu, Xin1 ; Wen, Zaiwen 2; Zhang, Yin 3
刊名	SIAM JOURNAL ON OPTIMIZATION
	2015
卷号	25 期号:3 页码:1571-1608
关键词	eigenvalue decomposition singular value decomposition low-rank product matrix approximation Gauss-Newton methods
ISSN号	1052-6234
DOI	10.1137/140971464
英文摘要	We derive and study a Gauss-Newton method for computing a symmetric low-rank product XXT, where X is an element of R-nxk for k < n, that is the closest to a given symmetric matrix A is an element of R-nxn in Frobenius norm. When A = (BB)-B-T (or BBT), this problem essentially reduces to finding a truncated singular value decomposition of B. Our Gauss-Newton method, which has a particularly simple form, shares the same order of iteration-complexity as a gradient method when k << n, but can be significantly faster on a wide range of problems. In this paper, we prove global convergence and a Q-linear convergence rate for this algorithm and perform numerical experiments on various test problems, including those from recently active areas of matrix completion and robust principal component analysis. Numerical results show that the proposed algorithm is capable of providing considerable speed advantages over Krylov subspace methods on suitable application problems where high-accuracy solutions are not required. Moreover, the algorithm possesses a higher degree of concurrency than Krylov subspace methods, thus offering better scalability on modern multi-/many-core computers.
资助项目	NSFC[11101409] ; NSFC[11331012] ; NSFC[91330115] ; NSFC[11322109] ; NSFC[91330202] ; NSFC[DMS-1115950] ; National Center for Mathematics and Interdisciplinary Sciences, CAS ; National Basic Research Project[2015CB856000] ; ONR grant[N00014-08-1-1101]
WOS研究方向	Mathematics
语种	英语
出版者	SIAM PUBLICATIONS
WOS记录号	WOS:000362418100015
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/20925]
专题	计算数学与科学工程计算研究所
通讯作者	Liu, Xin
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, State Key Lab Sci & Engn Comp, Beijing 100864, Peoples R China 2.Peking Univ, Beijing Int Ctr Math Res, Beijing 100871, Peoples R China 3.Rice Univ, Dept Computat & Appl Math, Houston, TX 77005 USA
推荐引用方式 GB/T 7714	Liu, Xin,Wen, Zaiwen,Zhang, Yin. AN EFFICIENT GAUSS-NEWTON ALGORITHM FOR SYMMETRIC LOW-RANK PRODUCT MATRIX APPROXIMATIONS[J]. SIAM JOURNAL ON OPTIMIZATION,2015,25(3):1571-1608.
APA	Liu, Xin,Wen, Zaiwen,&Zhang, Yin.(2015).AN EFFICIENT GAUSS-NEWTON ALGORITHM FOR SYMMETRIC LOW-RANK PRODUCT MATRIX APPROXIMATIONS.SIAM JOURNAL ON OPTIMIZATION,25(3),1571-1608.
MLA	Liu, Xin,et al."AN EFFICIENT GAUSS-NEWTON ALGORITHM FOR SYMMETRIC LOW-RANK PRODUCT MATRIX APPROXIMATIONS".SIAM JOURNAL ON OPTIMIZATION 25.3(2015):1571-1608.