KMS Of Academy of mathematics and systems sciences, CAS
LOW-RANK MATRIX ITERATION USING POLYNOMIAL-FILTERED SUBSPACE EXTRACTION | |
Li, Yongfeng1; Liu, Haoyang1; Wen, Zaiwen1; Yuan, Ya-Xiang2 | |
2020 | |
发表期刊 | SIAM JOURNAL ON SCIENTIFIC COMPUTING |
ISSN | 1064-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 |
DOI | 10.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. |
条目包含的文件 | 条目无相关文件。 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论