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

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 mu-strongly convex objective functions with L-Lipschitz continuous gradient. In the framework of Nesterov both mu and L are assumed known-an assumption that is seldom satisfied in practice. We propose to incorporate mechanisms to estimate locally sufficient mu 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 mu 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.