{
  "id": "1801.08691",
  "version": "v1",
  "published": "2018-01-26T06:49:05.000Z",
  "updated": "2018-01-26T06:49:05.000Z",
  "title": "On Quasi-Newton Forward--Backward Splitting: Proximal Calculus and Convergence",
  "authors": [
    "Stephen Becker",
    "Jalal Fadili",
    "Peter Ochs"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "We introduce a framework for quasi-Newton forward--backward splitting algorithms (proximal quasi-Newton methods) with a metric induced by diagonal $\\pm$ 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-01-26T06:49:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65K05",
      "65K10",
      "90C25",
      "90C31"
    ],
    "keywords": [
      "convergence",
      "composite convex minimization problems",
      "symmetric positive definite matrices",
      "elegant quasi-newton methods",
      "general proximal calculus"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}