Semismooth Newton Algorithm for Efficient Projections onto _1, -norm Ball

Code

• github.com/djchu/projontol1inf
  OfficialIn papernone★ 7

Abstract

Structured sparsity-inducing _1, -norm, as a generalization of the classical _1-norm, plays an important role in jointly sparse models which select or remove simultaneously all the variables forming a group. However, its resulting problem is more difficult to solve than the conventional _1-norm constrained problem. In this paper, we propose an efficient algorithm for Euclidean projection onto _1, -norm ball. We tackle the projection problem via semismooth Newton algorithm to solve the system of semismooth equations. Meanwhile, exploiting the structure of Jacobian matrix via LU decomposition yields an equivalent algorithm which is proved to terminate after a finite number of iterations. Empirical studies demonstrate that our proposed algorithm outperforms the existing state-of-the-art solver and is promising for the optimization of learning problems with _1, -norm ball constraint.

Reproductions