Penalty decomposition method for solving ℓ0 regularized problems: Application to trend filtering

In this paper we consider constrained ℓ₀ sparse optimization problems, that is, constrained problems with the objective function composed of a smooth part and an ℓ₀ regularization term. We analyze a penalty decomposition (PD) method for solving these nonconvex problems, in which a sequence of penalty subproblems are solved by alternating minimization (AM) method. Although the (AM) method finds only a local solution of the subproblem, the sequence generated by (PD) algorithm converges to a local minimum of the original problem. We estimate the iteration complexity of the (AM) method used for finding a local minimum of the penalty subproblem. In particular we prove that, under strong convexity assumption, this method has linear convergence. As an application for our general model, we propose the ℓ₀ trend filtering for estimation of the mean and variance of a given time series. We test the practical performance of our (PD) algorithm on such ℓ₀ trend filtering problems.