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 | |
| Source Publication | SIAM JOURNAL ON SCIENTIFIC COMPUTING
 |
| ISSN | 1064-8275 |
| Volume | 42Issue:3Pages:A1686-A1713 |
| Abstract | 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. |
| Keyword | low-rank matrix iteration eigenvalue decomposition inexact optimization method polynomial filter subspace extraction |
| DOI | 10.1137/19M1259444 |
| Indexed By | SCI |
| Language | 英语 |
| Funding Project | NSFC[11331012] ; NSFC[11688101] |
| WOS Research Area | Mathematics |
| WOS Subject | Mathematics, Applied |
| WOS ID | WOS:000551255700014 |
| Publisher | SIAM PUBLICATIONS |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/51853 |
| Collection | 中国科学院数学与系统科学研究院 |
| Corresponding Author | Li, Yongfeng |
| Affiliation | 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 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment