Non-smooth Non-convex Bregman Minimization: Unification and New Algorithms View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-12-06

AUTHORS

Peter Ochs, Jalal Fadili, Thomas Brox

ABSTRACT

We propose a unifying algorithm for non-smooth non-convex optimization. The algorithm approximates the objective function by a convex model function and finds an approximate (Bregman) proximal point of the convex model. This approximate minimizer of the model function yields a descent direction, along which the next iterate is found. Complemented with an Armijo-like line search strategy, we obtain a flexible algorithm for which we prove (subsequential) convergence to a stationary point under weak assumptions on the growth of the model function error. Special instances of the algorithm with a Euclidean distance function are, for example, gradient descent, forward–backward splitting, ProxDescent, without the common requirement of a “Lipschitz continuous gradient”. In addition, we consider a broad class of Bregman distance functions (generated by Legendre functions), replacing the Euclidean distance. The algorithm has a wide range of applications including many linear and nonlinear inverse problems in signal/image processing and machine learning. More... »

PAGES

244-278

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10957-018-01452-0

DOI

http://dx.doi.org/10.1007/s10957-018-01452-0

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1110421886


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Saarland University, Saarbr\u00fccken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.11749.3a", 
          "name": [
            "Saarland University, Saarbr\u00fccken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ochs", 
        "givenName": "Peter", 
        "id": "sg:person.011151475055.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011151475055.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Normandie Universit\u00e9 ENSICAEN, CNRS, GREYC, Caen, France", 
          "id": "http://www.grid.ac/institutes/grid.463910.9", 
          "name": [
            "Normandie Universit\u00e9 ENSICAEN, CNRS, GREYC, Caen, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Fadili", 
        "givenName": "Jalal", 
        "id": "sg:person.015176300477.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015176300477.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Freiburg, Freiburg, Germany", 
          "id": "http://www.grid.ac/institutes/grid.5963.9", 
          "name": [
            "University of Freiburg, Freiburg, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brox", 
        "givenName": "Thomas", 
        "id": "sg:person.012443225372.65", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012443225372.65"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s10957-013-0391-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012342771", 
          "https://doi.org/10.1007/s10957-013-0391-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-015-0943-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046288093", 
          "https://doi.org/10.1007/s10107-015-0943-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10013-016-0238-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1074240182", 
          "https://doi.org/10.1007/s10013-016-0238-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/b:jmiv.0000011320.81911.38", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003031106", 
          "https://doi.org/10.1023/b:jmiv.0000011320.81911.38"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4419-9467-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044558790", 
          "https://doi.org/10.1007/978-1-4419-9467-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02431-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008570186", 
          "https://doi.org/10.1007/978-3-642-02431-3"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s11228-010-0147-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032025040", 
          "https://doi.org/10.1007/s11228-010-0147-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/44565", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052721759", 
          "https://doi.org/10.1038/44565"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4419-8853-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049823794", 
          "https://doi.org/10.1007/978-1-4419-8853-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-011-0484-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053470670", 
          "https://doi.org/10.1007/s10107-011-0484-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10107-013-0701-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012159026", 
          "https://doi.org/10.1007/s10107-013-0701-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00938486", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009261784", 
          "https://doi.org/10.1007/bf00938486"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-12-06", 
    "datePublishedReg": "2018-12-06", 
    "description": "We propose a unifying algorithm for non-smooth non-convex optimization. The algorithm approximates the objective function by a convex model function and finds an approximate (Bregman) proximal point of the convex model. This approximate minimizer of the model function yields a descent direction, along which the next iterate is found. Complemented with an Armijo-like line search strategy, we obtain a flexible algorithm for which we prove (subsequential) convergence to a stationary point under weak assumptions on the growth of the model function error. Special instances of the algorithm with a Euclidean distance function are, for example, gradient descent, forward\u2013backward splitting, ProxDescent, without the common requirement of a \u201cLipschitz continuous gradient\u201d. In addition, we consider a broad class of Bregman distance functions (generated by Legendre functions), replacing the Euclidean distance. The algorithm has a wide range of applications including many linear and nonlinear inverse problems in signal/image processing and machine learning.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s10957-018-01452-0", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1044187", 
        "issn": [
          "0022-3239", 
          "1573-2878"
        ], 
        "name": "Journal of Optimization Theory and Applications", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "181"
      }
    ], 
    "keywords": [
      "non-smooth non-convex optimization", 
      "approximate proximal points", 
      "Lipschitz continuous gradient", 
      "nonlinear inverse problem", 
      "non-convex optimization", 
      "signal/image processing", 
      "line search strategy", 
      "Bregman distance function", 
      "next iterate", 
      "model function", 
      "approximate minimizer", 
      "distance function", 
      "backward splitting", 
      "descent direction", 
      "convex model", 
      "inverse problem", 
      "Euclidean distance function", 
      "unifying algorithm", 
      "weak assumptions", 
      "stationary points", 
      "objective function", 
      "broad class", 
      "special instances", 
      "gradient descent", 
      "function errors", 
      "new algorithm", 
      "flexible algorithm", 
      "proximal point", 
      "continuous gradient", 
      "algorithm", 
      "iterates", 
      "Euclidean distance", 
      "minimizers", 
      "machine learning", 
      "convergence", 
      "optimization", 
      "function", 
      "wide range", 
      "image processing", 
      "point", 
      "problem", 
      "assumption", 
      "error", 
      "class", 
      "unification", 
      "search strategy", 
      "common requirement", 
      "splitting", 
      "model", 
      "applications", 
      "descent", 
      "gradient", 
      "direction", 
      "instances", 
      "distance", 
      "range", 
      "processing", 
      "requirements", 
      "learning", 
      "addition", 
      "strategies", 
      "growth", 
      "example"
    ], 
    "name": "Non-smooth Non-convex Bregman Minimization: Unification and New Algorithms", 
    "pagination": "244-278", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1110421886"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10957-018-01452-0"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10957-018-01452-0", 
      "https://app.dimensions.ai/details/publication/pub.1110421886"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:44", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_767.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s10957-018-01452-0"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10957-018-01452-0'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10957-018-01452-0'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10957-018-01452-0'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10957-018-01452-0'


 

This table displays all metadata directly associated to this object as RDF triples.

188 TRIPLES      21 PREDICATES      99 URIs      79 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10957-018-01452-0 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N8fa3d9b174a74f8a83894cda1635a76a
4 schema:citation sg:pub.10.1007/978-1-4419-8853-9
5 sg:pub.10.1007/978-1-4419-9467-7
6 sg:pub.10.1007/978-3-642-02431-3
7 sg:pub.10.1007/bf00938486
8 sg:pub.10.1007/s10013-016-0238-3
9 sg:pub.10.1007/s10107-011-0484-9
10 sg:pub.10.1007/s10107-013-0701-9
11 sg:pub.10.1007/s10107-015-0943-9
12 sg:pub.10.1007/s10957-013-0391-8
13 sg:pub.10.1007/s11228-010-0147-7
14 sg:pub.10.1023/b:jmiv.0000011320.81911.38
15 sg:pub.10.1038/44565
16 schema:datePublished 2018-12-06
17 schema:datePublishedReg 2018-12-06
18 schema:description We propose a unifying algorithm for non-smooth non-convex optimization. The algorithm approximates the objective function by a convex model function and finds an approximate (Bregman) proximal point of the convex model. This approximate minimizer of the model function yields a descent direction, along which the next iterate is found. Complemented with an Armijo-like line search strategy, we obtain a flexible algorithm for which we prove (subsequential) convergence to a stationary point under weak assumptions on the growth of the model function error. Special instances of the algorithm with a Euclidean distance function are, for example, gradient descent, forward–backward splitting, ProxDescent, without the common requirement of a “Lipschitz continuous gradient”. In addition, we consider a broad class of Bregman distance functions (generated by Legendre functions), replacing the Euclidean distance. The algorithm has a wide range of applications including many linear and nonlinear inverse problems in signal/image processing and machine learning.
19 schema:genre article
20 schema:isAccessibleForFree true
21 schema:isPartOf N11a0236fcaf14e9db3cfd7305786228f
22 Nd722b5a6a7c8418289dfe23aeaace230
23 sg:journal.1044187
24 schema:keywords Bregman distance function
25 Euclidean distance
26 Euclidean distance function
27 Lipschitz continuous gradient
28 addition
29 algorithm
30 applications
31 approximate minimizer
32 approximate proximal points
33 assumption
34 backward splitting
35 broad class
36 class
37 common requirement
38 continuous gradient
39 convergence
40 convex model
41 descent
42 descent direction
43 direction
44 distance
45 distance function
46 error
47 example
48 flexible algorithm
49 function
50 function errors
51 gradient
52 gradient descent
53 growth
54 image processing
55 instances
56 inverse problem
57 iterates
58 learning
59 line search strategy
60 machine learning
61 minimizers
62 model
63 model function
64 new algorithm
65 next iterate
66 non-convex optimization
67 non-smooth non-convex optimization
68 nonlinear inverse problem
69 objective function
70 optimization
71 point
72 problem
73 processing
74 proximal point
75 range
76 requirements
77 search strategy
78 signal/image processing
79 special instances
80 splitting
81 stationary points
82 strategies
83 unification
84 unifying algorithm
85 weak assumptions
86 wide range
87 schema:name Non-smooth Non-convex Bregman Minimization: Unification and New Algorithms
88 schema:pagination 244-278
89 schema:productId N1ec70c5784394f8598f8db8bad2f3224
90 N93a874bcf824477a8e59796e488bc655
91 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110421886
92 https://doi.org/10.1007/s10957-018-01452-0
93 schema:sdDatePublished 2022-10-01T06:44
94 schema:sdLicense https://scigraph.springernature.com/explorer/license/
95 schema:sdPublisher N572c224135354482943d0c0f9361c7cd
96 schema:url https://doi.org/10.1007/s10957-018-01452-0
97 sgo:license sg:explorer/license/
98 sgo:sdDataset articles
99 rdf:type schema:ScholarlyArticle
100 N11a0236fcaf14e9db3cfd7305786228f schema:issueNumber 1
101 rdf:type schema:PublicationIssue
102 N1ec70c5784394f8598f8db8bad2f3224 schema:name dimensions_id
103 schema:value pub.1110421886
104 rdf:type schema:PropertyValue
105 N572c224135354482943d0c0f9361c7cd schema:name Springer Nature - SN SciGraph project
106 rdf:type schema:Organization
107 N8fa3d9b174a74f8a83894cda1635a76a rdf:first sg:person.011151475055.48
108 rdf:rest Ne379aed4c0764fae9285f1e0a3010ef2
109 N92d24e7f4fe648409974c037772d1de2 rdf:first sg:person.012443225372.65
110 rdf:rest rdf:nil
111 N93a874bcf824477a8e59796e488bc655 schema:name doi
112 schema:value 10.1007/s10957-018-01452-0
113 rdf:type schema:PropertyValue
114 Nd722b5a6a7c8418289dfe23aeaace230 schema:volumeNumber 181
115 rdf:type schema:PublicationVolume
116 Ne379aed4c0764fae9285f1e0a3010ef2 rdf:first sg:person.015176300477.01
117 rdf:rest N92d24e7f4fe648409974c037772d1de2
118 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
119 schema:name Mathematical Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
122 schema:name Numerical and Computational Mathematics
123 rdf:type schema:DefinedTerm
124 sg:journal.1044187 schema:issn 0022-3239
125 1573-2878
126 schema:name Journal of Optimization Theory and Applications
127 schema:publisher Springer Nature
128 rdf:type schema:Periodical
129 sg:person.011151475055.48 schema:affiliation grid-institutes:grid.11749.3a
130 schema:familyName Ochs
131 schema:givenName Peter
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011151475055.48
133 rdf:type schema:Person
134 sg:person.012443225372.65 schema:affiliation grid-institutes:grid.5963.9
135 schema:familyName Brox
136 schema:givenName Thomas
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012443225372.65
138 rdf:type schema:Person
139 sg:person.015176300477.01 schema:affiliation grid-institutes:grid.463910.9
140 schema:familyName Fadili
141 schema:givenName Jalal
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015176300477.01
143 rdf:type schema:Person
144 sg:pub.10.1007/978-1-4419-8853-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049823794
145 https://doi.org/10.1007/978-1-4419-8853-9
146 rdf:type schema:CreativeWork
147 sg:pub.10.1007/978-1-4419-9467-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044558790
148 https://doi.org/10.1007/978-1-4419-9467-7
149 rdf:type schema:CreativeWork
150 sg:pub.10.1007/978-3-642-02431-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008570186
151 https://doi.org/10.1007/978-3-642-02431-3
152 rdf:type schema:CreativeWork
153 sg:pub.10.1007/bf00938486 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009261784
154 https://doi.org/10.1007/bf00938486
155 rdf:type schema:CreativeWork
156 sg:pub.10.1007/s10013-016-0238-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1074240182
157 https://doi.org/10.1007/s10013-016-0238-3
158 rdf:type schema:CreativeWork
159 sg:pub.10.1007/s10107-011-0484-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053470670
160 https://doi.org/10.1007/s10107-011-0484-9
161 rdf:type schema:CreativeWork
162 sg:pub.10.1007/s10107-013-0701-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012159026
163 https://doi.org/10.1007/s10107-013-0701-9
164 rdf:type schema:CreativeWork
165 sg:pub.10.1007/s10107-015-0943-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046288093
166 https://doi.org/10.1007/s10107-015-0943-9
167 rdf:type schema:CreativeWork
168 sg:pub.10.1007/s10957-013-0391-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012342771
169 https://doi.org/10.1007/s10957-013-0391-8
170 rdf:type schema:CreativeWork
171 sg:pub.10.1007/s11228-010-0147-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032025040
172 https://doi.org/10.1007/s11228-010-0147-7
173 rdf:type schema:CreativeWork
174 sg:pub.10.1023/b:jmiv.0000011320.81911.38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003031106
175 https://doi.org/10.1023/b:jmiv.0000011320.81911.38
176 rdf:type schema:CreativeWork
177 sg:pub.10.1038/44565 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052721759
178 https://doi.org/10.1038/44565
179 rdf:type schema:CreativeWork
180 grid-institutes:grid.11749.3a schema:alternateName Saarland University, Saarbrücken, Germany
181 schema:name Saarland University, Saarbrücken, Germany
182 rdf:type schema:Organization
183 grid-institutes:grid.463910.9 schema:alternateName Normandie Université ENSICAEN, CNRS, GREYC, Caen, France
184 schema:name Normandie Université ENSICAEN, CNRS, GREYC, Caen, France
185 rdf:type schema:Organization
186 grid-institutes:grid.5963.9 schema:alternateName University of Freiburg, Freiburg, Germany
187 schema:name University of Freiburg, Freiburg, Germany
188 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...