A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-12-21

AUTHORS

Antonin Chambolle, Thomas Pock

ABSTRACT

In this paper we study a first-order primal-dual algorithm for non-smooth convex optimization problems with known saddle-point structure. We prove convergence to a saddle-point with rate O(1/N) in finite dimensions for the complete class of problems. We further show accelerations of the proposed algorithm to yield improved rates on problems with some degree of smoothness. In particular we show that we can achieve O(1/N2) convergence on problems, where the primal or the dual objective is uniformly convex, and we can show linear convergence, i.e. O(ωN) for some ω∈(0,1), on smooth problems. The wide applicability of the proposed algorithm is demonstrated on several imaging problems such as image denoising, image deconvolution, image inpainting, motion estimation and multi-label image segmentation. More... »

PAGES

120-145

References to SciGraph publications

  • 2005. Total Variation Minimization and a Class of Binary MRF Models in ENERGY MINIMIZATION METHODS IN COMPUTER VISION AND PATTERN RECOGNITION
  • 2009-03-05. Convexity Properties Associated with Nonconvex Quadratic Matrix Functions and Applications to Quadratic Programming in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 2004. Introductory Lectures on Convex Optimization, A Basic Course in NONE
  • 1986. A Method for Finding Projections onto the Intersection of Convex Sets in Hilbert Spaces in ADVANCES IN ORDER RESTRICTED STATISTICAL INFERENCE
  • 2004-12-29. Smooth minimization of non-smooth functions in MATHEMATICAL PROGRAMMING
  • 2007-01-01. A Duality Based Approach for Realtime TV-L1 Optical Flow in PATTERN RECOGNITION
  • 1995-12. Soap films and covering spaces in THE JOURNAL OF GEOMETRIC ANALYSIS
  • 2004-01. An Algorithm for Total Variation Minimization and Applications in JOURNAL OF MATHEMATICAL IMAGING AND VISION
  • 1992-04. On the Douglas—Rachford splitting method and the proximal point algorithm for maximal monotone operators in MATHEMATICAL PROGRAMMING
  • 1986-07. A finite algorithm for finding the projection of a point onto the canonical simplex of ∝n in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10851-010-0251-1

    DOI

    http://dx.doi.org/10.1007/s10851-010-0251-1

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "CMAP, Ecole Polytechnique, CNRS, 91128, Palaiseau, France", 
              "id": "http://www.grid.ac/institutes/grid.462265.1", 
              "name": [
                "CMAP, Ecole Polytechnique, CNRS, 91128, Palaiseau, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chambolle", 
            "givenName": "Antonin", 
            "id": "sg:person.015355621223.54", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015355621223.54"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute for Computer Graphics and Vision, Graz University of Technology, 8010, Graz, Austria", 
              "id": "http://www.grid.ac/institutes/grid.410413.3", 
              "name": [
                "Institute for Computer Graphics and Vision, Graz University of Technology, 8010, Graz, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pock", 
            "givenName": "Thomas", 
            "id": "sg:person.015744126036.09", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015744126036.09"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s10107-004-0552-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030642071", 
              "https://doi.org/10.1007/s10107-004-0552-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/b:jmiv.0000011325.36760.1e", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043097522", 
              "https://doi.org/10.1023/b:jmiv.0000011325.36760.1e"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10957-009-9539-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052181262", 
              "https://doi.org/10.1007/s10957-009-9539-y"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11585978_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050742914", 
              "https://doi.org/10.1007/11585978_10"
            ], 
            "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/bf00938486", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009261784", 
              "https://doi.org/10.1007/bf00938486"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-9940-7_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042788606", 
              "https://doi.org/10.1007/978-1-4613-9940-7_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02921771", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017374567", 
              "https://doi.org/10.1007/bf02921771"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74936-3_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016508230", 
              "https://doi.org/10.1007/978-3-540-74936-3_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01581204", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022153870", 
              "https://doi.org/10.1007/bf01581204"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010-12-21", 
        "datePublishedReg": "2010-12-21", 
        "description": "In this paper we study a first-order primal-dual algorithm for non-smooth convex optimization problems with known saddle-point structure. We prove convergence to a saddle-point with rate O(1/N) in finite dimensions for the complete class of problems. We further show accelerations of the proposed algorithm to yield improved rates on problems with some degree of smoothness. In particular we show that we can achieve O(1/N2) convergence on problems, where the primal or the dual objective is uniformly convex, and we can show linear convergence, i.e. O(\u03c9N) for some \u03c9\u2208(0,1), on smooth problems. The wide applicability of the proposed algorithm is demonstrated on several imaging problems such as image denoising, image deconvolution, image inpainting, motion estimation and multi-label image segmentation.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10851-010-0251-1", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1041815", 
            "issn": [
              "0924-9907", 
              "1573-7683"
            ], 
            "name": "Journal of Mathematical Imaging and Vision", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "40"
          }
        ], 
        "keywords": [
          "non-smooth convex optimization problem", 
          "convex optimization problem", 
          "first-order primal-dual algorithm", 
          "saddle point structure", 
          "primal-dual algorithm", 
          "multi-label image segmentation", 
          "degree of smoothness", 
          "smooth problems", 
          "linear convergence", 
          "convex problem", 
          "optimization problem", 
          "finite dimensions", 
          "dual algorithm", 
          "complete class", 
          "motion estimation", 
          "convergence", 
          "image deconvolution", 
          "algorithm", 
          "wide applicability", 
          "problem", 
          "image denoising", 
          "convex", 
          "dual objectives", 
          "image segmentation", 
          "image inpainting", 
          "smoothness", 
          "estimation", 
          "class", 
          "denoising", 
          "applicability", 
          "deconvolution", 
          "dimensions", 
          "acceleration", 
          "inpainting", 
          "applications", 
          "structure", 
          "segmentation", 
          "improved rates", 
          "degree", 
          "objective", 
          "rate", 
          "imaging", 
          "paper"
        ], 
        "name": "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging", 
        "pagination": "120-145", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1010318529"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10851-010-0251-1"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10851-010-0251-1", 
          "https://app.dimensions.ai/details/publication/pub.1010318529"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-11-24T20:54", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_499.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10851-010-0251-1"
      }
    ]
     

    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/s10851-010-0251-1'

    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/s10851-010-0251-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10851-010-0251-1'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10851-010-0251-1'


     

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

    150 TRIPLES      21 PREDICATES      77 URIs      59 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10851-010-0251-1 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author Nce7c8dcc91bb4d9a93aac91efa4183a7
    4 schema:citation sg:pub.10.1007/11585978_10
    5 sg:pub.10.1007/978-1-4419-8853-9
    6 sg:pub.10.1007/978-1-4613-9940-7_3
    7 sg:pub.10.1007/978-3-540-74936-3_22
    8 sg:pub.10.1007/bf00938486
    9 sg:pub.10.1007/bf01581204
    10 sg:pub.10.1007/bf02921771
    11 sg:pub.10.1007/s10107-004-0552-5
    12 sg:pub.10.1007/s10957-009-9539-y
    13 sg:pub.10.1023/b:jmiv.0000011325.36760.1e
    14 schema:datePublished 2010-12-21
    15 schema:datePublishedReg 2010-12-21
    16 schema:description In this paper we study a first-order primal-dual algorithm for non-smooth convex optimization problems with known saddle-point structure. We prove convergence to a saddle-point with rate O(1/N) in finite dimensions for the complete class of problems. We further show accelerations of the proposed algorithm to yield improved rates on problems with some degree of smoothness. In particular we show that we can achieve O(1/N2) convergence on problems, where the primal or the dual objective is uniformly convex, and we can show linear convergence, i.e. O(ωN) for some ω∈(0,1), on smooth problems. The wide applicability of the proposed algorithm is demonstrated on several imaging problems such as image denoising, image deconvolution, image inpainting, motion estimation and multi-label image segmentation.
    17 schema:genre article
    18 schema:isAccessibleForFree true
    19 schema:isPartOf N5502b8a3329345dfaeae879ffc9cf4b0
    20 N9718bb9fa951479c82e3c617b3034b74
    21 sg:journal.1041815
    22 schema:keywords acceleration
    23 algorithm
    24 applicability
    25 applications
    26 class
    27 complete class
    28 convergence
    29 convex
    30 convex optimization problem
    31 convex problem
    32 deconvolution
    33 degree
    34 degree of smoothness
    35 denoising
    36 dimensions
    37 dual algorithm
    38 dual objectives
    39 estimation
    40 finite dimensions
    41 first-order primal-dual algorithm
    42 image deconvolution
    43 image denoising
    44 image inpainting
    45 image segmentation
    46 imaging
    47 improved rates
    48 inpainting
    49 linear convergence
    50 motion estimation
    51 multi-label image segmentation
    52 non-smooth convex optimization problem
    53 objective
    54 optimization problem
    55 paper
    56 primal-dual algorithm
    57 problem
    58 rate
    59 saddle point structure
    60 segmentation
    61 smooth problems
    62 smoothness
    63 structure
    64 wide applicability
    65 schema:name A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging
    66 schema:pagination 120-145
    67 schema:productId N63d4d3db39294185af8afe736d62972d
    68 Nec3bf6e9957741c49a71616dbc0f4c68
    69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010318529
    70 https://doi.org/10.1007/s10851-010-0251-1
    71 schema:sdDatePublished 2022-11-24T20:54
    72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    73 schema:sdPublisher Nce741c9f5dda45f481fc57ddabfbc2d0
    74 schema:url https://doi.org/10.1007/s10851-010-0251-1
    75 sgo:license sg:explorer/license/
    76 sgo:sdDataset articles
    77 rdf:type schema:ScholarlyArticle
    78 N5502b8a3329345dfaeae879ffc9cf4b0 schema:issueNumber 1
    79 rdf:type schema:PublicationIssue
    80 N63d4d3db39294185af8afe736d62972d schema:name doi
    81 schema:value 10.1007/s10851-010-0251-1
    82 rdf:type schema:PropertyValue
    83 N76d19646d4584b3d821b694a92ee7cc9 rdf:first sg:person.015744126036.09
    84 rdf:rest rdf:nil
    85 N9718bb9fa951479c82e3c617b3034b74 schema:volumeNumber 40
    86 rdf:type schema:PublicationVolume
    87 Nce741c9f5dda45f481fc57ddabfbc2d0 schema:name Springer Nature - SN SciGraph project
    88 rdf:type schema:Organization
    89 Nce7c8dcc91bb4d9a93aac91efa4183a7 rdf:first sg:person.015355621223.54
    90 rdf:rest N76d19646d4584b3d821b694a92ee7cc9
    91 Nec3bf6e9957741c49a71616dbc0f4c68 schema:name dimensions_id
    92 schema:value pub.1010318529
    93 rdf:type schema:PropertyValue
    94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Information and Computing Sciences
    96 rdf:type schema:DefinedTerm
    97 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    98 schema:name Artificial Intelligence and Image Processing
    99 rdf:type schema:DefinedTerm
    100 sg:journal.1041815 schema:issn 0924-9907
    101 1573-7683
    102 schema:name Journal of Mathematical Imaging and Vision
    103 schema:publisher Springer Nature
    104 rdf:type schema:Periodical
    105 sg:person.015355621223.54 schema:affiliation grid-institutes:grid.462265.1
    106 schema:familyName Chambolle
    107 schema:givenName Antonin
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015355621223.54
    109 rdf:type schema:Person
    110 sg:person.015744126036.09 schema:affiliation grid-institutes:grid.410413.3
    111 schema:familyName Pock
    112 schema:givenName Thomas
    113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015744126036.09
    114 rdf:type schema:Person
    115 sg:pub.10.1007/11585978_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050742914
    116 https://doi.org/10.1007/11585978_10
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/978-1-4419-8853-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049823794
    119 https://doi.org/10.1007/978-1-4419-8853-9
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/978-1-4613-9940-7_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042788606
    122 https://doi.org/10.1007/978-1-4613-9940-7_3
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/978-3-540-74936-3_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016508230
    125 https://doi.org/10.1007/978-3-540-74936-3_22
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/bf00938486 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009261784
    128 https://doi.org/10.1007/bf00938486
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/bf01581204 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022153870
    131 https://doi.org/10.1007/bf01581204
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/bf02921771 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017374567
    134 https://doi.org/10.1007/bf02921771
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/s10107-004-0552-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030642071
    137 https://doi.org/10.1007/s10107-004-0552-5
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/s10957-009-9539-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1052181262
    140 https://doi.org/10.1007/s10957-009-9539-y
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1023/b:jmiv.0000011325.36760.1e schema:sameAs https://app.dimensions.ai/details/publication/pub.1043097522
    143 https://doi.org/10.1023/b:jmiv.0000011325.36760.1e
    144 rdf:type schema:CreativeWork
    145 grid-institutes:grid.410413.3 schema:alternateName Institute for Computer Graphics and Vision, Graz University of Technology, 8010, Graz, Austria
    146 schema:name Institute for Computer Graphics and Vision, Graz University of Technology, 8010, Graz, Austria
    147 rdf:type schema:Organization
    148 grid-institutes:grid.462265.1 schema:alternateName CMAP, Ecole Polytechnique, CNRS, 91128, Palaiseau, France
    149 schema:name CMAP, Ecole Polytechnique, CNRS, 91128, Palaiseau, France
    150 rdf:type schema:Organization
     




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


    ...