Newton method for the composite row sparsity regularized optimization

This paper is concerned with the composite row sparsity regularized (cRSR) minimization problem, which captures a number of important applications arising in machine learning, statistics, signal and image processing, and so forth. Due to the non-convexity and discontinuity of the composite row sparsity regularization term, the cRSR problem is NP-hard in general. In this paper, we study the optimality conditions of the cRSR problem and derive its stationary equation which is crucial to design efficient algorithms. Based on this stationary equation, an easy-to-implement Newton method is designed to solve the cRSR problem (NcRSR). The quadratic convergence rate and iteration complexity estimation of NcRSR are rigorously proved under some mild conditions. Furthermore, NcRSR is used for solving the regularized clustering and trend filtering problems. Extensive experimental results illustrate that our approach has superior performance compared with the state-of-the-art methods. In particular, NcRSR not only possesses perfect clustering performance and estimation accuracy but also is faster than all the compared methods.