Accelerated Alternating Descent Methods for Dykstra-Like Problems

Antonin Chambolle; Pauline Tan; Samuel Vaiter

doi:10.1007/s10851-017-0724-6

Accelerated Alternating Descent Methods for Dykstra-Like Problems

Antonin Chambolle
, Pauline Tan
, Samuel Vaiter

Ecole polytechnique
Centre de Recherches de Climatologie, CNRS UMR 5210, Université de Bourgogne

Research output: Contribution to journal › Article › peer-review

15 Citations (Scopus)

Abstract

This paper extends recent results by the first author and T. Pock (ICG, TU Graz, Austria) on the acceleration of alternating minimization techniques for quadratic plus nonsmooth objectives depending on two variables. We discuss here the strongly convex situation, and how ‘fast’ methods can be derived by adapting the overrelaxation strategy of Nesterov for projected gradient descent. We also investigate slightly more general alternating descent methods, where several descent steps in each variable are alternatively performed.

Original language	English
Pages (from-to)	481-497
Number of pages	17
Journal	Journal of Mathematical Imaging and Vision
Volume	59
Issue number	3
DOIs	https://doi.org/10.1007/s10851-017-0724-6
Publication status	Published - 1 Nov 2017
Externally published	Yes

Keywords

Accelerated methods
Alternating minimizations
Block descent algorithms
Total variation minimization

Access to Document

10.1007/s10851-017-0724-6

Cite this

@article{b1eefbc909ad4d61bbbd2fd1a973da85,

title = "Accelerated Alternating Descent Methods for Dykstra-Like Problems",

abstract = "This paper extends recent results by the first author and T. Pock (ICG, TU Graz, Austria) on the acceleration of alternating minimization techniques for quadratic plus nonsmooth objectives depending on two variables. We discuss here the strongly convex situation, and how {\textquoteleft}fast{\textquoteright} methods can be derived by adapting the overrelaxation strategy of Nesterov for projected gradient descent. We also investigate slightly more general alternating descent methods, where several descent steps in each variable are alternatively performed.",

keywords = "Accelerated methods, Alternating minimizations, Block descent algorithms, Total variation minimization",

author = "Antonin Chambolle and Pauline Tan and Samuel Vaiter",

note = "Publisher Copyright: {\textcopyright} 2017, Springer Science+Business Media New York.",

year = "2017",

month = nov,

day = "1",

doi = "10.1007/s10851-017-0724-6",

language = "English",

volume = "59",

pages = "481--497",

journal = "Journal of Mathematical Imaging and Vision",

issn = "0924-9907",

number = "3",

}

TY - JOUR

T1 - Accelerated Alternating Descent Methods for Dykstra-Like Problems

AU - Chambolle, Antonin

AU - Tan, Pauline

AU - Vaiter, Samuel

PY - 2017/11/1

Y1 - 2017/11/1

N2 - This paper extends recent results by the first author and T. Pock (ICG, TU Graz, Austria) on the acceleration of alternating minimization techniques for quadratic plus nonsmooth objectives depending on two variables. We discuss here the strongly convex situation, and how ‘fast’ methods can be derived by adapting the overrelaxation strategy of Nesterov for projected gradient descent. We also investigate slightly more general alternating descent methods, where several descent steps in each variable are alternatively performed.

AB - This paper extends recent results by the first author and T. Pock (ICG, TU Graz, Austria) on the acceleration of alternating minimization techniques for quadratic plus nonsmooth objectives depending on two variables. We discuss here the strongly convex situation, and how ‘fast’ methods can be derived by adapting the overrelaxation strategy of Nesterov for projected gradient descent. We also investigate slightly more general alternating descent methods, where several descent steps in each variable are alternatively performed.

KW - Accelerated methods

KW - Alternating minimizations

KW - Block descent algorithms

KW - Total variation minimization

UR - https://www.scopus.com/pages/publications/85015709706

U2 - 10.1007/s10851-017-0724-6

DO - 10.1007/s10851-017-0724-6

M3 - Article

AN - SCOPUS:85015709706

SN - 0924-9907

VL - 59

SP - 481

EP - 497

JO - Journal of Mathematical Imaging and Vision

JF - Journal of Mathematical Imaging and Vision

IS - 3

ER -

Accelerated Alternating Descent Methods for Dykstra-Like Problems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this