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

Tobias Lindstrøm Jensen, Jakob Heide Jørgensen, Per Christian Hansen, Søren Holdt Jensen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    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
    Volume52
    Issue number2
    Pages (from-to)329–356
    ISSN0006-3835
    DOIs
    Publication statusPublished - 2012

    Keywords

    • Optimal first-order optimization methods
    • Total variation regularization
    • Tomography
    • Strong convexity

    Fingerprint Dive into the research topics of 'Implementation of an optimal first-order method for strongly convex total variation regularization'. Together they form a unique fingerprint.

    Cite this