An optimization-based multilevel algorithm for total variation image denoising

This paper proposes a fast multilevel method using primal relaxations for the total variation image denoising and analyzes its convergence. The basic primal relaxation is known to get stuck at a nonstationary point (nearly a local minimum) of the minimization, whose solution is known to be "nonsmooth" in the space of functions with bounded variation. Our idea is to use coarse level corrections, overcoming the deadlock in a basic primal relaxation scheme and achieving much improvement over relaxation. Moreover, to reach a global minimizer, further refinement of the multilevel method is needed, and we propose a nonregular coarse level based on a patch-detection idea (relating to hemivariateness) to correct and improve the standard multilevel method. Both algorithmic and analytical results together with numerical experiments on both one- and two-dimensional images are presented.