Name
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1137/19M1259444 | SIAM JOURNAL ON SCIENTIFIC COMPUTING |
Keywords | DocType | Volume |
low-rank matrix iteration,eigenvalue decomposition,inexact optimization method,polynomial filter,subspace extraction | Journal | 42 |
Issue | ISSN | Citations |
3 | 1064-8275 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yongfeng Li | 1 | 0 | 0.34 |
| Haoyang Liu | 2 | 0 | 0.34 |
| Zaiwen Wen | 3 | 934 | 40.20 |
| Y. Yuan | 4 | 982 | 146.16 |