Communications in Mathematical Sciences

Volume 21 (2023)

Number 2

On anisotropic non-Lipschitz restoration model: lower bound theory and iterative algorithm

Pages: 351 – 378



Chunlin Wu (School of Mathematical Sciences, Nankai University, Tianjin, China)

Xuan Lin (School of Mathematical Sciences, Nankai University, Tianjin, China)

Yufei Zhao (School of Mathematical Sciences, Nankai University, Tianjin, China)


For nonconvex and nonsmooth restoration models, the lower bound theory reveals their good edge recovery ability, and related analysis can help to design convergent algorithms. Existing such discussions are focused on isotropic regularization models, or only the lower bound theory of anisotropic model with a quadratic fidelity. In this paper, we consider a general image recovery model with a non-Lipschitz anisotropic composite regularization term and an $\ell_q$ norm $(1 \leq q \leq + \infty)$ data fidelity term. We establish the lower bound theory for the anisotropic model with an $\ell_1$ fidelity or an $\ell_\infty$ fidelity, which applies to impulsive noise or uniform noise (quantization error) removal problems. For the general case with $1 \leq q \leq + \infty$, a support inclusion analysis is provided. To solve this non-Lipschitz composite minimization model, we are then naturally motivated to extend previous works to introduce a support shrinking strategy in the iterative algorithm and relax the support constraint to a $\tau$-support (a thresholded version) constraint, which is more consistent with practical computation. The objective function at each iteration is also linearized to construct a strongly convex subproblem. To make the algorithm more implementable, we compute an approximation solution to this subproblem at each iteration, but not an exact one. The global convergence result of the proposed inexact iterative thresholding and support shrinking algorithm with proximal linearization is established. The experiments on image restoration and two-stage image segmentation demonstrate the effectiveness of the proposed algorithm.


image restoration, anisotropic model, non-Lipschitz optimization, lower bound theory, thresholding, support shrinking

2010 Mathematics Subject Classification

49K30, 49N45, 90C26, 94A08

Received 2 March 2021

Received revised 12 January 2022

Accepted 29 May 2022

Published 1 February 2023