A Proximal Point Semismooth Newton Algorithm for Structural Composite Cardinality Optimization

Abstract

Many image-processing problems can be formulated as composite cardinality optimization (CCOP), whose objective is the sum of two convex terms and a cardinality function composed with a linear operator. The composite cardinality term creates major algorithmic challenges: the separability of the cardinality function is lost and convergence analysis often requires surjectivity-type assumptions on the linear operators. To overcome these challenges, we consider the stationary dual formulation of CCOP, which has more favorable structure consisting of two convex terms and a separable cardinality function. In this paper, we develop an efficient proximal point algorithm (PPA) to solve the stationary dual problem. The efficiency of our PPA stems from two aspects. Firstly, the key step of its subproblem solver minimizes a smooth convex function over a low-dimensional subspace by the classic semismooth Newton algorithm (SNA), which has global convergence and local superlinear rate under suitable conditions. Secondly, implementable inexact criteria are proposed for early termination of the SNA subroutine. These components form the basic framework of our inexact PPA. Under suitable conditions, it enjoys global convergence and local linear convergence rate. In particular, we provide examples in which the convergence assumptions are automatically satisfied. Finally, the SNA subroutine is incorporated into our inexact PPA to solve jump-sparse signal recovery and computed tomography (CT) image restoration. Numerical results demonstrate the time efficiency and solution accuracy of our proposed method.