Efficient Schemes for Total Variation Minimization Under Constraints in Image Processing

This paper presents new fast algorithms to minimize total variation and more generally l¹-norms under a general convex constraint. Such problems are standards of image processing. The algorithms are based on a recent advance in convex optimization proposed by Yurii Nesterov. Depending on the regularity of the data fidelity term, we solve either a primal problem or a dual problem. First we show that standard first-order schemes allow one to get solutions of precision ε in O(1/ε²) iterations at worst. We propose a scheme that allows one to obtain a solution of precision ε in O(1/ε) iterations for a general convex constraint. For a strongly convex constraint, we solve a dual problem with a scheme that requires O(1√ε) iterations to get a solution of precision ε. Finally we perform some numerical experiments which confirm the theoretical results on various problems of image processing.