Global optimality analysis and solution of the ℓ₀ total variation signal denoising model

The total variation regularizer is diffusely emerged in statistics, image and signal processing to obtain piecewise constant estimator. The ℓ₀ total variation (L0TV) regularized signal denoising model is a nonconvex and discontinuous optimization problem, and it is very difficult to find its global optimal solution. In this paper, we present the global optimality analysis of L0TV signal denoising model, and design an efficient algorithm to pursuit its solution. Firstly, we equivalently rewrite the L0TV denoising model as a partial regularized (PL0R) minimization problem by aid of the structured difference operator. Subsequently, we define a P-stationary point of PL0R, and show that it is a global optimal solution. These theoretical results allow us to find the global optimal solution of the L0TV model. Therefore, an efficient Newton-type algorithm is proposed for the PL0R problem. The algorithm has a considerably low computational complexity in each iteration. Finally, experimental results demonstrate the excellent performance of our approach in comparison with several state-of-the-art methods.