On the convergence of the lagged diffusivity fixed point method in total variation image restoration

In this paper we show that the lagged diffusivity fixed point algorithm int roduced by Vogel and Oman in [SIAM J. Sci. Comput., 17 (1996), pp. 227-238] to solve the problem of total variation denoising, proposed by Rudin, Oshe r, and Fatemi in [Phys. D, 60 (1992), pp. 259-268], is a particular instanc e of a class of algorithms introduced by Voss and Eckhardt in [Computing, 2 5 (1980), pp. 243-251], whose origins can be traced back to Weiszfeld's ori ginal work for minimizing a sum of Euclidean lengths [Tohoku Math. J., 43 ( 1937), pp. 355-386]. There have recently appeared several proofs for the co nvergence of this algorithm [G. Aubert et al., Technical report 94-01, Info rmatique, Signaux et Systemes de Sophia Antipolis, 1994], [A. Chambolle and P.-L. Lions, Technical report 9509, CEREMADE, 1995], and [D. C. Dobson and C. R. Vogel, SIAM J. Numer. Anal., 34 (1997), pp. 1779-1791]. Here we pres ent a proof of the global and linear convergence using the framework introd uced in [H. Voss and U. Eckhart, Computing, 25 (1980), pp. 243-251] and giv e a bound for the convergence rate of the fixed point iteration that agrees with our experimental results. These results are also valid for suitable g eneralizations of the fixed point algorithm.