CONVERGENCE OF TRUNCATED HALF-QUADRATIC AND NEWTON ALGORITHMS, WITH APPLICATION TO IMAGE RESTORATION.

Abstract. We address the minimization of penalized least squares (PLS) criteria customarily used for edge-preserving restoration and reconstruction of signals and images. The minimization of PLS criteria can be addressed using a half-quadratic (HQ) scheme, according either to Geman & Reynolds (1992) or to Geman & Yang (1995) constructions. In the case of large-scale problems, the cost of the HQ approach is usually too high. In practice, it is rather proposed to implement an inexact HQ algorithm using a truncated conjugate gradient (TCG) method. This principle echoes that of truncated-Newton algorithms. Our contribution is to establish the convergence of the resulting truncated algorithms (HQ or Newton), under the same conditions required for the exact HQ scheme. Indeed, convergence is granted whatever the number of performed iterations of TCG. According to our experimental study on a deconvolution problem, the fastest versions correspond to severe truncation. This reinforces the interest for the truncated schemes, as fully valid algorithms in the field of image restoration. Key words. Convergence, half-quadratic algorithms, truncated-Newton methods, conjugate gradient, inverse problems, optimization, preconditioning, signal and image restoration. AMS subject classifications. 68W40, 68W25, 49N45, 90C06, 65Y20, 68U10 1. Introduction. Thi