CSpace  > 计算数学与科学工程计算研究所
AN EFFICIENT GAUSS-NEWTON ALGORITHM FOR SYMMETRIC LOW-RANK PRODUCT MATRIX APPROXIMATIONS
Liu, Xin1; Wen, Zaiwen2; Zhang, Yin3
2015
Source PublicationSIAM JOURNAL ON OPTIMIZATION
ISSN1052-6234
Volume25Issue:3Pages:1571-1608
AbstractWe 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.
Keywordeigenvalue decomposition singular value decomposition low-rank product matrix approximation Gauss-Newton methods
DOI10.1137/140971464
Language英语
Funding ProjectNSFC[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 Research AreaMathematics
WOS SubjectMathematics, Applied
WOS IDWOS:000362418100015
PublisherSIAM PUBLICATIONS
Citation statistics
Cited Times:10[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/20926
Collection计算数学与科学工程计算研究所
Affiliation1.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
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Liu, Xin]'s Articles
[Wen, Zaiwen]'s Articles
[Zhang, Yin]'s Articles
Baidu academic
Similar articles in Baidu academic
[Liu, Xin]'s Articles
[Wen, Zaiwen]'s Articles
[Zhang, Yin]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Liu, Xin]'s Articles
[Wen, Zaiwen]'s Articles
[Zhang, Yin]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.