Repository logo
 

Choose your path wisely: gradient descent in a Bregman distance framework

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Betcke, Marta M 
Ehrhardt, Matthias J 
Schönlieb, Carola-Bibiane 

Abstract

We propose an extension of a special form of gradient descent --- in the literature known as linearised Bregman iteration -- to a larger class of non-convex functions. We replace the classical (squared) two norm metric in the gradient descent setting with a generalised Bregman distance, based on a proper, convex and lower semi-continuous function. The algorithm's global convergence is proven for functions that satisfy the Kurdyka-\L ojasiewicz property. Examples illustrate that features of different scale are being introduced throughout the iteration, transitioning from coarse to fine. This coarse-to-fine approach with respect to scale allows to recover solutions of non-convex optimisation problems that are superior to those obtained with conventional gradient descent, or even projected and proximal gradient descent. The effectiveness of the linearised Bregman iteration in combination with early stopping is illustrated for the applications of parallel magnetic resonance imaging, blind deconvolution as well as image classification with neural networks.

Description

Keywords

math.OC, math.OC, 49M37, 65K05, 65K10, 90C26, 90C30

Journal Title

SIAM Journal on Imaging Sciences

Conference Name

Journal ISSN

1936-4954
1936-4954

Volume Title

14

Publisher

Society for Industrial and Applied Mathematics

Rights

All rights reserved
Sponsorship
Engineering and Physical Sciences Research Council (EP/M00483X/1)
Leverhulme Trust (RPG-2015-250)
Engineering and Physical Sciences Research Council (EP/N014588/1)
European Commission Horizon 2020 (H2020) Marie Sk?odowska-Curie actions (691070)
European Commission Horizon 2020 (H2020) Marie Sk?odowska-Curie actions (777826)
Leverhulme Trust (RPG-2018-121)
Leverhulme Trust (PLP-2017-275)
Alan Turing Institute (Unknown)
EPSRC (EP/S026045/1)
EPSRC (EP/T017961/1)
Royal Society (RSWF\R3\193016)
EPSRC (EP/T003553/1)
Relationships
Is supplemented by: