A primal-dual active-set method for non-negativity constrained total variation deblurring problems

Abstract

This thesis studies image deblurring problems using a total variationbased model, with a non-negativity constraint. The addition of thenon-negativity constraint improves the quality of the solutions butmakes the process of solution a difficult one. The contribution of ourwork is a fast and robust numerical algorithm to solve thenon-negatively constrained problem. To overcome thenon-differentiability of the total variation norm, we formulate theconstrained deblurring problem as a primal-dual program which is avariant of the formulation proposed by Chan, Golub and Mulet\cite{cgm} (CGM) for unconstrained problems. Here, dual refers to acombination of the Lagrangian and Fenchel duals. To solve theconstrained primal-dual program, we use a semi-smooth Newton'smethod. We exploit the relationship, established in \cite{hik},between the semi-smooth Newton's method and the Primal-Dual ActiveSet (PDAS) method to achieve considerable simplification of thecomputations. The main advantages of our proposed scheme are: noparameters need significant adjustment, a standard inversepreconditioner works very well, quadratic rate of local convergence(theoretical and numerical), numerical evidence of globalconvergence, and high accuracy of solving the KKT system. The schemeshows robustness of performance over a wide range of parameters. Acomprehensive set of numerical comparisons are provided againstother methods to solve the same problem which show the speed andaccuracy advantages of our scheme. The Matlab and C (Mex) code for all the experiments conducted in this thesis may be downloaded from\url{http://www.math.nus.edu.sg/~mhyip/nncgm/}.