Welcome to the homepage of the

Mathematical Optimization for Data Science Group

Department of Mathematics and Computer Science, Saarland University, Germany

On Quasi-Newton Forward--Backward Splitting: Proximal Calculus and Convergence

S. Becker, J. Fadili and P. Ochs

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 piece-wise 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 state-of-the-art. The algorithm has extensive applications including signal processing, sparse recovery, machine learning and classification to name a few.
pdf Bibtex Publisher's link arXiv Code
Latest update: 22.11.2018
Citation:
S. Becker, J. Fadili, P. Ochs:
On Quasi-Newton Forward--Backward Splitting: Proximal Calculus and Convergence. [pdf]
SIAM Journal on Optimization, 29(4):2445-2481, 2019.
Bibtex:
@article{BFO19,
  title        = {On Quasi-Newton Forward--Backward Splitting: Proximal Calculus and Convergence},
  author       = {S. Becker and J. Fadili and P. Ochs},
  year         = {2019},
  journal      = {SIAM Journal on Optimization},
  number       = {4},
  volume       = {29},
  pages        = {2445--2481}
}


MOP Group
©2017-2024
The author is not
responsible for
the content of
external pages.