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

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

View graph of relations

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.
Original languageEnglish
JournalBIT Numerical Mathematics
Issue number2
Pages (from-to)329–356
StatePublished - 2012
CitationsWeb of Science® Times Cited: 43


  • Optimal first-order optimization methods, Total variation regularization, Tomography, Strong convexity
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 6437677