This paper investigates a semismooth Newton based augmented Lagrangian (SSNAL) algorithm for solving equivalent formulation of the general l(1) trend filtering problem. The computational costs of a semismooth Newton (SSN) algorithm for solving the subproblem in the SSNAL algorithm can be substantially reduced by exploiting the second order sparsity of Hessian matrix and some efficient techniques. The global convergence and the asymptotically superlinear local convergence of the SSNAL algorithm are given under mild conditions. Numerical comparisons between the SSNAL algorithm and other state-of-the-art algorithms on real and synthetic data sets validate that our algorithm has superior performance in both robustness and efficiency.
展开▼
