Implementation of an optimal first-order method for strongly convex total variation regularization

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Standard

Implementation of an optimal first-order method for strongly convex total variation regularization. / Jensen, Tobias Lindstrøm; Jørgensen, Jakob Heide; Hansen, Per Christian; Jensen, Søren Holdt.

In: Bit (Lisse), Vol. 52, No. 2, 2012, p. 329–356.

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Harvard

APA

CBE

MLA

Vancouver

Author

Jensen, Tobias Lindstrøm; Jørgensen, Jakob Heide; Hansen, Per Christian; Jensen, Søren Holdt / Implementation of an optimal first-order method for strongly convex total variation regularization.

In: Bit (Lisse), Vol. 52, No. 2, 2012, p. 329–356.

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Bibtex

@article{84e6ab778006449db28da18a1b93e39b,
title = "Implementation of an optimal first-order method for strongly convex total variation regularization",
keywords = "Optimal first-order optimization methods, Total variation regularization, Tomography, Strong convexity",
publisher = "Springer Netherlands",
author = "Jensen, {Tobias Lindstrøm} and Jørgensen, {Jakob Heide} and Hansen, {Per Christian} and Jensen, {Søren Holdt}",
year = "2012",
doi = "10.1007/s10543-011-0359-8",
volume = "52",
number = "2",
pages = "329–356",
journal = "Bit (Lisse)",
issn = "0006-3835",

}

RIS

TY - JOUR

T1 - Implementation of an optimal first-order method for strongly convex total variation regularization

A1 - Jensen,Tobias Lindstrøm

A1 - Jørgensen,Jakob Heide

A1 - Hansen,Per Christian

A1 - Jensen,Søren Holdt

AU - Jensen,Tobias Lindstrøm

AU - Jørgensen,Jakob Heide

AU - Hansen,Per Christian

AU - Jensen,Søren Holdt

PB - Springer Netherlands

PY - 2012

Y1 - 2012

N2 - We present a practical implementation of an optimal first-order method, due to Nesterov, for large-scale total variation regularization in tomographic reconstruction, image deblurring, etc. The algorithm applies to μ-strongly convex objective functions with L-Lipschitz continuous gradient. In the framework of Nesterov both μ and L are assumed known—an assumption that is seldom satisfied in practice. We propose to incorporate mechanisms to estimate locally sufficient μ and L during the iterations. The mechanisms also allow for the application to non-strongly convex functions. We discuss the convergence rate and iteration complexity of several first-order methods, including the proposed algorithm, and we use a 3D tomography problem to compare the performance of these methods. In numerical simulations we demonstrate the advantage in terms of faster convergence when estimating the strong convexity parameter μ for solving ill-conditioned problems to high accuracy, in comparison with an optimal method for non-strongly convex problems and a first-order method with Barzilai-Borwein step size selection.

AB - We present a practical implementation of an optimal first-order method, due to Nesterov, for large-scale total variation regularization in tomographic reconstruction, image deblurring, etc. The algorithm applies to μ-strongly convex objective functions with L-Lipschitz continuous gradient. In the framework of Nesterov both μ and L are assumed known—an assumption that is seldom satisfied in practice. We propose to incorporate mechanisms to estimate locally sufficient μ and L during the iterations. The mechanisms also allow for the application to non-strongly convex functions. We discuss the convergence rate and iteration complexity of several first-order methods, including the proposed algorithm, and we use a 3D tomography problem to compare the performance of these methods. In numerical simulations we demonstrate the advantage in terms of faster convergence when estimating the strong convexity parameter μ for solving ill-conditioned problems to high accuracy, in comparison with an optimal method for non-strongly convex problems and a first-order method with Barzilai-Borwein step size selection.

KW - Optimal first-order optimization methods

KW - Total variation regularization

KW - Tomography

KW - Strong convexity

U2 - 10.1007/s10543-011-0359-8

DO - 10.1007/s10543-011-0359-8

JO - Bit (Lisse)

JF - Bit (Lisse)

SN - 0006-3835

IS - 2

VL - 52

SP - 329

EP - 356

ER -