Noname manuscript No. (will be inserted by the editor) Implementation of an Optimal First-Order Method for Strongly Convex Total Variation Regularization

Abstract We present a practical implementation of an optimal first-order method, due to Nesterov, for large-scale total variation regularization in tomographic recon-struction, 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 iteration complexity of several first-order methods, inclu-ding the proposed algorithm, and we use a 3D tomography problem to compare the performance of these methods. The results show that for ill-conditioned problems solved to high accuracy, the proposed method significantly outperforms state-of-the-art first-order methods, as also suggested by theoretical results