Abstract | ||
---|---|---|
We introduce a framework for quasi-Newton forward-backward splitting algorithms (proximal quasi-Newton methods) with a metric induced by diagonal +/- rank-r symmetric positive definite matrices. This special type of metric allows for a highly efficient evaluation of the proximal mapping. The key to this efficiency is a general proximal calculus in the new metric. By using duality, formulas are derived that relate the proximal mapping in a rank-r modified metric to the original metric. We also describe efficient implementations of the proximity calculation for a large class of functions; the implementations exploit the piecewise linear nature of the dual problem. Then, we apply these results to acceleration of composite convex minimization problems, which leads to elegant quasi-Newton methods for which we prove convergence. The algorithm is tested on several numerical examples and compared to a comprehensive list of alternatives in the literature. Our quasi-Newton splitting algorithm with the prescribed metric compares favorably against the state of the art. The algorithm has extensive applications including signal processing, sparse recovery, machine learning, and classification to name a few. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1137/18M1167152 | SIAM JOURNAL ON OPTIMIZATION |
Keywords | Field | DocType |
forward-backward splitting,quasi-Newton,proximal calculus,duality | Convergence (routing),Diagonal,Discrete mathematics,Matrix (mathematics),Positive-definite matrix,Pure mathematics,Duality (optimization),Mathematics | Journal |
Volume | Issue | ISSN |
29 | 4 | 1052-6234 |
Citations | PageRank | References |
1 | 0.35 | 24 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
stephen becker | 1 | 47 | 8.04 |
Jalal Fadili | 2 | 1184 | 80.08 |
Peter Ochs | 3 | 182 | 9.43 |