Sparsity-inducing Nonconvex Nonseparable Regularization for Convex Image Processing

A popular strategy for determining solutions to linear least-squares problems relies on using sparsity-promoting regularizers and is widely exploited in image processing applications such as, e.g., image denoising, deblurring and inpainting. It is well known that, in general, non-convex regularizers hold the potential for promoting sparsity more effectively than convex regularizers such as, e.g., those involving the $ell_1$ norm. To avoid the intrinsic difficulties related to non-convex optimization, the Convex Non-Convex (CNC) strategy has been proposed, which allows the use of non-convex regularization while maintaining convexity of the total objective function. In this paper, a new CNC variational model is proposed, based on a more general parametric non-convex non-separable regularizer. The proposed model is applicable to a greater variety of image processing problems than prior CNC methods. We derive the convexity conditions and related theoretical properties of the presented CNC model, and we analyze existence and uniqueness of its solutions. A primal-dual forward-backward splitting algorithm is proposed for solving the related saddle-point problem. The convergence of the algorithm is demonstrated theoretically and validated empirically. Several numerical experiments are presented which prove the effectiveness of the proposed approach.