CSpace
LOW-RANK MATRIX ITERATION USING POLYNOMIAL-FILTERED SUBSPACE EXTRACTION
Li, Yongfeng1; Liu, Haoyang1; Wen, Zaiwen1; Yuan, Ya-Xiang2
2020
发表期刊SIAM JOURNAL ON SCIENTIFIC COMPUTING
ISSN1064-8275
卷号42期号:3页码:A1686-A1713
摘要In this paper, we study fixed-point schemes with certain low-rank structures arising from matrix optimization problems. Traditional first-order methods depend on the eigenvalue decomposition at each iteration, which may take most of the computational time. In order to reduce the cost, we propose an inexact algorithmic framework based on a polynomial subspace extraction. The idea is to use an additional polynomial-filtered iteration to extract an approximated eigenspace and to project the iteration matrix on this subspace, followed by an optimization update. The accuracy of the extracted subspace can be controlled by the degree of the polynomial filters. This kind of subspace extraction also enjoys the warm-start property: the subspace of the current iteration is refined from the previous one. Then this framework is instantiated into two algorithms: the polynomial-filtered proximal gradient method and the polynomial-filtered alternating direction method of multipliers. The convergence of the proposed framework is guaranteed if the polynomial degree grows with an order\scrO (log k) at the kth iteration. If the warm-start property is considered, the degree can be reduced to a constant, independent of the iteration k. Preliminary numerical experiments on several matrix optimization problems show that the polynomial-filtered algorithms usually provide multifold speedups.
关键词low-rank matrix iteration eigenvalue decomposition inexact optimization method polynomial filter subspace extraction
DOI10.1137/19M1259444
收录类别SCI
语种英语
资助项目NSFC[11331012] ; NSFC[11688101]
WOS研究方向Mathematics
WOS类目Mathematics, Applied
WOS记录号WOS:000551255700014
出版者SIAM PUBLICATIONS
引用统计
文献类型期刊论文
条目标识符http://ir.amss.ac.cn/handle/2S8OKBNM/51853
专题中国科学院数学与系统科学研究院
通讯作者Li, Yongfeng
作者单位1.Peking Univ, Beijing Int Ctr Math Res, Beijing 100871, Peoples R China
2.Chinese Acad Sci, Acad Math & Syst Sci, State Key Lab Sci & Engn Comp, Beijing 100190, Peoples R China
推荐引用方式
GB/T 7714
Li, Yongfeng,Liu, Haoyang,Wen, Zaiwen,et al. LOW-RANK MATRIX ITERATION USING POLYNOMIAL-FILTERED SUBSPACE EXTRACTION[J]. SIAM JOURNAL ON SCIENTIFIC COMPUTING,2020,42(3):A1686-A1713.
APA Li, Yongfeng,Liu, Haoyang,Wen, Zaiwen,&Yuan, Ya-Xiang.(2020).LOW-RANK MATRIX ITERATION USING POLYNOMIAL-FILTERED SUBSPACE EXTRACTION.SIAM JOURNAL ON SCIENTIFIC COMPUTING,42(3),A1686-A1713.
MLA Li, Yongfeng,et al."LOW-RANK MATRIX ITERATION USING POLYNOMIAL-FILTERED SUBSPACE EXTRACTION".SIAM JOURNAL ON SCIENTIFIC COMPUTING 42.3(2020):A1686-A1713.
条目包含的文件
条目无相关文件。
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[Li, Yongfeng]的文章
[Liu, Haoyang]的文章
[Wen, Zaiwen]的文章
百度学术
百度学术中相似的文章
[Li, Yongfeng]的文章
[Liu, Haoyang]的文章
[Wen, Zaiwen]的文章
必应学术
必应学术中相似的文章
[Li, Yongfeng]的文章
[Liu, Haoyang]的文章
[Wen, Zaiwen]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

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