LOW-RANK MATRIX ITERATION USING POLYNOMIAL-FILTERED SUBSPACE EXTRACTION
文献类型：期刊论文
| 作者 | Li, Yongfeng1; Liu, Haoyang1; Wen, Zaiwen1; Yuan, Ya-Xiang2 |
| 刊名 | SIAM JOURNAL ON SCIENTIFIC COMPUTING
 |
| 出版日期 | 2020 |
| 卷号 | 42期号:3页码:A1686-A1713 |
| 关键词 | low-rank matrix iteration eigenvalue decomposition inexact optimization method polynomial filter subspace extraction |
| ISSN号 | 1064-8275 |
| DOI | 10.1137/19M1259444 |
| 英文摘要 | 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. |
| 资助项目 | NSFC[11331012] ; NSFC[11688101] |
| WOS研究方向 | Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000551255700014 |
| 出版者 | SIAM PUBLICATIONS |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/51852]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。