A Globally Convergent Algorithm for a Constrained Non-Lipschitz Image Restoration Model

In this paper, we study a non-Lipschitz and box-constrained model for both piecewise constant and natural image restoration with Gaussian noise removal. It consists of non-Lipschitz isotropic first-order ℓp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _{p}$$\end{document} (0<p<1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$0<p<1$$\end{document}) and second-order ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _{1}$$\end{document} as regularization terms to keep edges and overcome staircase effects in smooth regions simultaneously. The model thus combines the advantages of non-Lipschitz and high order regularization, as well as box constraints. Although this model is quite complicated to analyze, we establish a motivating theorem, which induces an iterative support shrinking algorithm with proximal linearization. This algorithm can be easily implemented and is globally convergent. In the convergence analysis, a key step is to prove a lower bound theory for the nonzero entries of the gradient of the iterative sequence. This theory also provides a theoretical guarantee for the edge preserving property of the algorithm. Extensive numerical experiments and comparisons indicate that our method is very effective for both piecewise constant and natural image restoration.